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