Markov Chains

Definition (Markov Process)

A Stochastic Process is a set $\{X_n{\}}_{n=0}^{\infty }$ is a Markov Process if

$$\mathbb{P}(X_{n+1}=i_{n+1}|X_0=i_0,\dots ,X_n=i_n)=\mathbb{P}(X_{n+1}=i_{n+1}|X_n=i_n)$$

$\forall n\ge 0,\forall i_0,\dots i_{n+1}\in S$. In particular, it means if $(n+1)$th step only depends on the previous step.

A Markov Process is time homogeneous if

$$\mathbb{P}(X_{n+1}=j|X_n=i)=\mathbb{P}(X_1=j|X_0=i)$$

$\forall n\ge 0,\forall i_j\in S$. So the probability of going from state $i$ to $j$ does not depend on the time.

Definition (Transition Probability)

The transition probability of jumping between states is

$$p(i,j)=\mathbb{P}(X_1=j|X_0=i)=\mathbb{P}(i\to j)$$

for all $i,j\in S$. This allows us to put these relationships into a matrix.

$$P=\left[\begin{array}{c}p(i,j)\end{array}\right]$$

for $i,j\in S$. Here, $i,j$ are states with row/column labels.

Definition (Joint Distribution for Markov Processes)

The Joint Distribution is for any $n\ge 1,i_0,\dots ,i_n\in S$ we have

$$\begin{array}{rl}\mathbb{P}(X_0=i_0,\dots ,X_n=i_n)& =\mathbb{P}(X_0=i_0)\prod _{k=1}^n\mathbb{P}(X_k=i_k|X_0=i_0,\dots ,X_{k-1}=i_{k-1})\\ & =\mathbb{P}(X_0=i_0)\prod _{k=1}^n\mathbb{P}(X_k=i_k|X_{k-1}=i_{k-1})\\ & =P(X_0=i_0)\prod _{k=1}^{n}p(i_{k-1},i_k)\end{array}$$

by the chain rule, Markov Property, and time homogeneity in that order. Visually, this is a path through a graph. The probability of this path is the product of the edges crossed.

Example 1 (Transition Matrix)

Let $X_0,X_1,\dots X_n\in S$ be iid. Then $\{X_n{\}}_{n=0}^{\infty }$ is a time homogeneous Markov Chain. Let $S=\{1,2,\dots ,N\}$. Then $p(i,j)=\mathbb{P}(X_1=j|X_0=i)=\mathbb{P}(X_1=j)=p_j$. This means our transition matrix is

$$P=\left[\begin{array}{cccc}{p}_1& p_2& \dots & p_N\\ p_1& p_2& \dots & p_N\\ ⋮& ⋮& \ddots & ⋮\\ p_1& p_2& \dots & p_N\end{array}\right],\sum _{i=1}^N{p}_i=1$$

The sum of a column must be equal to $1$. This corresponds to every edge out of a node summing to $1$.

Example 3 (1D Random Walk)

Consider a random walk on a number line from $0\to 1\to 2\to \cdots \to N-1\to N$. Then

$$X_n\in S=\{0,1,\dots ,N\}$$

for $N=0,1,2,\dots$ and $X_n$ at $i$ for $0<i<N$. We jump right at probability $p$ and left with probability $1-p$. We can model this with a Markov Chain where jumping from $i\to i+1$ is probability $p$ and $i\to i-1$ as $1-p$.

Definition (Stochastic Matrix)

A square matrix $P=[p_{ij}]$ is a stochastic matrix if all $p_{ij}\ge 0$ and ${\sum }_i{p}_{ij}=1$ for all $i$. All rows sum to $1$. For a discrete state time homogeneous Markov Chain,

$$X_n\in S=\{0,1,\dots \},n\ge 0$$

with transition matrix $P$, the $n-$step transition probabilities are

$$\begin{array}{rl}{p}_n& =\mathbb{P}(X_{n+k}=j|X_k=i)\\ & =\mathbb{P}(X_n=j|X_0=i)\end{array}$$

and $n$-step transition matrix is

$$P_n=[p_n(i,j)]$$

e.g.

• $P_0=I,p_0(i,j)={\delta }_{ij}$
• $P_1=p,p_1(i,j)=p(i,j)$ where ${\delta }_{ij}$ is the Kronecker Delta.

Definition (Distribution Vector)

The distribution vector ${\pi }_n$ for $X_n$ is

$${\vec{\pi }}_n=\left[{\pi }_n(0),{\pi }_n(1),\dots ,\right]$$

where ${\pi }_n(i)=\mathbb{P}(X_n=i)$ for $i\in S$.

Proposition (Stochastic Properties)

Let $X_n\in S=\{0,1,2,\dots \}$ for $n\ge 0$ be a time homogeneous Markov Chain with transition matrix $P$. Then

1. $P$ is a Stochastic Matrix
2. $P1=1$ is an Eigenvalue of $P$ with eigenvector $1$. In particular, $$1=\left(\begin{array}{c}1\\ 1\\ ⋮\\ 1\end{array}\right)$$
3. $p_{m+n}=p_m\cdot p_n$ (Chapman-Kolmgorov Equality)
4. ${\pi }_n={\pi }_0\cdot p_n={\pi }_0{p}^n$ and ${\pi }_{n+1}={\pi }_n\cdot p$ for all $n\ge 0$.