\documentclass[12pt]{article} \usepackage{wide,me} \parindent0pt
$$\newcommand{\Wbar}{{\overline W}}$$

Markov Chains for Sampling

Sampling:

Formalize: what is “near” and “long time”?

Eigenvalues

Method 1 for mixing time: Eigenvalues.

Expanders:

Definition

n factor $c$ more neighbors, at least until $S$ near $n/2$.

Take random walk on $(n,d,c)$ expander with constant $c$

Deduce: mixing time in expander is $O(\log n)$ to get $\epsilon$ r.p.d. (since $\pi_i = 1/n$)

Do expanders exist? Yes! proof: probabilistic method.

Gabber-Galil expanders:

Expanders:

Definition

factor $c$ more neighbors, at least until $S$ near $n/2$.

Take random walk on $(n,d,c)$ expander with constant $c$

Deduce: mixing time in expander is $O(\log n)$ to get $\epsilon$ r.p.d. (since $\pi_i = 1/n$)

Converse theorem: if $\lambda_2 \le 1-\epsilon$, get expander with \[ c \ge 4(\epsilon-\epsilon^2) \] Walks that mix fast are on expanders.

Gabber-Galil expanders:

Application: conserving randomness.