# Fullscreen View

The author recommends viewing the raindrop in fullsceen.
×

# Raindrop Info

Title:
Random Walks in Markov Chains: Part II
Authors:
Created:
2014-Mar-02
Updated:
2015-Jul-17
Views:
851
Pages:
88
Likes:
5
×

# Copy the link below to embed!

×
1

Random Walks in Markov Chains: Part II
Data Sciences Course, Jan 2014

Ramesh Hariharan

2

Rayleigh formulation of the second Eigenvalue

• Consider a reversible Markov chain $P$

Ramesh Hariharan

3

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

4

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

5

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

6

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

7

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

8

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

9

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

10

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

11

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

12

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

13

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

14

Proof of the Rayleigh formulation

• $D^{-\frac{1}{2}} P D^{\frac{1}{2}}$ has same eigenvalues as $P$

Ramesh Hariharan

15

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

16

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

17

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

18

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

19

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

20

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

21

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

22

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

23

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

24

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

25

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

26

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

27

A More Combinatorial Quantity

• Consider a subset of states $S$

Ramesh Hariharan

28

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

29

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

30

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

31

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

32

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

33

$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

34

$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

35

$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

36

$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

37

$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

38

$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

39

$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

40

$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

41

$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

42

$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

43

$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

44

$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

45

$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

46

$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

47

$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

48

$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

49

$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

50

$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

51

$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

52

Using Conductance: Line Graph Example

• Consider a straight line $0\ldots M-1$

Ramesh Hariharan

53

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

54

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

55

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

56

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

57

Using Conductance: Complete Graph Example

• Consider a complete undirected graph with vertices $0\ldots M-1$

Ramesh Hariharan

58

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

59

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

60

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

61

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

62

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

63

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

64

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

65

A Certificate for Conductance: Canonical Paths

• Suppose we can find

Ramesh Hariharan

66

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

67

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

68

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

69

Conductance and Canonical Path Congestion: Proof

• Consider any cut $(S,V-S)$

Ramesh Hariharan

70

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

71

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

72

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

73

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

74

Using Canonical Paths: The Hypercube Example

• States tuples $(x_1,\ldots,x_d)$, $x_i=0/1$

Ramesh Hariharan

75

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

76

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

77

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

78

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

79

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

80

The Metropolis Algorithm

• Consider a multidimensional prob. distribution $\cal D:$ $(x_1,\ldots,x_d)\rightarrow p$

Ramesh Hariharan

81

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

82

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

83

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

84

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

85

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

86

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

87

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

88

Ramesh Hariharan

Share
×