Randomized Algorithms (Spring 2010)/Random sampling
Conductance and the mixing time
We see how the mixing time of a reversible Markov chain is related to [math]\displaystyle{ \lambda_\max }[/math]. But how to compute [math]\displaystyle{ \lambda_\max }[/math] of a Markov chain? There are two levels of complications:
- Is [math]\displaystyle{ \lambda_\max=|\lambda_2| }[/math] or [math]\displaystyle{ \lambda_\max=|\lambda_n| }[/math]?
- This is rather easy to solve, by considering lazy walks. For a time-reversion Markov chain with transition matrix [math]\displaystyle{ P }[/math], we can make a lazy random walk out of it by letting [math]\displaystyle{ Q=\frac{1}{2}(I+P) }[/math] be the new transition matrix. It is easy to see that [math]\displaystyle{ Q }[/math] is also time-reversible and has the same stationary distribution. A lovely property of [math]\displaystyle{ Q }[/math] is that it always has [math]\displaystyle{ \lambda_\max=\lambda_2 }[/math], which is easy to check. Therefore, from now on, we only consider lazy random walks and always assume that [math]\displaystyle{ \lambda_\max=\lambda_2 }[/math].
- Another complication is that [math]\displaystyle{ \lambda_2 }[/math] is hard to estimate. For many problems, such as card shuffling, the state space is exponentially large, so the estimation of [math]\displaystyle{ \lambda_2 }[/math] becomes especially hard.
- This problem is quite difficult. The following technique based on conductance is due to Jerrum and Sinclair, which is fundamental for the theory of rapid mixing random walks.
Definition (conductance)
|
The definition of conductance looks quite similar to the expansion ratio of graphs. In fact, for the random walk on a undirected [math]\displaystyle{ d }[/math]-regular graph [math]\displaystyle{ G }[/math], there is a straightforward relation between the conductance [math]\displaystyle{ \Phi }[/math] of the walk and the expansion ratio [math]\displaystyle{ \phi(G) }[/math] of the graph
- [math]\displaystyle{ \Phi=\frac{\phi(G)}{d}. }[/math]
Very informally, the conductance can be seen as the weighted normalized version of expansion ratio.
The following theorem states a Cheeger's inequality for the conductance.
Theorem (Jerrum-Sinclair 1988)
|
The inequality can be equivalent written for the spectral gap:
- [math]\displaystyle{ \frac{\Phi^2}{2}\le1-\lambda_2\le 2\Phi }[/math]
thus a large conductance implies a large spectral gap, which in turn implies the rapid mixing of the random walk.
We will see in the next class, how to argue about the conductance.