# 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, {*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.

## 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). 
* 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. 

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