Mixing Why should a uniform random walk on a graph be rapidly mixing? Why should a Markov chain be rapidly mixing?
Mixing • Why should a uniform random walk on a graph be rapidly mixing? • Why should a Markov chain be rapidly mixing?
Sample Matchings G(V,E matching: MCE Ve1,e2∈M no common vertex input:G(V,E) sampling a uniform random matching in G
Sample Matchings input: G(V,E) matching: M ✓ E 8e1, e2 2 M no common vertex sampling a uniform random matching in G G(V,E)
the Jerrum-Sinclair random walk of matchings at each step:M with probability 1/2,do nothing; pick a uniform random edge e=uveE; ·(个)if none of u,v is matched,add e to M; (if eeM,remove e from M; (>if one of u,v is matched by some e'eM, replace e'by e;
• with probability 1/2, do nothing; • pick a uniform random edge e=uv∊E; • (↑) if none of u, v is matched, add e to M; (↓) if e∊M, remove e from M; (↔) if one of u, v is matched by some e’∊M, replace e’ by e; at each step: M the Jerrum-Sinclair random walk of matchings
Mixing Why should a uniform random walk on a graph be rapidly mixing? Why should a Markov chain be rapidly mixing? initial distribution g the decreasing rate of gpe-
Mixing • Why should a uniform random walk on a graph be rapidly mixing? • Why should a Markov chain be rapidly mixing? kqPt ⇡k1 initial distribution q the decreasing rate of
Spectral Decomposition Spectral Theorem P:symmetric nxn matrix eigenvalues:d≥2≥.≥λn the corresponding eigenvectors v1,v2,...,v are orthonormal m g∈Rm q=>civi where ci=qTvi i=1 qP=∑cP=∑c入 2=1 i=1
Spectral Decomposition P : eigenvalues : symmetric n×n matrix the corresponding eigenvectors v1, v2, ..., vn are orthonormal 1 2 ··· n Spectral Theorem where ci = qT vi = X n i=1 ciivi q = X n i=1 8q 2 R civi n qP = X n i=1 civiP