GaeBlogX Arista Networks, Software-Defined Networking

# Markov Chains

2017-06-26
Yanxi Chen

## The Setting

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 Evolution

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 Properties

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 Problem

Given a undirected graph $G=(V,E),\lvert V\rvert=n,\lvert E\rvert=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(\log n)$ 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(\log n)$ 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 $\mathbb{E}[T_{ij}]$, 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\leq n)$

Why $\mathbb{E}[T_{uv}]\leq 2m$?

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

by Markov’s inequality.