Markov Chain

def. Markov Chain. A Stochastic Process $\{X_t{\}}_{t=0,1,2,\dots }$ where:

• $X_t$ has finite or infinite states $=0,1,\dots$
• $\mathcal{L}(X_{n+1})$ only depends on $\mathcal{L}(X_{n+1})$, i.e. is memoryless
• $\mathbb{P}(X_{n+1}=j|X_n=i)=P_{ij}$ where $P$ is a matrix that contains all transition probabilities, the transition matrix:

$$\mathbf{P}=\left[\begin{array}{cccc}{P}_{00}& P_{01}& P_{02}& \cdots \\ P_{10}& P_{11}& P_{12}& \cdots \\ ⋮& ⋮& ⋮& \ddots \\ P_{i0}& P_{i1}& P_{i2}& \cdots \\ ⋮& ⋮& ⋮& \ddots \end{array}\right]$$

• Row sums are always 1, since total probability exiting a state should add to 1
• Absorbing States

thm. Chapman-Kolmogorov Eq. Given Markov chain $\{X_t{\}}_{t=0,1,2,\dots }$ and transition probability matrix $P$, the transition probability from state $i$ to $j$ in $n$ steps is denoted $P_{ij}^n$ and for all $i,j$ in matrix $P^n$, the n-step transition matrix. This is calculated as:

$$P_{ij}^{n+m}=\sum _{\forall k\in \text{states}}{P}_{ik}^n{P}_{kj}^m$$

Absorbing States §

def. Absorbing State is a state $i$ where once entered, it is never left. Motivation. Calculation of the probability that, from an initial state, the process will ever enter a certain state is a common question yet difficult to calculate. The following formalizes this type of problem and offers a concise solution. Consider a Markov chain $\{X_n{\}}_{n=0,1,\dots }$, initial state $i$, transition matrix $P$. let $\mathcal{A}\subset \text{states}$ and we want to know if $X$ ever enters any states $\mathcal{A}$ within $m$ transition steps. This is:

$$\begin{array}{rl}& \mathbb{P}(\exists k\le m,X_k\in \mathcal{A}|X_0=i)\\ & =\mathbb{P}(\bigcup _{k=1}^m\{X_k\in A\}|X_0=i)\\ & =\mathbb{P}(\bigcup _{k=1}^m[\bigcap _{j=1}^{k-1}\{X_k\notin \mathcal{A}\}]|X_0=i)\end{array}$$

which is a pain in the ass to calculate. Instead, we construct a new Markov chain $\{W_n{\}}_{n=0,1,\dots }$, transition matrix $Q$ with states ${\mathcal{A}}^C\cup \{A\ast \}$ which $A^{\ast }$ is an absorbing state. $Q$ is constructed accordingly to model this absorption, in the following way:

• $Q_{ij}=P_{ij}$ for all $i,j\notin \mathcal{A}$
• $Q_{i{A}^{\ast }}={\sum }_{j\in \mathcal{A}}{P}_{ij}$, obviously only for $i\notin \mathcal{A}$
• $Q_{AA}=1$ since it’s an absorbing state Then the original probability is

$$\begin{array}{r}\mathbb{P}(\exists k\le m,X_k\in \mathcal{A}|X_0=i)=P(W_m=A^{\ast }|W_0=i)=Q_{i{A}^{\ast }}^m\end{array}$$

Classification of States §

def. Accessible. From state $i$ state $j$ is accessible iff:

$$\exists n\ge 0,P_{ij}^n>0$$

def. Communication & Class. State $i$ and $j$ communicate iff $i$ accesses $j$ and vice versa. Properties:

• Identity. $i$ communicates with itself
• Commutative. if $i$ comm. with $j$, and $j$ with $k$, then $i$ comms. with $k$. Proof:

$$P_{ik}^{n+m}:=\sum _{\forall r\in \text{states}}{P}_{ir}^n{P}_{rk}^m\ge \stackrel{\text{ since i,j and j,k communicates }}{\overbrace{P_{ij}^n{P}_{jk}^m>0}}$$

