Markov Chains - A Mathematical Treatise

Markov Chains

We have a set of stated, $\mathcal{S}$ = {${s_1, s_2, ..., s_m}$}. A Markov process starts in one of these states and moves successively from one state to another. Each move is called a step . If the chain is currently in state $s_i$, then it moves to state $s_j$ at the next step with a probability denoted by $p_{ij}$, and this probability does not depend upon which states the chain was in before the current state.These probabilities $p_{ij}$ are called transition probabilities. The process can remain in the state it is in, and this occurs with probability $p_{ii}$ . Initially a probability is defined by specifying a particular state as the starting state.

Say, we stay in Patna (Capital of the State of Bihar, India), and at my home we usually eat either Roti ($\text{Ro}$), Rice ($\text{Ri}$), Parantha ($\text{Pa}$)) or Bread ($\text{Br}$) for dinner. There are also some days when we eat one particular dinner on two or three or more consecutive days.

Now, we define transition probabilities of using a Transition Matrix which is given as,
$$\text{T}=\begin{array}{c c} & \begin{array}{c c c} \text{Ri} & \text{Ro} & \text{Pa} & \text{Br} \\ \end{array} \\ \begin{array}{c c c} \text{Ri} \\ \text{Ro} \\ \text{Pa} \\ \text{Br}\\ \end{array} & \left[ \begin{array}{c c c} \frac{1}{2} & \frac{1}{4} & \frac{1}{4} & 0 \\ 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{2} \\ 0 & \frac{1}{2} & \frac{1}{4} & \frac{1}{4} \\ \frac{1}{2} & 0 & \frac{1}{4} & \frac{1}{4} \\ \end{array} \right] \end{array}$$
From the above matrix, it can be seen that $P_{(Rice \implies Rice)}=\frac{1}{2}$ and similarly, $P_{(Roti \implies Parantha)}=\frac{1}{4}$.

In the similar lines of the above concept, a Transition Diagram can also be drawn.

Let us dig further into the concept now. Imagine today we eat Rice at home and two days from today we eat Bread. This is written as $P^{2}_{(Rice \implies Bread)}$. We see that if we ate Rice today then the event of us eating Bread two days from today is a disjoint union of the following,

1. We ate Rice tomorrow and Bread day after.
2. We ate something else tomorrow and Bread day after.
3. We ate Bread tomorrow and Bread day after.

Therefore, we can write $P^{2}_{(Rice \implies Bread)}$ as ,
$$P^{2}_{(Rice \implies Bread)} = [P_{(Rice \implies Rice)}]\cdot[P_{(Rice \implies Bread)}]+[P_{(Rice \implies Roti)}]\cdot[P_{(Roti \implies Bread)}]+ \\ [P_{(Rice \implies Parantha)}]\cdot[P_{(Parantha \implies Bread)}]+[P_{(Rice \implies Bread)}]\cdot[P_{(Bread \implies Bread)}]$$
The has pointed towards a more generalized concept of Dot product of two vectors.

Considering there are $r$ states in the Markov chain,
$$P^{2}_{ij}=\sum_{k=1}^{r}P_{ik}P_{kj}$$
This study was for $n=2$ , meaning we are yet to define this in a more generalized manner. Obviously, looking at the present scenario of high-end computing software packages available, this attempt seems to be a waste of efforts, but then knowing the math is always good fun!

Before doing that, we will again go into the basic definition as defined above and try to make an iterative approach into the problem.

We have assumed that our meal starts at state Rice, so, for us,
$$\text{p}_0=\begin{bmatrix} 1 \\ 0 \\ 0 \\ 0\\ \end{bmatrix}$$
$\text{p}_0$ is the state of our system at $0^{th}$ state or the beginning of the system.

Similarly, if we want to find $\text{p}_1$ we will do it as,
$$\text{p}_1 = \text{T} \cdot \text{p}_0$$
In the similar lines,
$$\boxed{\text{p}_5 = \text{T} \cdot \text{p}_4 = \text{T}^{2} \cdot \text{p}_3 = \text{T}^3 \cdot \text{p}_2 = \text{T}^4 \cdot \text{p}_1 = \text{T}^{5} \cdot \text{p}_0}$$
This means, for generalization’s sake,
$$\text{p}_n = \text{T}^{n}\cdot \text{p}_0$$
Using some very basic Linear Algebra methods to compute $\text{T}^n$,

Recall : $\text{T}=\mathcal{u}\cdot D \cdot\mathcal{u}^{-1}$

Here, $D$ is a Diagonal matrix and $\mathcal{u}$ is a matrix whose columns correspond to the Eigen-vectors of $\text{T}$.

