
Random Walks in Markov Chains: Part II
Data Sciences Course, Jan 2014
Ramesh Hariharan
Rayleigh formulation of the second Eigenvalue
- Consider a reversible Markov chain $P$
Ramesh Hariharan
Rayleigh formulation of the second Eigenvalue
- Consider a reversible Markov chain $P$
- Recall $\pi_i p_{ij}=\pi_j p_{ji}$
- $D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ is symmetric and has the same eigenvalues as $P$
Ramesh Hariharan
Rayleigh formulation of the second Eigenvalue
- Consider a reversible Markov chain $P$
- Recall $\pi_i p_{ij}=\pi_j p_{ji}$
- $D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ is symmetric and has the same eigenvalues as $P$
- Claim:
$$1-\lambda_2 = \inf_{v} v(D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T= \inf_{v} \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}$$
Ramesh Hariharan
Rayleigh formulation of the second Eigenvalue
- Consider a reversible Markov chain $P$
- Recall $\pi_i p_{ij}=\pi_j p_{ji}$
- $D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ is symmetric and has the same eigenvalues as $P$
- Claim:
$$1-\lambda_2 = \inf_{v} v(D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T= \inf_{v} \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}$$
* where the $\inf$ is over all $v$ such that $\sum_i \sqrt{\pi_i}v_i=0$, $\sum_i v^2_i=1 $
Ramesh Hariharan
Rayleigh formulation of the second Eigenvalue
- Consider a reversible Markov chain $P$
- Recall $\pi_i p_{ij}=\pi_j p_{ji}$
- $D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ is symmetric and has the same eigenvalues as $P$
- Claim:
$$1-\lambda_2 = \inf_{v} v(D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T= \inf_{v} \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}$$
* where the $\inf$ is over all $v$ such that $\sum_i \sqrt{\pi_i}v_i=0$, $\sum_i v^2_i=1 $ * Edges are in play now!
Ramesh Hariharan
Proof of the Rayleigh formulation: Using $I-D^{-\frac{1}{2}} P D^{\frac{1}{2}}$
- Recall $D^{-\frac{1}{2}} P D^{\frac{1}{2}}$
- Is symmetric with entries $\sqrt{\frac{\pi_i}{\pi_j}} p_{ij}=\sqrt{\frac{\pi_j}{\pi_i}} p_{ji} $
- Has the same eigenvalues as $P$
Ramesh Hariharan
Proof of the Rayleigh formulation: Using $I-D^{-\frac{1}{2}} P D^{\frac{1}{2}}$
- Recall $D^{-\frac{1}{2}} P D^{\frac{1}{2}}$
- Is symmetric with entries $\sqrt{\frac{\pi_i}{\pi_j}} p_{ij}=\sqrt{\frac{\pi_j}{\pi_i}} p_{ji} $
- Has the same eigenvalues as $P$
- Let the eigenvalues sorted by decreasing absolute value be $1,\lambda_2,\ldots,\lambda_n$, $|\lambda_i|<1$
Ramesh Hariharan
Proof of the Rayleigh formulation: Using $I-D^{-\frac{1}{2}} P D^{\frac{1}{2}}$
- Recall $D^{-\frac{1}{2}} P D^{\frac{1}{2}}$
- Is symmetric with entries $\sqrt{\frac{\pi_i}{\pi_j}} p_{ij}=\sqrt{\frac{\pi_j}{\pi_i}} p_{ji} $
- Has the same eigenvalues as $P$
- Let the eigenvalues sorted by decreasing absolute value be $1,\lambda_2,\ldots,\lambda_n$, $|\lambda_i|<1$
- The eigenvalues of $I-D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ are
- $0, 1-\lambda_2,\ldots, 1-\lambda_n$
- All are non-negative $\implies$ Sym. positive semi-definite
Ramesh Hariharan
Proof of the Rayleigh formulation: +-ve Semi-definiteness
- $I-D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ can be written as $B^TB$
Ramesh Hariharan
Proof of the Rayleigh formulation: +-ve Semi-definiteness
- $I-D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ can be written as $B^TB$
- $B$ has size $|E|*|M|$
Ramesh Hariharan
Proof of the Rayleigh formulation: +-ve Semi-definiteness
- $I-D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ can be written as $B^TB$
- $B$ has size $|E|*|M|$
- For $e=(i,j)\in E$ (note: undirected, no self loops)
- $B_{ei}= \sqrt{ p_{ij}}$
- $B_{ej}= -\sqrt{ p_{ji}}$
Ramesh Hariharan
Proof of the Rayleigh formulation: +-ve Semi-definiteness
- $I-D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ can be written as $B^TB$
- $B$ has size $|E|*|M|$
- For $e=(i,j)\in E$ (note: undirected, no self loops)
- $B_{ei}= \sqrt{ p_{ij}}$
- $B_{ej}= -\sqrt{ p_{ji}}$
- $(B^TB)_{ij}=\left\{\begin{array} \ - \sqrt{p_{ij}p_{ji}}= -\sqrt{\frac{\pi_j}{\pi_i}} p_{ji} = -\sqrt{\frac{\pi_i}{\pi_j}} p_{ij} & \mbox{ if } i\not=j \\ \sum_k p_{ik}=1-p_{ii} & \mbox{ if } i=j \end{array}\right\}$
Ramesh Hariharan
Proof of the Rayleigh formulation
- $D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ has same eigenvalues as $P$
Ramesh Hariharan
Proof of the Rayleigh formulation
- $D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ has same eigenvalues as $P$
- Eigenvector of $(D^{-\frac{1}{2}} P D^{\frac{1}{2}})$ corresponding to eigenvalue 1 is $v_i=\sqrt{\pi_i}$
Ramesh Hariharan
Proof of the Rayleigh formulation
- $D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ has same eigenvalues as $P$
- Eigenvector of $(D^{-\frac{1}{2}} P D^{\frac{1}{2}})$ corresponding to eigenvalue 1 is $v_i=\sqrt{\pi_i}$
- Let the eigenvalues in decreasing order be $1,\lambda_2,\ldots,\lambda_M$, $|\lambda_i|<1$
Ramesh Hariharan
Proof of the Rayleigh formulation
- $D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ has same eigenvalues as $P$
- Eigenvector of $(D^{-\frac{1}{2}} P D^{\frac{1}{2}})$ corresponding to eigenvalue 1 is $v_i=\sqrt{\pi_i}$
- Let the eigenvalues in decreasing order be $1,\lambda_2,\ldots,\lambda_M$, $|\lambda_i|<1$
- $|\lambda_2|>|\lambda_M|$, assuming self-loops have been added to $P$, i.e., $P=\frac{P'+I}{2}$
Ramesh Hariharan
Proof of the Rayleigh formulation
- $D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ has same eigenvalues as $P$
- Eigenvector of $(D^{-\frac{1}{2}} P D^{\frac{1}{2}})$ corresponding to eigenvalue 1 is $v_i=\sqrt{\pi_i}$
- Let the eigenvalues in decreasing order be $1,\lambda_2,\ldots,\lambda_M$, $|\lambda_i|<1$
- $|\lambda_2|>|\lambda_M|$, assuming self-loops have been added to $P$, i.e., $P=\frac{P'+I}{2}$
- Because $\lambda_i(P)=\frac{\lambda_i(P')+1}{2}>0$
Ramesh Hariharan
Proof of the Rayleigh formulation
- $D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ has same eigenvalues as $P$
- Eigenvector of $(D^{-\frac{1}{2}} P D^{\frac{1}{2}})$ corresponding to eigenvalue 1 is $v_i=\sqrt{\pi_i}$
- Let the eigenvalues in decreasing order be $1,\lambda_2,\ldots,\lambda_M$, $|\lambda_i|<1$
- $|\lambda_2|>|\lambda_M|$, assuming self-loops have been added to $P$, i.e., $P=\frac{P'+I}{2}$
- Because $\lambda_i(P)=\frac{\lambda_i(P')+1}{2}>0$
- I.e., $\lambda_i$'s are positive
Ramesh Hariharan
Proof of the Rayleigh formulation
- $D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ has same eigenvalues as $P$
- Eigenvector of $(D^{-\frac{1}{2}} P D^{\frac{1}{2}})$ corresponding to eigenvalue 1 is $v_i=\sqrt{\pi_i}$
- Let the eigenvalues in decreasing order be $1,\lambda_2,\ldots,\lambda_M$, $|\lambda_i|<1$
- $|\lambda_2|>|\lambda_M|$, assuming self-loops have been added to $P$, i.e., $P=\frac{P'+I}{2}$
- Because $\lambda_i(P)=\frac{\lambda_i(P')+1}{2}>0$
- I.e., $\lambda_i$'s are positive
- $\lambda_2=\sup_v v(D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T$
- over all $v$ such that $\sum_i \sqrt{\pi_i}v_i=0$ and $\sum_i v^2_i=1$
Ramesh Hariharan
Proof of the Rayleigh formulation
- It follows that
- $1-\lambda_2= \inf_v v(I-D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T$, where $\sum_i \sqrt{\pi_i}v_i=0$, $\sum_i v^2_i=1$
Ramesh Hariharan
Proof of the Rayleigh formulation
- It follows that
- $1-\lambda_2= \inf_v v(I-D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T$, where $\sum_i \sqrt{\pi_i}v_i=0$, $\sum_i v^2_i=1$
- Next: $v(I-D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T$
Ramesh Hariharan
Proof of the Rayleigh formulation
- It follows that
- $1-\lambda_2= \inf_v v(I-D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T$, where $\sum_i \sqrt{\pi_i}v_i=0$, $\sum_i v^2_i=1$
- Next: $v(I-D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T$
- $= {vB^TBv^T}= \inf_v {(vB^T) (vB^T)^T}$
Ramesh Hariharan
Proof of the Rayleigh formulation
- It follows that
- $1-\lambda_2= \inf_v v(I-D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T$, where $\sum_i \sqrt{\pi_i}v_i=0$, $\sum_i v^2_i=1$
- Next: $v(I-D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T$
- $= {vB^TBv^T}= \inf_v {(vB^T) (vB^T)^T}$
- $= {\sum_{e=(i,j)\in E} (v_i\sqrt{p_{ij}}-v_j\sqrt{p_{ji}})^2 }$
Ramesh Hariharan
Proof of the Rayleigh formulation
- It follows that
- $1-\lambda_2= \inf_v v(I-D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T$, where $\sum_i \sqrt{\pi_i}v_i=0$, $\sum_i v^2_i=1$
- Next: $v(I-D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T$
- $= {vB^TBv^T}= \inf_v {(vB^T) (vB^T)^T}$
- $= {\sum_{e=(i,j)\in E} (v_i\sqrt{p_{ij}}-v_j\sqrt{p_{ji}})^2 }$
- $= \sum_{e=(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}\frac{v_j}{\sqrt{\pi_j}})^2 \pi_i p_{ij}$
Ramesh Hariharan
Proof of the Rayleigh formulation
- It follows that
- $1-\lambda_2= \inf_v v(I-D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T$, where $\sum_i \sqrt{\pi_i}v_i=0$, $\sum_i v^2_i=1$
- Next: $v(I-D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T$
- $= {vB^TBv^T}= \inf_v {(vB^T) (vB^T)^T}$
- $= {\sum_{e=(i,j)\in E} (v_i\sqrt{p_{ij}}-v_j\sqrt{p_{ji}})^2 }$
- $= \sum_{e=(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}\frac{v_j}{\sqrt{\pi_j}})^2 \pi_i p_{ij}$
- Therefore
$1-\lambda_2 = \inf_{v} v(D^{-\frac{1}{2}} P D^{\frac{1}{2}})v^T= \inf_{v} \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}$
- over $v$ such that $\sum_i \sqrt{\pi_i}v_i=0$, $\sum_i v^2_i=1$
Ramesh Hariharan
A More Combinatorial Quantity
- Consider a subset of states $S$
Ramesh Hariharan
A More Combinatorial Quantity
- Consider a subset of states $S$
- Given one is in $S$, with what probability does one exit $S$ on the next move?
Ramesh Hariharan
A More Combinatorial Quantity
- Consider a subset of states $S$
- Given one is in $S$, with what probability does one exit $S$ on the next move?
- $\sum_{i\in S} \left(\frac{\pi_i}{\pi(S)}\sum_{j\in V-S} p_{ij}\right)$, where $\pi(S)=\sum_{i\in S} \pi_i$ and $\pi(V-S)=\sum_{i\in V-S} \pi_i$
Ramesh Hariharan
A More Combinatorial Quantity
- Consider a subset of states $S$
- Given one is in $S$, with what probability does one exit $S$ on the next move?
- $\sum_{i\in S} \left(\frac{\pi_i}{\pi(S)}\sum_{j\in V-S} p_{ij}\right)$, where $\pi(S)=\sum_{i\in S} \pi_i$ and $\pi(V-S)=\sum_{i\in V-S} \pi_i$
- If $\pi(S)$ is not too large, then the above probability should be large for rapid mixing
Ramesh Hariharan
A More Combinatorial Quantity
- Consider a subset of states $S$
- Given one is in $S$, with what probability does one exit $S$ on the next move?
- $\sum_{i\in S} \left(\frac{\pi_i}{\pi(S)}\sum_{j\in V-S} p_{ij}\right)$, where $\pi(S)=\sum_{i\in S} \pi_i$ and $\pi(V-S)=\sum_{i\in V-S} \pi_i$
- If $\pi(S)$ is not too large, then the above probability should be large for rapid mixing
- i.e., Conductance $\Phi=\frac{\sum_{e \in C} \pi_i p_{ij}}{{\pi(S)}}$ should be large, where $C$ is the set of edges between $S$ and $V-S$
Ramesh Hariharan
A More Combinatorial Quantity
- Consider a subset of states $S$
- Given one is in $S$, with what probability does one exit $S$ on the next move?
- $\sum_{i\in S} \left(\frac{\pi_i}{\pi(S)}\sum_{j\in V-S} p_{ij}\right)$, where $\pi(S)=\sum_{i\in S} \pi_i$ and $\pi(V-S)=\sum_{i\in V-S} \pi_i$
- If $\pi(S)$ is not too large, then the above probability should be large for rapid mixing
- i.e., Conductance $\Phi=\frac{\sum_{e \in C} \pi_i p_{ij}}{{\pi(S)}}$ should be large, where $C$ is the set of edges between $S$ and $V-S$
- for symmetry, use $\Phi=\frac{\sum_{e \in C} \pi_i p_{ij}}{{\pi(S)\pi(V-S)}}$ instead
Ramesh Hariharan
$ 1-\lambda_2\leq \Phi$
- Consider a cut $C=(S,V-S)$ which realizes the conductance $\Phi=\frac{\sum_{e \in C} \pi_i p_{ij}}{{\pi(S)\pi(V-S)}}$
Ramesh Hariharan
$ 1-\lambda_2\leq \Phi$
- Consider a cut $C=(S,V-S)$ which realizes the conductance $\Phi=\frac{\sum_{e \in C} \pi_i p_{ij}}{{\pi(S)\pi(V-S)}}$
- $\pi(S)=\sum_{i\in S} \pi_i$ and $\pi(V-S)=\sum_{i\in V-S} \pi_i$
Ramesh Hariharan
$ 1-\lambda_2\leq \Phi$
- Consider a cut $C=(S,V-S)$ which realizes the conductance $\Phi=\frac{\sum_{e \in C} \pi_i p_{ij}}{{\pi(S)\pi(V-S)}}$
- $\pi(S)=\sum_{i\in S} \pi_i$ and $\pi(V-S)=\sum_{i\in V-S} \pi_i$
- Consider any vector $v$ so $\sum_i \sqrt{\pi_i}v_i=0$, $\sum_i v_i^2=1$
Ramesh Hariharan
$ 1-\lambda_2\leq \Phi$
- Consider a cut $C=(S,V-S)$ which realizes the conductance $\Phi=\frac{\sum_{e \in C} \pi_i p_{ij}}{{\pi(S)\pi(V-S)}}$
- $\pi(S)=\sum_{i\in S} \pi_i$ and $\pi(V-S)=\sum_{i\in V-S} \pi_i$
- Consider any vector $v$ so $\sum_i \sqrt{\pi_i}v_i=0$, $\sum_i v_i^2=1$
- $ 1-\lambda_2 \leq \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}$
Ramesh Hariharan
$ 1-\lambda_2\leq \Phi$
- Consider a cut $C=(S,V-S)$ which realizes the conductance $\Phi=\frac{\sum_{e \in C} \pi_i p_{ij}}{{\pi(S)\pi(V-S)}}$
- $\pi(S)=\sum_{i\in S} \pi_i$ and $\pi(V-S)=\sum_{i\in V-S} \pi_i$
- Consider any vector $v$ so $\sum_i \sqrt{\pi_i}v_i=0$, $\sum_i v_i^2=1$
- $ 1-\lambda_2 \leq \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}$
- Set $v_i=+\sqrt{\pi_i\frac{\pi(S)}{\pi(V-S)}}$ if $i\in V-S$ and $v_i=-\sqrt{\pi_i\frac{\pi(V-S)}{\pi(S)}}$ if $i\in S$
Ramesh Hariharan
$ 1-\lambda_2\leq \Phi$
- Consider a cut $C=(S,V-S)$ which realizes the conductance $\Phi=\frac{\sum_{e \in C} \pi_i p_{ij}}{{\pi(S)\pi(V-S)}}$
- $\pi(S)=\sum_{i\in S} \pi_i$ and $\pi(V-S)=\sum_{i\in V-S} \pi_i$
- Consider any vector $v$ so $\sum_i \sqrt{\pi_i}v_i=0$, $\sum_i v_i^2=1$
- $ 1-\lambda_2 \leq \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}$
- Set $v_i=+\sqrt{\pi_i\frac{\pi(S)}{\pi(V-S)}}$ if $i\in V-S$ and $v_i=-\sqrt{\pi_i\frac{\pi(V-S)}{\pi(S)}}$ if $i\in S$
- $ 1-\lambda_2\\ \leq \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij} =\frac{\sum_{e \in C} \pi_i p_{ij}}{{\pi(S)\pi(V-S)}} = \Phi $
Ramesh Hariharan
$1-\lambda_2\geq \frac{\Phi^2}{32}$ (Jerrum-Sinclair or Cheeger's Thm)
- Consider $v$ for which $ 1-\lambda_2= \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}$
Ramesh Hariharan
$1-\lambda_2\geq \frac{\Phi^2}{32}$ (Jerrum-Sinclair or Cheeger's Thm)
- Consider $v$ for which $ 1-\lambda_2= \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}$
- Change norms using Cauchy-Schwartz:
- $\sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij} \geq \frac{(\sum_{(i,j)\in E}|\frac{v_i^2}{{\pi_i}}-\frac{v^2_j}{{\pi_j}}|\pi_i p_{ij})^2}{\sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}+\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij} }$
Ramesh Hariharan
$1-\lambda_2\geq \frac{\Phi^2}{32}$ (Jerrum-Sinclair or Cheeger's Thm)
- Consider $v$ for which $ 1-\lambda_2= \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}$
- Change norms using Cauchy-Schwartz:
- $\sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij} \geq \frac{(\sum_{(i,j)\in E}|\frac{v_i^2}{{\pi_i}}-\frac{v^2_j}{{\pi_j}}|\pi_i p_{ij})^2}{\sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}+\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij} }$
- Refine denominator using Jensen's:
- $ \frac{(\sum_{(i,j)\in E}|\frac{v_i^2}{{\pi_i}}-\frac{v^2_j}{{\pi_j}}|\pi_i p_{ij})^2}{\sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}+\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij} }\geq \frac{(\sum_{(i,j)\in E}|\frac{v_i^2}{{\pi_i}}-\frac{v^2_j}{{\pi_j}})|\pi_i p_{ij})^2}{2\sum_{(i,j)\in E} (\frac{v_i^2}{{\pi_i}}+\frac{v_j^2}{{\pi_j}})\pi_i p_{ij} }\geq \frac{(\sum_{(i,j)\in E}|\frac{v_i^2}{{\pi_i}}-\frac{v^2_j}{{\pi_j}})|\pi_i p_{ij})^2}{2\sum_i v_i^2 }$
Ramesh Hariharan
$1-\lambda_2\geq \frac{\Phi^2}{16}$

- $ \sum_{(i,j)\in E} |\frac{v^2_i}{{\pi_i}}-\frac{v^2_j}{{\pi_j}}|\pi_i p_{ij}$
Ramesh Hariharan
$1-\lambda_2\geq \frac{\Phi^2}{16}$

- $ \sum_{(i,j)\in E} |\frac{v^2_i}{{\pi_i}}-\frac{v^2_j}{{\pi_j}}|\pi_i p_{ij}$
- $\geq \Phi \sum_{i} (\frac{v^2_{i+1}}{{\pi_{i+1}}}-\frac{v^2_i}{{\pi_i}}) {\pi({\leq i}) \pi({\geq i+1})}$
Ramesh Hariharan
$1-\lambda_2\geq \frac{\Phi^2}{16}$

- $ \sum_{(i,j)\in E} |\frac{v^2_i}{{\pi_i}}-\frac{v^2_j}{{\pi_j}}|\pi_i p_{ij}$
- $\geq \Phi \sum_{i} (\frac{v^2_{i+1}}{{\pi_{i+1}}}-\frac{v^2_i}{{\pi_i}}) {\pi({\leq i}) \pi({\geq i+1})}$
- $\geq \frac{\Phi}{{2}} \sum_{i} (\frac{v^2_{i+1}}{{\pi_{i+1}}}-\frac{v^2_i}{{\pi_i}}) \min\{{\pi({\leq i})}, {\pi({\geq i+1})}\}$
Ramesh Hariharan
$1-\lambda_2\geq \frac{\Phi^2}{16}$
- $ \sum_{(i,j)\in E} |\frac{v^2_i}{{\pi_i}}-\frac{v^2_j}{{\pi_j}}|\pi_i p_{ij}\\ \geq \Phi \sum_{i} (\frac{v^2_{i+1}}{{\pi_{i+1}}}-\frac{v^2_i}{{\pi_i}}) {\pi({\leq i}) \pi({\geq i+1})} \\ \geq \frac{\Phi}{{2}} \sum_{i} (\frac{v^2_{i+1}}{{\pi_{i+1}}}-\frac{v^2_i}{{\pi_i}}) \min\{{\pi({\leq i})}, {\pi({\geq i+1})}\} \\ \geq \frac{\Phi}{{2}} (\sum_{i\in R} \frac{v^2_{i}\pi_i}{{\pi_{i}}}- \sum_{i\in L} \frac{v^2_{i}\pi_i}{{\pi_{i}}})$


Ramesh Hariharan
$1-\lambda_2\geq \frac{\Phi^2}{16}$
- Summarizing $ 1-\lambda_2= \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}\geq \frac{\frac{\Phi^2}{{4}} (\sum_{i\in R} {v^2_{i}}- \sum_{i\in L} {v^2_{i}})^2}{2\sum_i v_i^2 }$
Ramesh Hariharan
$1-\lambda_2\geq \frac{\Phi^2}{16}$
- Summarizing $ 1-\lambda_2= \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}\geq \frac{\frac{\Phi^2}{{4}} (\sum_{i\in R} {v^2_{i}}- \sum_{i\in L} {v^2_{i}})^2}{2\sum_i v_i^2 }$
- Modify the $v_i$'s so one of the numerator terms disappears
- Change the order: consider $\frac{v_i}{\sqrt{\pi_i}}$ in increasing order
Ramesh Hariharan
$1-\lambda_2\geq \frac{\Phi^2}{16}$
- Summarizing $ 1-\lambda_2= \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}\geq \frac{\frac{\Phi^2}{{4}} (\sum_{i\in R} {v^2_{i}}- \sum_{i\in L} {v^2_{i}})^2}{2\sum_i v_i^2 }$
- Modify the $v_i$'s so one of the numerator terms disappears
- Change the order: consider $\frac{v_i}{\sqrt{\pi_i}}$ in increasing order
- Let $k$ be such that $\sum_{i < k} \pi_i < \frac{1}{2}$, $\sum_{i > k} \pi_i < \frac{1}{2}$
Ramesh Hariharan
$1-\lambda_2\geq \frac{\Phi^2}{16}$
- Summarizing $ 1-\lambda_2= \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}\geq \frac{\frac{\Phi^2}{{4}} (\sum_{i\in R} {v^2_{i}}- \sum_{i\in L} {v^2_{i}})^2}{2\sum_i v_i^2 }$
- Modify the $v_i$'s so one of the numerator terms disappears
- Change the order: consider $\frac{v_i}{\sqrt{\pi_i}}$ in increasing order
- Let $k$ be such that $\sum_{i < k} \pi_i < \frac{1}{2}$, $\sum_{i > k} \pi_i < \frac{1}{2}$
- Consider $\frac{z_i}{\sqrt{\pi_i}}=\max\{\frac{v_i}{\sqrt{\pi_i}}-\frac{v_k}{\sqrt{\pi_k}},0 \}$
Ramesh Hariharan
$1-\lambda_2\geq \frac{\Phi^2}{16}$
- Summarizing $ 1-\lambda_2= \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}\geq \frac{\frac{\Phi^2}{{4}} (\sum_{i\in R} {v^2_{i}}- \sum_{i\in L} {v^2_{i}})^2}{2\sum_i v_i^2 }$
- Modify the $v_i$'s so one of the numerator terms disappears
- Change the order: consider $\frac{v_i}{\sqrt{\pi_i}}$ in increasing order
- Let $k$ be such that $\sum_{i < k} \pi_i < \frac{1}{2}$, $\sum_{i > k} \pi_i < \frac{1}{2}$
- Consider $\frac{z_i}{\sqrt{\pi_i}}=\max\{\frac{v_i}{\sqrt{\pi_i}}-\frac{v_k}{\sqrt{\pi_k}},0 \}$
- $ 1-\lambda_2\geq \sum_{(i,j)\in E} (\frac{z_i}{\sqrt{\pi_i}}-\frac{z_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}\geq \frac{\frac{\Phi^2}{{4}} \left(\sum_{i\in R} {z^2_{i}}\right)^2}{2\sum_{i\in R} z_i^2 }\geq \frac{\Phi^2}{8} \sum_{i\in R} {z^2_{i}} $
Ramesh Hariharan
$1-\lambda_2\geq \frac{\Phi^2}{16}$
- Summarizing $ 1-\lambda_2= \sum_{(i,j)\in E} (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}\geq \frac{\frac{\Phi^2}{{4}} (\sum_{i\in R} {v^2_{i}}- \sum_{i\in L} {v^2_{i}})^2}{2\sum_i v_i^2 }$
- Modify the $v_i$'s so one of the numerator terms disappears
- Change the order: consider $\frac{v_i}{\sqrt{\pi_i}}$ in increasing order
- Let $k$ be such that $\sum_{i < k} \pi_i < \frac{1}{2}$, $\sum_{i > k} \pi_i < \frac{1}{2}$
- Consider $\frac{z_i}{\sqrt{\pi_i}}=\max\{\frac{v_i}{\sqrt{\pi_i}}-\frac{v_k}{\sqrt{\pi_k}},0 \}$
- $ 1-\lambda_2\geq \sum_{(i,j)\in E} (\frac{z_i}{\sqrt{\pi_i}}-\frac{z_j}{\sqrt{\pi_j}})^2\pi_i p_{ij}\geq \frac{\frac{\Phi^2}{{4}} \left(\sum_{i\in R} {z^2_{i}}\right)^2}{2\sum_{i\in R} z_i^2 }\geq \frac{\Phi^2}{8} \sum_{i\in R} {z^2_{i}} $
- $\sum_{i\in R} z_i^2=\sum_i \pi_i \max\{\frac{v_i}{\sqrt{\pi_i}}-\frac{v_k}{\sqrt{\pi_k}},0 \}^2 \geq \frac{1}{2}\sum_i \pi_i (\frac{v_i}{\sqrt{\pi_i}}-\frac{v_k}{\sqrt{\pi_k}})^2\geq \frac{1}{2}$
Ramesh Hariharan
Using Conductance: Line Graph Example
- Consider a straight line $0\ldots M-1$
Ramesh Hariharan
Using Conductance: Line Graph Example
- Consider a straight line $0\ldots M-1$
- $X_{t+1}=\left\{\begin{array} \ X_t+1 & w.p \frac{1}{2} \mbox{ if } X_t\not=M-1\\ X_t-1 & w.p \frac{1}{2} \mbox{ if } X_t\not=0\\ X_t & w.p \frac{1}{2} \mbox{ if } X_t=0,M-1 \\ \end{array}\right\}$
Ramesh Hariharan
Using Conductance: Line Graph Example
- Consider a straight line $0\ldots M-1$
- $X_{t+1}=\left\{\begin{array} \ X_t+1 & w.p \frac{1}{2} \mbox{ if } X_t\not=M-1\\ X_t-1 & w.p \frac{1}{2} \mbox{ if } X_t\not=0\\ X_t & w.p \frac{1}{2} \mbox{ if } X_t=0,M-1 \\ \end{array}\right\}$
- $\pi_i = \frac{1}{M}$ because $p_{ij}=p_{ji}$
Ramesh Hariharan
Using Conductance: Line Graph Example
- Consider a straight line $0\ldots M-1$
- $X_{t+1}=\left\{\begin{array} \ X_t+1 & w.p \frac{1}{2} \mbox{ if } X_t\not=M-1\\ X_t-1 & w.p \frac{1}{2} \mbox{ if } X_t\not=0\\ X_t & w.p \frac{1}{2} \mbox{ if } X_t=0,M-1 \\ \end{array}\right\}$
- $\pi_i = \frac{1}{M}$ because $p_{ij}=p_{ji}$
- Conductance $\Phi\geq \frac{2}{M}$
Ramesh Hariharan
Using Conductance: Line Graph Example
- Consider a straight line $0\ldots M-1$
- $X_{t+1}=\left\{\begin{array} \ X_t+1 & w.p \frac{1}{2} \mbox{ if } X_t\not=M-1\\ X_t-1 & w.p \frac{1}{2} \mbox{ if } X_t\not=0\\ X_t & w.p \frac{1}{2} \mbox{ if } X_t=0,M-1 \\ \end{array}\right\}$
- $\pi_i = \frac{1}{M}$ because $p_{ij}=p_{ji}$
- Conductance $\Phi\geq \frac{2}{M}$
- So mixing time
$$\frac{\log(\frac{\sqrt{M}}{\sqrt{2}\epsilon\} )}{1-\lambda_2}\leq \frac{\log(\frac{\sqrt{M}}{\sqrt{2}\epsilon\} )}{1/(4M^2)}\leq 4M^2 \log \frac{M}{\sqrt{2}\epsilon}$$
Ramesh Hariharan
Using Conductance: Complete Graph Example
- Consider a complete undirected graph with vertices $0\ldots M-1$
Ramesh Hariharan
Using Conductance: Complete Graph Example
- Consider a complete undirected graph with vertices $0\ldots M-1$
- $X_{t+1}= \begin{array} \ i & w.p \frac{1}{M} \mbox{ for } i\in 0\ldots M-1 \end{array}$
Ramesh Hariharan
Using Conductance: Complete Graph Example
- Consider a complete undirected graph with vertices $0\ldots M-1$
- $X_{t+1}= \begin{array} \ i & w.p \frac{1}{M} \mbox{ for } i\in 0\ldots M-1 \end{array}$
- $\pi_i = \frac{1}{M}$ because $p_{ij}=p_{ji}$
Ramesh Hariharan
Using Conductance: Complete Graph Example
- Consider a complete undirected graph with vertices $0\ldots M-1$
- $X_{t+1}= \begin{array} \ i & w.p \frac{1}{M} \mbox{ for } i\in 0\ldots M-1 \end{array}$
- $\pi_i = \frac{1}{M}$ because $p_{ij}=p_{ji}$
- Conductance $\Phi=1$
Ramesh Hariharan
Using Conductance: Complete Graph Example
- Consider a complete undirected graph with vertices $0\ldots M-1$
- $X_{t+1}= \begin{array} \ i & w.p \frac{1}{M} \mbox{ for } i\in 0\ldots M-1 \end{array}$
- $\pi_i = \frac{1}{M}$ because $p_{ij}=p_{ji}$
- Conductance $\Phi=1$
- So mixing time
$$\frac{\log(\frac{\sqrt{M}}{\sqrt{2}\epsilon\} )}{1-\lambda_2}\leq \frac{\log(\frac{\sqrt{M}}{\sqrt{2}\epsilon\} )}{1/(16)}\leq 16 \log \frac{\sqrt{M}}{\sqrt{2}\epsilon}$$
Ramesh Hariharan
Using Conductance: Complete Graph Example
- Consider a complete undirected graph with vertices $0\ldots M-1$
- $X_{t+1}= \begin{array} \ i & w.p \frac{1}{M} \mbox{ for } i\in 0\ldots M-1 \end{array}$
- $\pi_i = \frac{1}{M}$ because $p_{ij}=p_{ji}$
- Conductance $\Phi=1$
- So mixing time
$$\frac{\log(\frac{\sqrt{M}}{\sqrt{2}\epsilon\} )}{1-\lambda_2}\leq \frac{\log(\frac{\sqrt{M}}{\sqrt{2}\epsilon\} )}{1/(16)}\leq 16 \log \frac{\sqrt{M}}{\sqrt{2}\epsilon}$$
- Note $\lambda_2=0$, so actual mixing time is 1!
Ramesh Hariharan
A Certificate for Conductance: Inspired by Menger's Theorem
- And if there are $k$ edge-disjoint paths between $u$ and $v$, the min-cut separating $u$ and $v$ has size at least $k$
Ramesh Hariharan
A Certificate for Conductance: Inspired by Menger's Theorem
And if there are $k$ edge-disjoint paths between $u$ and $v$, the min-cut separating $u$ and $v$ has size at least $k$
If the min-cut separating $u,v$ has at least $k$ edges then there must be at least $k$ edge-disjoint paths between $u$ and $v$
Ramesh Hariharan
A Certificate for Conductance: Canonical Paths
- Suppose we can find
Ramesh Hariharan
A Certificate for Conductance: Canonical Paths
- Suppose we can find
- For every pair of vertices $u,v$, a path from $u$ to $v$ with weight $\pi_u\pi_v$, such that
Ramesh Hariharan
A Certificate for Conductance: Canonical Paths
- Suppose we can find
- For every pair of vertices $u,v$, a path from $u$ to $v$ with weight $\pi_u\pi_v$, such that
- The total weight of paths going through any given edge $e=(i,j)$ is at most $C *\pi_i p_{ij}$, where $C$ denotes Congestion
Ramesh Hariharan
A Certificate for Conductance: Canonical Paths
- Suppose we can find
- For every pair of vertices $u,v$, a path from $u$ to $v$ with weight $\pi_u\pi_v$, such that
- The total weight of paths going through any given edge $e=(i,j)$ is at most $C *\pi_i p_{ij}$, where $C$ denotes Congestion
- Then $\Phi \geq \frac{1}{C}$
Ramesh Hariharan
Conductance and Canonical Path Congestion: Proof
- Consider any cut $(S,V-S)$
Ramesh Hariharan
Conductance and Canonical Path Congestion: Proof
- Consider any cut $(S,V-S)$
- The total weight of all paths from $S$ to $V-S$ is $\pi(S) \pi(V-S)$
Ramesh Hariharan
Conductance and Canonical Path Congestion: Proof
- Consider any cut $(S,V-S)$
- The total weight of all paths from $S$ to $V-S$ is $\pi(S) \pi(V-S)$
- The total weight carried by an edge $e=(ij)$ crossing the cut is at most $C*\pi_i p_{ij}$
Ramesh Hariharan
Conductance and Canonical Path Congestion: Proof
- Consider any cut $(S,V-S)$
- The total weight of all paths from $S$ to $V-S$ is $\pi(S) \pi(V-S)$
- The total weight carried by an edge $e=(ij)$ crossing the cut is at most $C*\pi_i p_{ij}$
- So $C \sum_{i\in S, j\in V-S} \pi_i p_{ij} \geq \pi(S) \pi(V-S)$
Ramesh Hariharan
Conductance and Canonical Path Congestion: Proof
- Consider any cut $(S,V-S)$
- The total weight of all paths from $S$ to $V-S$ is $\pi(S) \pi(V-S)$
- The total weight carried by an edge $e=(ij)$ crossing the cut is at most $C*\pi_i p_{ij}$
- So $C \sum_{i\in S, j\in V-S} \pi_i p_{ij} \geq \pi(S) \pi(V-S)$
- So $\Phi \geq \frac{1}{C}$
Ramesh Hariharan
Using Canonical Paths: The Hypercube Example
- States tuples $(x_1,\ldots,x_d)$, $x_i=0/1$
Ramesh Hariharan
Using Canonical Paths: The Hypercube Example
- States tuples $(x_1,\ldots,x_d)$, $x_i=0/1$
- Prob $\frac{1}{2}$ self, otherwise pick one of the $d$ bits u.a.r and flip
Ramesh Hariharan
Using Canonical Paths: The Hypercube Example
- States tuples $(x_1,\ldots,x_d)$, $x_i=0/1$
- Prob $\frac{1}{2}$ self, otherwise pick one of the $d$ bits u.a.r and flip
- Symmetric, so uniform stationary distribution $1/2^d$
Ramesh Hariharan
Using Canonical Paths: The Hypercube Example
- States tuples $(x_1,\ldots,x_d)$, $x_i=0/1$
- Prob $\frac{1}{2}$ self, otherwise pick one of the $d$ bits u.a.r and flip
- Symmetric, so uniform stationary distribution $1/2^d$
- Canonical Paths: Flip bits as needed in order from left to right
Ramesh Hariharan
Using Canonical Paths: The Hypercube Example
- States tuples $(x_1,\ldots,x_d)$, $x_i=0/1$
- Prob $\frac{1}{2}$ self, otherwise pick one of the $d$ bits u.a.r and flip
- Symmetric, so uniform stationary distribution $1/2^d$
- Canonical Paths: Flip bits as needed in order from left to right
- Paths via $(a_1,\ldots, a_{i-1},x,a_{i+1},\ldots,a_d)- (a_1,\ldots, a_{i-1},y,a_{i+1},\ldots,a_d)$?
- Between $(*,\ldots,*,x,a_{i+1},\ldots,a_{d}) \leftrightarrow (a_1,\ldots, a_{i-1},y,*,\ldots,*)$
- $2*2^{d-1}$ such paths
- $\left(C=\frac{2^d/2^{2d}}{1/(2d\cdot 2^{d})}=2d \right) \Rightarrow k=\frac{\log(\frac{\sqrt{M}}{\sqrt{2}\epsilon} )}{1-\lambda_2}\leq \frac{\log(\frac{\sqrt{M}}{\sqrt{2}\epsilon} )}{1/(32C^2)}= 128 d^2 \log \frac{\sqrt{M}}{\sqrt{2}\epsilon}$
Ramesh Hariharan
Exercises
- Prove using coupling that a random walk on the hypercube converges in $O(d\log d)$ time.
- Prove using conductance a random walk on a $n*n$ grid converges in time $O(n^2\log n)$
- Prove that a random walk on a $n*n*\cdots *n$ d-dim lattice grid converges in time $O(d^3 n^2\log n)$
- Prove that any Markov Chain in which the gcd of all cycle lengths is 1 is aperiodic, i.e., $\lim_{k\rightarrow 0} vP^k=\pi$
Ramesh Hariharan
The Metropolis Algorithm
- Consider a multidimensional prob. distribution $\cal D:$ $(x_1,\ldots,x_d)\rightarrow p$
Ramesh Hariharan
The Metropolis Algorithm
- Consider a multidimensional prob. distribution $\cal D:$ $(x_1,\ldots,x_d)\rightarrow p$
- States of the chain: all $d$ tuples
Ramesh Hariharan
The Metropolis Algorithm
- Consider a multidimensional prob. distribution $\cal D:$ $(x_1,\ldots,x_d)\rightarrow p$
- States of the chain: all $d$ tuples
- Design transitions so stationary distribution is $\cal D$
Ramesh Hariharan
The Metropolis Algorithm
- Consider a multidimensional prob. distribution $\cal D:$ $(x_1,\ldots,x_d)\rightarrow p$
- States of the chain: all $d$ tuples
- Design transitions so stationary distribution is $\cal D$
- $a=(x_1,\ldots,x_{i-1},y,x_{i+1},\ldots,x_d),b=(x_1,\ldots,x_{i-1},z,x_{i+1},\ldots,x_d)$
Ramesh Hariharan
The Metropolis Algorithm
- Consider a multidimensional prob. distribution $\cal D:$ $(x_1,\ldots,x_d)\rightarrow p$
- States of the chain: all $d$ tuples
- Design transitions so stationary distribution is $\cal D$
- $a=(x_1,\ldots,x_{i-1},y,x_{i+1},\ldots,x_d),b=(x_1,\ldots,x_{i-1},z,x_{i+1},\ldots,x_d)$
- $p_{ab}= \frac{1}{d} \min \{ 1 , \frac{p(x_i=z|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)}{p(x_i=y|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)} \}$
Ramesh Hariharan
The Metropolis Algorithm
- Consider a multidimensional prob. distribution $\cal D:$ $(x_1,\ldots,x_d)\rightarrow p$
- States of the chain: all $d$ tuples
- Design transitions so stationary distribution is $\cal D$
- $a=(x_1,\ldots,x_{i-1},y,x_{i+1},\ldots,x_d),b=(x_1,\ldots,x_{i-1},z,x_{i+1},\ldots,x_d)$
- $p_{ab}= \frac{1}{d} \min \{ 1 , \frac{p(x_i=z|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)}{p(x_i=y|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)} \}$
- $p(a) p_{ab}= p(x_1,\ldots,x_{i-1},y,x_{i+1},\ldots, x_d) \frac{1}{d}\min \{ 1 , \frac{p(x_i=z|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)}{p(x_i=y|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)} \}$
Ramesh Hariharan
The Metropolis Algorithm
- Consider a multidimensional prob. distribution $\cal D:$ $(x_1,\ldots,x_d)\rightarrow p$
- States of the chain: all $d$ tuples
- Design transitions so stationary distribution is $\cal D$
- $a=(x_1,\ldots,x_{i-1},y,x_{i+1},\ldots,x_d),b=(x_1,\ldots,x_{i-1},z,x_{i+1},\ldots,x_d)$
- $p_{ab}= \frac{1}{d} \min \{ 1 , \frac{p(x_i=z|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)}{p(x_i=y|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)} \}$
- $p(a) p_{ab}= p(x_1,\ldots,x_{i-1},y,x_{i+1},\ldots, x_d) \frac{1}{d}\min \{ 1 , \frac{p(x_i=z|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)}{p(x_i=y|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)} \}$
- WLOG, $= p(x_1,\ldots,x_{i-1},y,x_{i+1},\ldots, x_d) \frac{1}{d} \frac{p(x_i=z|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)}{p(x_i=y|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)}$
Ramesh Hariharan
The Metropolis Algorithm
- Consider a multidimensional prob. distribution $\cal D:$ $(x_1,\ldots,x_d)\rightarrow p$
- States of the chain: all $d$ tuples
- Design transitions so stationary distribution is $\cal D$
- $a=(x_1,\ldots,x_{i-1},y,x_{i+1},\ldots,x_d),b=(x_1,\ldots,x_{i-1},z,x_{i+1},\ldots,x_d)$
- $p_{ab}= \frac{1}{d} \min \{ 1 , \frac{p(x_i=z|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)}{p(x_i=y|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)} \}$
- $p(a) p_{ab}= p(x_1,\ldots,x_{i-1},y,x_{i+1},\ldots, x_d) \frac{1}{d}\min \{ 1 , \frac{p(x_i=z|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)}{p(x_i=y|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)} \}$
- WLOG, $= p(x_1,\ldots,x_{i-1},y,x_{i+1},\ldots, x_d) \frac{1}{d} \frac{p(x_i=z|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)}{p(x_i=y|x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_d)}$
- $= \frac{1}{d} p(x_1,\ldots, x_{i-1},z, x_{i+1},\ldots, x_d) = p(b) p_{ba}$ (recall detailed balance)
Ramesh Hariharan
Ramesh Hariharan