Inequalities and Markov Chains (BH Chapter 10 & 11)

A Markov Chain is a walk along a discrete **state space** {1, 2, . . . , *M*}. We let $X_t$ denote which element of the state space the walk is on at time *t*. The Markov Chain is the set of random variables denoting where the walk is at all points in time, {*X*0, *X*1, *X*2, . . . }. Each $X_t$ takes on values that are in the state space, so if *X*1 = 3, then at time 1, we are at state 3.

What makes such a sequence of random variables a Markov Chain is the **Markov Property**, which says that if you want to predict where the chain is at at a future time, you only need to use the present state, and not any past information. In other words, the *given the present, the future and past are conditionally independent*.

Mathematically, this says:

$P(X_{n+1} = j | X_0 = i_0, X_1 = i_1, \dots, X_n = i_n) = P(X_{n+1} = j | X_n = i_n)$

In words: Given that my history of states has been $i_0, i_2 \ldots i_n$, the distribution of where my next state will be doesn’t depend on any of that history besides $i_n$, the most recent state.

A state is either recurrent or transient.

If you start at a

**Recurrent State**, then you will always return back to that state at some point in thefuture.

*You can leave, but you’ll always return at some point.*Otherwise you are at a

**Transient State**. There is some probability that once you leave you will never return.*There’s a chance that you’ll leave and never come back*

A state is either periodic or aperiodic.

If you start at a

**Periodic State**of period*k*, then the GCD of all of the possible number steps it would take to return back is*k*(which should be > 1).Otherwise you are at an

**Aperiodic State.**The GCD of all of the possible number of steps it would take to return back is 1.

Element $q_{ij}$ in square transition matrix Q is the probability that the chain goes from state $i$ to state $j$, or more formally:

$q_{ij} = P(X_{n+1} = j | X_n = i)$

To find the probability that the chain goes from state $i$ to state $j$ in $m$ steps, take the (i, j)-th} element of $Q^m$.

$q^{(m)}_{ij} = P(X_{n+m} = j | X_n = i)$

If $X_0$ is distributed according to row-vector PMF $\vec{p}$ (e.g. $p_j = P(X_0 = i_j)$), then the marginal PMF of $X_n$ is $\vec{p}Q^n$.

A chain is **irreducible** if you can get from anywhere to anywhere. An irreducible chain must have all of its states recurrent. A chain is **periodic** if any of its states are periodic, and is **aperiodic** if none of its states are periodic. In an irreducible chain, all states have the same period.

A chain is **reversible** with respect to $\vec{s}$ if $s_iq_{ij} = s_jq_{ji}$ for all $i, j$. A reversible chain running on $\vec{s}$ is indistinguishable whether it is running forwards in time or backwards in time. Examples of reversible chains include random walks on undirected networks, or any chain with $q_{ij} = q_{ji}$, where the Markov chain would be stationary with respect to $\vec{s} = (\frac{1}{M}, \frac{1}{M}, \dots, \frac{1}{M})$.

**Reversibility Condition Implies Stationarity** - If you have a PMF $\vec{s}$ on a Markov chain with transition matrix $Q$, then $s_iq_{ij} = s_jq_{ji}$ for all $i, j$ implies that $s$ is stationary.

Let us say that the vector $\vec{p} = (p_1, p_2, \dots, p_M)$ is a possible and valid PMF of where the Markov Chain is at at a certain time. We will call this vector the stationary distribution, $\vec{s}$, if it satisfies $\vec{s}Q = \vec{s}$.

As a consequence, if $X_t$ has the stationary distribution, then all future $X_{t+1}, X_{t + 2}, \dots$ also has the stationary distribution.

If a Markov Chain is irreducible, then it has a unique stationary distribution. In addition, all entries of this stationary distribution are non-zero (which could have been inferred from the fact that all states are recurrent).

Example: In the Gambler's Ruin problem, which is not irreducible, what ultimately happens to the chain can either be that one's money is always $0$ or always $N$.

If a Markov Chain is irreducible

**and**aperiodic, then it has a unique stationary distribution $\vec{s}$ and the chain*converges*to the stationary distribution. $\lim_{n \to \infty} P(X_n = i) = \vec{s}_i$Example: Imagine a Markov chain which is just a cycle, and hence is periodic. Then, depending on where we start, $P(X_n = i)$ will be either 0 or 1 deterministically, and surely won't converge to the stationary distribution, which is uniform across all nodes in the cycle.

If a Markov Chain is irreducible and aperiodic

**and**the stationary distribution exists**and**is unique, then the expected number of steps to return back to $i$ starting from $i$ is $1/s_i$, where $s_i$ is the long-run probability of a chain being at state $i$. To solve for the stationary distribution, you can solve for $\vec{s}Q = \vec{s}$ or $(Q^T - I)\vec{s}^T = 0$. The stationary distribution is uniform if the columns of $Q$ sum to 1.

**Random Walk on Undirected Network**

If you have a certain number of nodes with undirected edges between them, and a chain can pick any edge uniformly at random and move to another node, then this is a random walk on an undirected network. The stationary distribution can be easily calculated. Let $d_i$ be the degree of the i-th node, meaning the number of edges connected to this node. Then, we have:

$\vec{s}_i = \frac{d_i}{\sum_i d_i}$