# 随机算法 (Fall 2011)/Random Walks on Undirected Graphs

Jump to: navigation, search

A walk on a graph ${\displaystyle G=(V,E)}$ is a sequence of vertices ${\displaystyle v_{1},v_{2},\ldots \in V}$ such that ${\displaystyle v_{i+1}}$ is a neighbor of ${\displaystyle v_{i}}$ for every index ${\displaystyle i}$. When ${\displaystyle v_{i+1}}$ is selected uniformly at random from among ${\displaystyle v_{i}}$’s neighbors, independently for every ${\displaystyle i}$, this is called a random walk on ${\displaystyle G}$.

We consider the special case that ${\displaystyle G(V,E)}$ is an undirected graph, and denote that ${\displaystyle n=|V|}$ and ${\displaystyle m=|E|}$.

A Markov chain is defined by this random walk, with the vertex set ${\displaystyle V}$ as the state space, and the transition matrix ${\displaystyle P}$, which is defined as follows:

${\displaystyle P(u,v)={\begin{cases}{\frac {1}{d(u)}}&{\mbox{if }}(u,v)\in E,\\0&{\mbox{otherwise }},\end{cases}}}$

where ${\displaystyle d(u)}$ denotes the degree of vertex ${\displaystyle u}$.

Note that unlike the PageRank example, now the probability depends on ${\displaystyle d(u)}$ instead of ${\displaystyle d_{+}(u)}$. This is because the graph is undirected.

 Proposition Let ${\displaystyle M_{G}}$ be the Markov chain defined as above. ${\displaystyle M_{G}}$ is irreducible if and only if ${\displaystyle G}$ is connected. ${\displaystyle M_{G}}$ is aperiodic if and only if ${\displaystyle G}$ is non-bipartite.

We leave the proof as an exercise.

We can just assume ${\displaystyle G}$ is connected, so we do not have to worry about the reducibility any more.

The periodicity of a random walk on a undirected bipartite graph is usually dealt with by the following trick of "lazy" random walk.

Lazy random walk
Given an undirected graph ${\displaystyle G(V,E)}$, a random walk is defined by the transition matrix
${\displaystyle P'(u,v)={\begin{cases}{\frac {1}{2}}&{\mbox{if }}u=v,\\{\frac {1}{2d(u)}}&{\mbox{if }}(u,v)\in E,\\0&{\mbox{otherwise }}.\end{cases}}}$
For this random walk, at each step, we first flip a fair coin to decide whether to move or to stay, and if the coin told us to move, we pick a uniform edge and move to the adjacent vertex. It is easy to see that the resulting Markov chain is aperiodic for any ${\displaystyle G}$.

We consider the non-lazy version of random walk. We observe that the random walk has the following stationary distribution.

 Theorem The random walk on ${\displaystyle G(V,E)}$ with ${\displaystyle |E|=m}$ has a stationary distribution ${\displaystyle \pi }$, where ${\displaystyle \forall v\in V}$, {\displaystyle {\begin{aligned}\pi _{v}={\frac {d(v)}{2m}}\end{aligned}}} for ${\displaystyle v\in V}$.
Proof.
 First, since ${\displaystyle \sum _{v\in V}d(v)=2m}$, it follows that ${\displaystyle \sum _{v\in V}\pi _{v}=\sum _{v\in V}{\frac {d(v)}{2m}}=1,}$ thus ${\displaystyle \pi }$ is a well-defined distribution. And let ${\displaystyle N(v)}$ denote the set of neighbors of ${\displaystyle v}$. Then for any ${\displaystyle v\in V}$, ${\displaystyle (\pi P)_{v}=\sum _{u\in V}\pi _{u}P(u,v)=\sum _{u\in N(v)}{\frac {d(u)}{2m}}{\frac {1}{d(u)}}={\frac {1}{2m}}\sum _{u\in N(v)}1={\frac {d(v)}{2m}}=\pi _{v}.}$ Thus ${\displaystyle \pi P=\pi }$, and ${\displaystyle \pi }$ is stationary.
${\displaystyle \square }$

For connected and non-bipartite ${\displaystyle G}$, the random walk converges to this stationary distribution. Note that the stationary distribution is proportional to the degrees of the vertices, therefore, if ${\displaystyle G}$ is a regular graph, that is, ${\displaystyle d(v)}$ is the same for all ${\displaystyle v\in V}$, the stationary distribution is the uniform distribution.

The following parameters of random walks are closely related to the performances of randomized algorithms based on random walks:

• Hitting time: It takes how long for a random walk to visit some specific vertex.
• Cover time: It takes how long for a random walk to visit all vertices.
• Mixing time: It takes how long for a random walk to be close enough to the stationary distribution.