---
description: Inequalities and Markov Chains (BH Chapter 10 & 11)
---

# Section 10

## Statistical Inequalities

## Markov Chains

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, {_&#x58;_&#x30;, _&#x58;_&#x31;, _&#x58;_&#x32;, . . . }. Each $$X_t$$ takes on values that are in the state space, so if _&#x58;_&#x31; = 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.

## State Properties

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 the

    future. _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).&#x20;
* 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.&#x20;

## Transition Matrix

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$$.

## Chain Properties

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.

## Stationary Distribution

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$$.&#x20;
* 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}$$
