7. Markov Chain Monte Carlo Methods

Monte Carlo Method

• (P)Problem
  • Universe $U$, subset $S\subseteq U$ where $\rho=\frac{|S|}{|U|}$
  • Assume a uniform sampler for elements
  • Estimate $Z=|S|$
• Monte Carlo Method (for estimating)
  • Sample $X_1,X_2,\cdots,X_N$ uniformly and independently from $U$
  • $Y_i=[X_i\in S]$
  • counting: $\hat Z=\frac{|U|}{N}\sum_{i=1}^NY_i$
• $\epsilon$-approx estimator: $(1-\epsilon)Z\leq\hat Z\leq(1+\epsilon)Z$
• Estimator Theorem(Naive): $N\geq\frac{4}{\epsilon^2\rho}\ln\frac{2}{\delta}=\Theta(\frac{1}{\epsilon^2\rho}\ln\frac{1}{\delta})\Rightarrow P(\hat Z$ is $\epsilon$-approx of $|S|)\geq 1-\delta$
• Monte Carlo Method (for sampling)
  • rejection sampling: inefficient if $\rho$ is small

Counting DNF Solutions

• (P)Counting DNF Solutions: #$\text{P}$-hard
  • Input: DNF formula $\phi:\{T,F\}^n\rightarrow\{T,F\},U=\{T,F\}^n$
  • Output: $Z=|\phi^{-1}(T)|,S=\phi^{-1}(T)$
  • $\rho=\frac{|S|}{|U|}$ can be exponentially small
• (P)Union of Sets
  • Input: $m$ sets $S_1,S_2,\cdots,S_m$, estimate $|\bigcup_{i=1}^mS_i|$
  • Output: $|\bigcup_{i=1}^mS_i|$
• Coverage Algorithm: $\rho\geq \frac{1}{m}$
  • $U=\{(x,i)|x\in S_i\}$ (multiset union)
  • $\overline{S}=\{(x,i^*)|x\in S_{i^*}\text{ and }x\in S_i\Rightarrow i^*\leq i\}$
  • Sample unifomr $(x,i)\in U$
    • Sample $i\in\{1,2,\cdots,m\}$
    • Sample uniform $x\in S_i$
  • check if $(x,i)\in\overline{S}$
    • $x\in S_i$
    • and $\forall j<i,x\not\in S_j$
• Counting by Coverage Algorithm: $|U|=\sum_i|S_i|$
• Sampling by Coverage Algorithm: Rejection Sampling

Markov Chain

$\{X_t|t\in T\},X_t\in\Omega$

• discrete time: $T=\{0,1,\cdots\}$
• discrete space: $\Omega$ is finite
• state $X_t\in\Omega$
• chain: stochastic process in discrete time and discrete state space
• Markov property(memoryless): $X_{t+1}$ depends only on $X_t$

$P[X_{t+1}=y|X_0=x_0,\cdots,X_{t-1}=x_{t-1},X_t=x]=P[X_{t+1}=y|X_t=x]$

• Markov chain(memoryless): discrete time discrete space stochastic process with Markov property
• homogeneity: transition does not depend on time
• homogenous Markov chain $\mathfrak{M} = (\Omega,P)$: $P[X_{t+1}=y|X_t=x]=P_{xy}$
  • transition matrix $P$ over $\Omega\times\Omega$
  • (row-)stochastic matrix $P\mathbf{1}=\mathbf{1}$
  • distribution $p^{(t)}(x)=P[X_t=x]$
  • $p^{(t+1)}=p^{(t)}P$
• stationary distribution $\pi$ of matrix $P$: $\pi P=\pi$
• Perron-Frobenius Theorem

Fundamental Theorem of Markov Chain

If a finite Markov chain is irreducible and ergodic(aperiodic), then $\forall$ initial distribution $\pi^{(0)},\lim_{t\rightarrow\infty}\pi^{(0)}P^t=\pi$ where $\pi$ is a unique stationary distribution

• finite: the stationary distribution $\pi$ exists
• irreducible: the stationary distribution is unique
  • all pairs of states communicate
  • Special case
    • not connected: $\pi=\lambda\pi_A+(1-\lambda)\pi_B$
    • weak connected(absorbing case): $\pi=(0,\pi_B)$
• aperiodicity: distribution converges to $\pi$
  • period of state $x$: $d_x=\gcd\{t|P^t_{x,x}>0\}$
  • aperiodic: all states have period $1$
  • if $\forall x\in\Omega,P(x,x)>0$(self-loop), then a chain is aperiodic
  • $x$ and $y$ communicate $\Rightarrow$ $d_x=d_y$

If Markov chain is infinite: positive recurrent

Random Walk

• random walk: Markov Chain Sample on stationary distribution $\pi$
• Fundamental Theorem of Markov Chain on Graph
  • irreducible: $G$ is connected
  • aperiodic: $G$ is non-bipartite
• uniform random walk (on undirected graph) $\mathfrak{M} = (V,P)$
  • Strategy: At each step, uniformly at random move to a neighbor $v$ of current vertex
  • necessary condition for stationary distribution: $\pi(u)=\frac{\text{deg(u)}}{2|E|}$