I leave the computation to your own practice.

There for,
$$\text{T}^n = \mathcal{u} \cdot D^n . \mathcal{u}^{-1}$$
Since, $D$ is a diagonal matrix, which is obviously of form,
$$D = \begin{bmatrix} a & 0 & 0 & 0 \\ 0 & b & 0 & 0 \\ 0 & 0 & c & 0 \\ 0 & 0 & 0 & d \end{bmatrix}$$
Therefore, $D^n$ will be,
$$D = \begin{bmatrix} a^n & 0 & 0 & 0 \\ 0 & b^n & 0 & 0 \\ 0 & 0 & c^n & 0 \\ 0 & 0 & 0 & d^n \end{bmatrix}$$
Hence, we can easily compute $T^n$.

The Python implementation of this concept is relatively simple once we understand the math behind it.

All the best with that.

Cheers!

Resources:

1. Matrix Diagonalization

2. Eigen Values and Eigen Vectors

3. Markov Chains

4. Markov Chains

Moore-Penrose Pseudoinverse

Generalization of the inverse of a matrix.

I believe, we pay too much attention to implementation, and too less
attention in the study of the concept that is implemented. I have been
on then teams of many Data Science and Machine Learning projects, and
I would always reiterate on one simple idea; that is, “If you do not
know the math, you don’t know it at all.”

This is a piece of philosophy I deeply believe in. With the advent of packages like numpy, matplotlib, scikit-learn etc., implementing a machine learning model with a moderately difficult data set and problem is fairly simple.
The magic then stays in being able to tweak the algorithm and getting something new (or weird) out of the model. And, for you to be capable of doing so, you will have to know the mechanism behind it.
The Moore-Penrose pseudoinverse in the soul of PCA (Principal Component Analysis), one of the most popularly used Dimensionality reduction techniques.

---

How do we define the inverse of a matrix?
Provided that the matrix is a square matrix and non-singular, we simple divide the adjoint of the matrix with its determinant.
Mathematically, for $A_{m \times m}$ and $|A| \neq 0$, the inverse of $A$ is defined as,
$$A^{-1} = \frac{ \text{adj.} A}{|A|} \tag*{(1)}$$

---

Of course, the above method is computationally very expensive. Hence, we can get the inverse of the matrix recursively using the Fadeev-LeVerrier equation ( Read about that in this blog of mine).

---

Now, how do we deal with matrices that are non-square? How do you find the inverse of a matrix that looks like this,
$$B = \begin{bmatrix} x_{11} & x_{13} \\ x_{21} & x_{23}\\ x_{d1} & x_{d3} \end{bmatrix}_{3\times 2}$$
This is where the Generalization of inverse of a matrix happens, named the Moore-Penrose Pseudoinverse.

---

For every $A_{m \times n}$, there exists a pseudoinverse $A^{\dagger}_{n \times m}$. ( $A^\dagger$ is read as “A dagger”).
$A^{\dagger}$ is mathematically defined as,
$$A^{\dagger}=(A^{T}A)^{-1}A^{T} \tag*{(2)}$$
This is dimensionally consistent. Please check and verify.

---

Now, say we have,
$$Q = \begin{bmatrix} 1 \\ 2 \end{bmatrix}$$
It is impossible to find $Q^{-1}$ by the conventional method $(1)$. So, we use the Generalized Inverse at $(2)$.
So,
$$Q^{T} = \begin{bmatrix} 1 && 2 \end{bmatrix}$$
So, $Q^{T}Q$ comes out to be $[5]_{1 \times 1}$. So, $(Q^{T}Q)^{-1}$ comes out to be $\frac{1}{5}$.
Hence,
$$Q^{\dagger}=(Q^{T}Q)^{-1}Q^{T} =\frac{1}{5} \begin{bmatrix} 1 && 2 \end{bmatrix} = \begin{bmatrix} \frac{1}{5} && \frac{2}{5} \end{bmatrix}$$ which is the pseudoinverse or the generalized inverse.

---

For a square matrix (i.e., $m \times m$),
$$A^{\dagger}=A^{-1}$$
In detail,
$$(A^{T}A)^{-1}A^{T}=\frac{\text{adj. A}}{|A|}$$

---

Some properties of the generalized inverse are,
1. $AA^{\dagger}A=A$
2. $A^{\dagger}AA^{\dagger}=A^{\dagger}$
3. $(AA^{\dagger})=AA^{\dagger}$
One important point to remember is, $A^{\dagger}$ always exists and is unique.

---

Cheers!