## 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

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

## 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