$P(u,v)=\begin{cases}\frac{1}{\text{deg}(u)} & uv\in E\newline 0&uv\not\in E\end{cases}$

• lazy random walk $\mathfrak{M} = (V,\frac{1}{2}(I+P))$
  • Strategy: At each step, uniformly at random move to a neighbor $v$ of current vertex with probability $\frac{1}{2}$, otherwise do nothing
  • $\pi P=\pi\Rightarrow \pi\frac{1}{2}(I+P)=\pi$

$P(u,v)=\begin{cases}\frac{1}{2} & u=v\newline \frac{1}{2\text{deg}(u)} & uv\in E\newline 0&uv\not\in E\end{cases}$

PageRank

• Rank $r(v)$:importance of a page
  • pointed by more high-rank pages
  • high-rank page have greater influence
  • pages pointing to few others have greater influence
• $d_+(u)$: out-degree
• $r(v)=\sum_{u:(u,v)\in E}\frac{r(u)}{d_+(u)}$
• random walk: $P(u,v)=[(u,v)\in E]\frac{1}{d_+(u)}$
• stationary distribution: $rP=r$

Reversibility

• Detailed Balance Equation: $\pi(x)P(x,y)=\pi(y)P(y,x)$
• time-reversible Markov chain: $\exists\pi,\forall x,y\in\Omega,\pi(x)P(x,y)=\pi(y)P(y,x)$
  • time-reversible: when start from $\pi$, $(X_0,X_1,\cdots,X_n)\sim(X_n,X_{n-1},\cdots,X_0)$
  • $\forall x,y\in\Omega,\pi(x)P(x,y)=\pi(y)P(y,x)\Rightarrow \pi$ is a stationary distribution
• Analyze $\pi$ for a given $P$ (Random walk on graph)
  • $u=v,u\not\sim v$: DBE holds
  • $u\sim v$: $\pi(u)\propto\frac{1}{P(u,v)}\propto\text{deg}(u),\Delta=\max_v\text{deg}(v)$
• Design $P$ to make $\pi$ uniform distribution

MCMC

• Problem setting
  • Given a Markov chain with transition matrix $Q$
  • Goal: a new Markov chain $P$ with stationary distribution $\pi$
• Detailed Balance Equation with acceptance ratio: $\pi(i)Q(i,j)\alpha(i,j)=\pi(j)Q(j,i)\alpha(j,i)$
  • $P(i,j)=Q(i,j)\alpha(i,j)$
  • $\alpha(i,j)=\pi(j)Q(j,i)$
• Original MCMC
  • (proposal) propose $y\in\Omega$ with probability $Q(x,y),x$ is current state
  • (accept-reject sample) accept the proposal and move to $y$ with probability $\pi(y)$
  • run above $T$ times and return
• mixing time $T$: time to be close to the stationary distribution
  • 前沿研究

Metropolis Algorithm

• Metroplis-Hastings Algorithm (symmetric case)
  • (proposal) propose $y\in\Omega$ with probability $Q(x,y),x$ is current state
  • (filter) accept the proposal and move to $y$ with probability $\min\{1,\frac{\pi(y)}{\pi(x)}\}$
• New Transition Matrix (Meet Detailed Balance Equation)

$P(x,y)=\begin{cases} Q(x,y)\min\{1,\frac{\pi(x)}{\pi(y)}\}& x\neq y\newline 1-\sum_{y\neq x}P(x,y) & x=y\end{cases}$

• Metropolis Algorithm (M-H for sampling uniform random CSP solution)
  • Initially, start with an arbitrary CSP solution $\sigma=(\sigma_1,\cdots,\sigma_n)$
  • (proposal) pick a variable $i\in[n]$ and value $c\in[q]$ uniformly at random
  • (filter) accept the proposal and change $\sigma_i$ to $c$ if it does not violate any constraint

Gibbs Sampling

• For $A(x_1,y_1),B(x_1,y_2)$, we have

$\pi(A)\pi(y_2|x_1)=\pi(x_1,y_1)\pi(y_2|x_1)=\pi(x_1)\pi(y_1|x_1)\pi(y_2|x_1)\newline =\pi(x_1,y_2)\pi(y_1|x_1)=\pi(B)\pi(y_1|x_1)$

Let $P(A,B)$ be the marginal distribution on their corrdinate of the same value, then DBE condition holds.

• Goal: Sample a random vector $X=(X_1,\cdots,X_n)$ according to a joint distribution $\pi(x_1,\cdots,x_n)$
• Gibbs Sampling
  • Initially, start with an arbitrary possible $X$
  • run following after $T$ steps:
    • pick a variable $i\in[n]$ uniformly at random
    • resample $X_i$ according to the marginal distribution of $X_i$ conditioning on the current values of $(X_1,\cdots,X_{i-1},X_{i+1},\cdots,X_n)$

Glauber Dynamics

• Glauber Dynamics for CSP
  • Initially, start with an arbitrary CSP solution; at each step, the current CSP solution is $\sigma$
  • pick avarible $i\in[n]$ uniformly at random
  • change value of $\sigma_i$ to a uniform value $c$ among all $\sigma$'s available values $c$, namely changing $\sigma_i$ to $c$ won't violate any constraint