Markov Chain

Description:

• A Memoryless Variable Stochastic Process
• Like a Successor Function of a Stochastic Process
• Suppose whenever the process is in state $i$, there is a fixed probability $P_{ij}$ that will take it from state $i$ to state $j$. .
  • That is $P\{X_{n+1}=j|X_n=i,X_{n-1}=i_{n-1},...,X_1=i_1,X_0=i_0\}=P_{ij}$ for all states and $n\ge 0$
  • Meaning $P_{ij}=P(X_{n+1}=j|X_n=i)$
• The future state only concern with the current state, it is independent from the past states
  • Must hold true for any possible state
• $\sum _{j=1}{P}_{ij}=1$

As a matrix:

• Represented with a Matrix of one-step each with probability $P_{ij}$
  • ex: $\left[\begin{array}{ccc}{P}_{00}& P_{01}& ...\\ P_{10}& P_{11}& ...\\ ...& ...& ...\end{array}\right]=\left[\begin{array}{ccc}{P}_{0\to 0}& P_{0\to 1}& ...\\ P_{1\to 0}& P_{1\to 1}& ...\\ ...& ...& ...\end{array}\right]$
  • Sum of a row is always $1$ as 1 state must have an outcome
• Should be $n\times n$ square matrix with $n$ possible state

Transforming a process to a Markov Chain:

• If a future state depends on the last 2 states, combine the last two states into 1 combined state → more nb of states
• However, the nb of states as result must be the same, so we need to combine with the current (or more before if needed)
• ex: Rain yesterday, rain today to predict raining tomorrow
  • X00: rain ytd + rain today
  • X01: rain ytd + rain today
  • …
  • so the resulting X00 becomes rain today + rain tomorrow → X 00-00 = P(rain+rain+rain)

Chapman-Kolmogorov Equation

State in Markov Chain

Reducing Markov chain:

• Irreducible:
  • means there is only 1 class (1 state can move to every other states)
• Reducible meaning?

Long-run Proportion of Markov Chain

Limiting probability:

• ${\alpha }_j=\underset{n\to \infty }{\lim }P(X_n=j)$ which is equal to Long-run Proportion of Markov Chain if exist
  • $1=\sum _{i=0}^{\infty }{\alpha }_i$
  • such chains that have limiting probability, $\alpha$, is called Ergodic Markov Chain
  • When $n$ is large, the matrix converges and its called Ergodic Markov Chain, Stationary Markov Chain, Stationary Ergodic markov chain
• Therefore for big steps, state of any given step doesnt depend on the intial step
• except for Periodic Markov Chain
  • ex: $P=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$, as $P^{\infty }$ doesnt converge to a long-run proportion for each state
  • Does thave limiting probability
  • Can only return to a state in an exact $d>1$ steps
    • in this case, 2 steps
  • State at any steps depends on the first state

Some applications:

• Gambler’s Ruin Problem
• A Model for Algorithmic Efficiency

Time Reversible Markov Chain

• Consider an Ergodic Markov Chain having transition probabilities Pij and stationary probabilities ${\pi }_i$
  • A reversible Markov chain is like having a “time machine” for this little world. It considers the process to be “fair” in both directions.
• We trace the sequence of states going backward in time, that is, starting at time $n$, consider the sequence of states $X_n,X_{n-1},X_{n-2},...$
• This sequence of states is itself a Markov chain with transition probabilities $Q_{ij}$ defined by $Q_{ij}=P\{X_m=j|Xm+1=i\}=\frac{{\pi }_j{P}_{ji}}{{\pi }_i}$
  • Opposite of $P_{ij}$
• The reverse process is also a Markov Chain
• Markov chain is time reversible if $Q_{ij}=P_{ij}$ for all $i,j$
  • Equivalently ${\pi }_j{P}_{ij}={\pi }_i{P}_{ji}$ for all $i,j$
  • for all states $i$ and $j$, the rate at which the process goes from $i$ to $j$ $({\pi }_i{P}_{ij})$ is equal to the rate at which it goes from $j$ to $i$ $({\pi }_j{P}_{ji})$
• We can model undirected connected graph with time reversible markov chain:
  • If at any time the particle resides at node $i$, then it will next move to node $j$ with probability $P_{ij}$ where $P_{ij}=\frac{w_{ij}}{{\sum }_j{w}_{ij}}$
    • where $w_{ij}$ is 1 if there is an arc, 0 otherwise
    • meaning probability from $i$ to $j$ is 1/number of arc connected from i
  • Using ${\pi }_i{P}_{ji}={\pi }_j{P}_{ij}=>{\pi }_i\frac{w_{ij}}{{\sum }_j{w}_{ij}}={\pi }_j\frac{w_{ji}}{{\sum }_i{w}_{ji}}$ combining with $w_{ij}=w_{ji}$ and ${\sum }_i{\pi }_i=1$
    • we have ${\pi }_i=\frac{{\sum }_j{w}_{ij}}{{\sum }_i{\sum }_j{w}_{ij}}$
• theorem A Stationary Markov Chain for which $P_{ij}=0$ whenever $P_{ji}=0$ is time reversible if and only if starting in state $i$, any path back to $i$ has the same probability as the reversed path.
  • That is, if $P_{i,i1}{P}_{i1,i2}...P_{ik,i}=P_{i,ik}{P}_{ik,ik-1}...P_{i2,i}$ for all state $i,i1,...,ik$
• Consider an irreducible Markov chain with transition probabilities $P_{ij}$ .
  • If we can find positive numbers ${\pi }_i,i\ge 0$, summing to one, and a transition probability matrix $Q=[Q_{ij}]$ such that ${\pi }_i{P}_{ij}={\pi }_j{Q}_{ji}$
  • then the $Q_{ij}$ are the transition probabilities of the reversed chain and the ${\pi }_i$ are the stationary probabilities both for the original and reversed chain
    • ie. double time reversed MC

---