Markov Chains

The SettingPermalink

There is a system with $n$ possible states/values. At each step, the state changes probabilistically.

Let $X_t$ be the state of the system at time $t$

So the evolution of the system is: $X_0,X_1,X_2,\cdots ,X_t,\cdots$ and $X_0$ is the initial state.

The system is memoryless: the probability that $X_t$ is in a certain state is determined by the state of $X_{t-1}$:

For simplicity, we assume that:

• Finite number of states
• The underlying graph is strongly connected: for any two states, there is a path from 1 to 2 and a path from 2 to 1

Mathematical Representation of the EvolutionPermalink

In general, if the initial probabilistic state is $[p_1{p}_2\cdots p_n]={\pi }_0$, where $p_i$ is the probability of being in state $i$, $\sum p_i=1$, and the transition matrix is $T$, such that:

After $t$ more steps, the probabilistic state is:

And the probability of bing in state $i$ after $t$ steps is:

Some PropertiesPermalink

1. Suppose the Markov chain is “aperiodic”, then as the system evolves, the probabilistic state converges to a limiting probabilistic state:

So the resulting $\pi$ is called stationary/invariant distribution, which is unique.

1. Let $T_{ij}$ be the time of reaching state $j$ when you start at state $i$, then:

This is known as the Mean Recurrence Theorem.

Example: The Connectivity ProblemPermalink

Given a undirected graph $G=(V,E),\left|V\right|=n,\left|E\right|=m$, and $s,t\in V$, check if there is a path from $s$ to $t$.

It is easy to do in polynomial time with BFS or DFS, but how about using only $O\left(\log n\right)$ space?

Here is a possible randomized algorithm:

v = s
for k = 1,2,...,N:
    v = random-neighbor(v)
    if v == t, return YES
return NO

For $N=poly\left(n\right)$, then this uses $O\left(\log n\right)$ space.

But what is the success probability? If $s$ and $t$ are disconnected, we give the correct answer.

What if $s$ and $t$ are connected?

If we have a graph $A$ represented by the following adjacency matrix, and we start at any vertex and randomly walk to a neighbor, how does the transition matrix look like?

The stationary distribution is:

So

What we care is really $E\left[T_{ij}\right]$, where $i$ and $j$ are connected.

We pick a path from $i$ to $j$: $i=i_1,i_2,i_3,\cdots ,i_r=j(r\le n)$

Why $E\left[T_{uv}\right]\le 2m$?

So if we set N in the algorithm to be $1000n^3$, then:

by Markov’s inequality.