Question

What can you say in general about the limiting behavior of a random walk on an even-length cycle compared to that of the lazy random walk?

Answer 1

Random walk on a cycle:-Suppose the underlying graph is a cycle on n vertices. Let us analyze the stationary distribution and convergence of random walk on this graph.

The stationary distribution is the uniform distribution. For convergence, we need to find the second eigenvalue of 1/2 (I + 1/2Cn), where Cn is the adjacency matrix of the cycle on n vertices.

The eigenvalues of 1/2 (I + 1/2Cn) are 1/2 + 1/2λi , where λi are the eigenvalues of 1/2Cn. Let ω be the primitive n-th root of unity. You will show in the assignment that (1,ω^k,ω^2k,…,ω^(n-1)k) for all k, are the eigenvectors of Cn.

Lazy Random Walk:- There is an easy way to fix the above periodicity problem. We introduce a modified version of the original walk, which we call lazy random walk. In a lazy random walk at time t

1. we take a step of the original random walk with probability 1/2,

2. we stay at the current vertex with probability 1/2.

We can show that the above modification breaks the periodicity of the random walk. The transition probabilities are encoded in the following matrix:

W = (W + I)/2 = (I + A · D−1)/2,

where I denotes the identity matrix.

The fact that W and W are not symmetric matrices makes their analysis complicated. We will thus define new matrices.

The normalized walk matrix is defined as N = D−1/2 · W · D1/2 = D−1/2 · A · D−1/2. The normalized lazy walk matrix is defined as N = D−1/2 · W · D1/2 = (I + D−1/2 · A · D−1/2)/2.