Randomized Algorithms (Spring 2010)/Random sampling
Random sampling
Conductance
Recap
Conductance and the mixing time
For many problems, such as card shuffling, the state space is exponentially large, so the estimation of [math]\displaystyle{ \lambda_2 }[/math] becomes very 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.