def. Irreducible Markov Chain. A markov chain that contains only one class. We also see below, irreducible markov chain has one recurrent class. def. Recurrence and Transience. Initial state $i$. Let $f_i=\mathbb{P}({\bigcup }_{k=1}^{\infty }\{X_k=i\}|X_0=i)$, i.e. that we will ever visit state $i$ again (indefinitely) State $i$ is:

• recurrent if $f_i=1$, will visit again
• transient if $f_i<1$, will probably never visit again thm. Determiniation of Recurrence. State $i$ is:
• recurrent if ${\sum }_{n=1}^{\infty }{P}_{ii}^n<\infty$ Converges
• transient if ${\sum }_{n=1}^{\infty }{P}_{ii}^n=\infty$ Diverges Proof. See (Proof) Markov Recurrence by Sum Divergence. This leads to following corollaries that are pretty self-evident.

1. thm. Finite state markov chains always contain a recurrent state.
   • …but infinite state markov chains may have no recurrent states
2. thm. Recurrence/transience is a class property. If state $i,j$ comm., and $i$ is recurrent, so is $j$.
3. thm. Irreducible markov chains have one recurrent class that contains all states. def. Positive/Null Recurrent. let state $i$, and $T=\min \{X_T=i\mid X_0=i\}$, the expected time of return. Then $i$:

$$\mathbb{E}[T]=\{\begin{array}{ll}<\infty & \text{Positive-Recurrent}\\ =\infty & \text{Null-Recurrent}\end{array}$$

Intuition. Null recurrence is an odd variety. It means the process will definitely eventually return to $i$, but you have to wait infinitely long(!).

• thm. A Markov Chain does not have a stationary distribution iff it is null recurrent
• thm. In a finite-state markov chain, all recurrent states are positive recurrent. def. Periodic/Aperiodic. A state $i$ is periodic with period $d>1$ iff:

1. $P_{ii}^n=0$ for all $n$ not a multiple of $d$
2. $d=\max \{d:d\text{ divides }n\}$, the largest of such numbers

• If $d=1$, the state is aperiodic.
• thm. Periodicity is a class property.

Stationary Distribution §

Motivation. In certain Markov chains, as we run the process for a large number of steps, the fraction of time spent in every state $i$s approaches some enumber. This is equally the transition matrix at infinite number of transitions.

$$\underset{n\to \infty }{\lim }{P}^n$$

• def. Ergodic state. A state that is positive-recurrent, aperiodic.
• def. Ergodic Markov Chain is a markov chain with only ergodic states. Since ergodicity is naturally also a class property, we consider irreducible ergodic MCs, i.e. chains that “go in cycles”, will return in a finite amount of time, and has only one “cycle group”. thm. Stationary Distribution. For an ergodic markov chain there exists the limit:

$$\underset{n\to \infty }{\lim }{P}^n=\left[\begin{array}{cccc}{\pi }_1& {\pi }_2& \cdots & {\pi }_n\\ ⋮& ⋮& \ddots & ⋮\\ {\pi }_1& {\pi }_2& \cdots & {\pi }_n\end{array}\right]=\left[\begin{array}{c}{\pi }_1,{\pi }_2,\dots ,{\pi }_n\end{array}\right]$$

Notice first that each column has just one limiting value. Thus we index $\pi$ with just one index, the destination. ${\pi }_j$ for each column is the unique non-negative solution to:

$$\begin{array}{rlr}{\pi }_j& =\sum _{i=0}^{\infty }{\pi }_i{P}_{ij},& j\ge 0\\ 1& =\sum _{j=0}^{\infty }{\pi }_j& \text{is a distribution}\end{array}$$

• thm. If MC is (just) irreducible then there always exists such a solution iff MC is positive recurrent
  • If solution exists i.e. MC is pos-rec, solution will be unique
  • If MC is aperiodic as well, ${\pi }_j$ is then the limiting probability.