Markov Chains

The SettingPermalink

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

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

So the evolution of the system is: X0,X1,X2,⋯,Xt,⋯$X_0,X_1,X_2,\cdots ,X_t,\cdots$ and X0$X_0$ is the initial state.

The system is memoryless: the probability that Xt$X_t$ is in a certain state is determined by the state of Xt−1$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 [p1 p2 ⋯ pn]=π0$[p_1{p}_2\cdots p_n]={\pi }_0$, where pi$p_i$ is the probability of being in state i$i$, ∑pi=1$\sum p_i=1$, and the transition matrix is T$T$, such that:

After t$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 π is called stationary/invariant distribution, which is unique.

1. Let Tij 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),|V|=n,|E|=m, and s,t∈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(logn) 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(n), then this uses O(logn) 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[Tij], where i and j are connected.

We pick a path from i to j: i=i1,i2,i3,⋯,ir=j (r≤n)

Why E[Tuv]≤2m?

So if we set N in the algorithm to be 1000n3, then:

by Markov’s inequality.