Fullscreen View

The author recommends viewing the raindrop in fullsceen.
Click here to go fullscreen.
×

Raindrop Info

Title:
Random Walks in Markov Chains: Part II
Authors:
Created:
2014-Mar-02
Updated:
2019-Sep-29
Views:
1588
Pages:
88
Likes:
5
×

Copy the link below to embed!

small
medium
large
×
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

Copy the link below to share!

Share
×