Counting Problems
Two big pieces:
- Equivalence of counting and generating via self reducibility
- Generating via Markov chains
Application: Permanent
Counting perfect matchings
- Choose random $n$-edge set
- check if matching
- problem: rare event
- to solve, need sample space where matchings are dense
Idea: self reducibility by adding an edge (till reach complete graph)
- problem: don't know how to generate random matching
Different idea: ratio of $k$-edge to $k-1$-edge matchings
- telescope down to 1-edge matchings (self reduction)
- in dense graphs (degree $n/2$), ratio is at most $m^3$ both ways.
- map each $k$ edge matching by removing an edge: $n^2$ to 1
- map each $k-1$ edge matching to $k$-edge matching by
augmenting path of length at most 3.
- take unmatched $u$ and $v$
- if unmatched neighbor of $u$ or $v$, done
- by $u$ and $v$ have $n/2$ neighbors, so if all matched, some neighbor $b$ of $u$ matched to some neighbor $a$ of $v$.
- so each size $k$ matching “receives” at most $m^3$ size $k-1$ matchings.
Generate via random walk
- based on using uniform generation to do sampling.
- applies to minimum degree $n/2$
- Let $M_k$ be $k$-edge matchings, $\|M_k\|=m_k$
- algorithm estimates all ratios $m_k/m_{k-1}$, multiplies
- claim: ratio $m_{k+1}/m_k$ polynomially bounded (dense).
- deduce sufficient to generate randomly from $M_k\cup M_{k-1}$, test frequency of $m_k$
- do so by random walk of local moves:
- with probability $1/2$. stay still
- else Pick random edge $e$
- if in $M_k$ and $e$ matched, remove
- if in $M_{k-1}$ end $e$ can be added, add.
- if in $M_k$, $e=(u,v)$, $u$ matched to $w$ and $v$ unmatched, then match $u$ to $w$.
- else do nothing
- Note that exactly one applies
- Matrix is symmetric (undirected), so double stochastic, so stationary distribution is uniform as desired.
- In text, prove $\lambda_2 =1-1/n^{O(1)}$ on an $n$ vertex graph (by proving expansion property)
- so within $n^{O(1)}$ steps, rpd is polynomially small
- so can pretend stationary
Need to prove rapid mixing
- Markov chain is an unweighted undirected graph
- Show markov chain is an expander
- but not quite: count edges leaving rather than neighboring nodes
- same argument implies rapid mixing
Canonical paths argument
- Suppose chain has $N$ vertices
- Want to prove every set $S$ has $\Omega(|S|)$ edges leaving
- Pick a path between every pair of verties
- Show no edge on more than $3n^4N$ paths
- Know $S(N-S)\ge SN/2$ paths leave $S$
- So at least that$/3n^4N=S/6n^4$ edges leave
- i.e, a polynomial fraction of $S$
- Suffices to prove mixing time polynomial (ie as if expansion was $1+1/n^4$ so mixing time like $n^4$
Canonical path construction:
- path each $M_{n-1}$ to an $M_n$ by a length 3 path
- so each $M_k$ only gets $m^3$ of the matching
- make a canonical path for each $M_n$ pair
- corresponds to $m^6$ canonical paths including $M_{n-1}$ “children”
- for two perfect matchings:
- XOR them
- get a collection of even cycles
- so arbitrarily number (order) all even cycles
- canonical path “unwinds” these cycles: remove first matching edge, add second matching edge, etc.
- do so in canonical order, starting with smallest numbered vertex in smallest numbered cycle and going up
- claim only $N$ canonical paths use an edge
- prove by fixing edge, and creating a bijection between canonical paths that use it and the $N$ perfect matchings
- given matchings $s$ and $t$, XOR is collection of cycles
- suppose $M$ is matching on transition edge
- XORing cycles with $M$ gives a different matching $M'$
- $M'$ is the representative of the $s$-$t$ path
- Show this is a bijection
- map from representative to $s$-$t$ pair
- from representative $M'$, XOR with $M$ yields cycles unwound on canonical path
- edges of $M$ not in any cycle are in both $s$ and $t$ (don't get unwound)
- edges of $M$ in a cycle are in exactly one of $s$ and $t$
- edges that precede edge that is unwound in this transition have already been unwound
- i.e. those in $M$ are in $t$, those not in $M$ are in $s$
- edges that follow edge unwound in this transition have not yet been unwound
- i.e. those in $M$ are in $s$, those not in $M$ are in $t$.
Recently, extended to non-dense case.
Volume
Outline:
- Describe problem. Membership oracle
- $\sharp P$ hard to volume intersection of half spaces in $n$ dimensions
- In low dimensions, integral.
- even for convex bodies, can't do better than $(n/\log n))^n$ ratio
- what about FPRAS?
Estimating $\pi$:
- pick random in unit square
- check if in circle
- gives ratio of square to circle
- Extends to arbitrary shape with “membership oracle”
- Problem: rare events.
- Circle has good easy outer box
Problem: rare events:
- In 2d, long skinny shapes
- In high $d$, even round shape has exponentially larger bounding box
Solution: “creep up” on volume
- modify $P$ to contain unit sphere $B_1$, contined in larger $B_2$ of radius $r$ with $r/r_1$ polynomial
- choose $\rho=1-1/n$.
- Consider sequence of bodies $\rho^i r P \cap B_2$
- note for large $i$, get $P$
- but for $i=0$, body contains $B_2$
- so volume known
- so just need ratios
- At each step, need to random sample from $\rho^i r P \cap B_2$
Sample method: random walk forbidden to leave
- MC irreducible since body connected
- ensure aperiodic by staying put with prob. 1/2
- markov chain is “regular graph” so uniform stationary distribution
- eigenvalues show rapid mixing: after $t$ steps, r.p.d at most \[ (1-\frac{1}{10^17n^19})^t \]
- eigenvalues small because body convex: no bottlenecks.
Observations:
- Key idea of self reducibility: compare size of sequence of “related” shapes, then telescope ratios.
- Sizes compared by sampling
- Sample by markov chain
- wait: markov chain not exact?
- doesn't matter: just get accurate to within $(1-1/poly)$ in each step, product of errors still tiny.
Coupling:
Method
- Run two copies of Markov chain $X_t,Y_t$
- Each considered in isolation is a copy of MC (that is, both have MC distribution)
- but they are not independent: they make dependent choices at each step
- in fact, after a while they are almost certainly the same
- Start $Y_t$ in stationary distribution, $X_t$ anywhere
- Coupling argument: $$ \begin{eqnarray*} \Pr[X_t=j] &= &\Pr[X_t=j \mid X_t=Y_t]\Pr[X_t=Y_t]+\Pr[X_t=j \mid X_t\ne Y_t]\Pr[X_t\ne Y_t]\\ &= &\Pr[Y_t=j]\Pr[X_t=Y_t]+\epsilon\Pr[X_t=j\mid X_t\ne Y_t] \end{eqnarray*} $$ So just need to make $\epsilon$ (which is r.p.d.) small enough.
$n$-bit Hypercube walk: at each step, flip random bit to random value
- At step $t$, pick a random bit $b$, random value $v$
- both chains set but $b$ to value $v$
- after $O(n\log n)$ steps, probably all bits matched.
Counting $k$ colorings when $k>2\Delta+1$
- The reduction from (approximate) uniform generation
- compute ratio of coloring of $G$ to coloring of $G-e$
- Recurse counting $G-e$ colorings
- Base case $k^n$ colorings of empty graph
- Bounding the ratio:
- note $G-e$ colorings outnumber $G$ colorings
- By how much? Let $L$ colorings in difference ($u$ and $v$ same color)
- to make an $L$ coloring a $G$ coloring, change $u$ to one of $k-\Delta=\Delta+1$ legal colors
- Each $G$-coloring arises at most one way from this
- So each $L$ coloring has at least $\Delta+1$ neighbors unique to them
- So $L$ is $1/(\Delta+1)$ fraction of $G$.
- So can estimate ratio with few samples
- The chain:
- Pick random vertex, random color, try to recolor
- loops, so aperiodic
- Chain is time-reversible, so uniform distribution.
- Coupling:
- choose random vertex $v$ (same for both)
- based on $X_t$ and $Y_t$, choose bijection of colors
- choose random color $c$
- apply $c$ to $v$ in $X_t$ (if can), $g(c)$ to $v$ in $Y_t$ (if can).
- What bijection?
- Let $A$ be vertices that agree in color, $D$ that disagree.
- if $v\in D$, let $g$ be identity
- if $v \in A$, let $N$ be neighbors of $v$
- let $C_X$ be colors that $N$ has in $X$ but not $Y$ ($X$ can't use them at $v$)
- let $C_Y$ similar, wlog larger than $C_X$
- $g$ should swap each $C_X$ with some $C_Y$, leave other colors fixed. Result: if $X$ doesn't change, $Y$ doesn't
- Convergence:
- Let $d'(v)$ be number of neighbors of $v$ in opposite set, so \[ \sum_{v \in A}d'(v) = \sum_{v \in D} d'(v) = m' \]
- Let $\delta=|D|$
- Note at each step, $\delta$ changes by $0,\pm1$
- When does it increase?
- $v$ must be in $A$, but move to $D$
- happens if only one MC accepts new color
- If $c$ not in $C_X$ or $C_Y$, then $g(c)=c$ and both change
- If $c\in C_X$, then $g(c) \in C_Y$ so neither moves
- So must have $c \in C_Y$
- But $|C_Y| \le d'(v)$, so probability this happens is \[ \sum_{v \in A} \frac1n \cdot \frac{d'(v)}{k} = \frac{m'}{kn} \]
- When does it decrease?
- must have $v \in D$, both move (since move to same color)
- sufficient that pick color not in either neighborhood of $v$,
- total neighborhood size $2\Delta$, but that counts the $d'(v)$ elements of $A$ twice.
- so Prob. \[ \sum_{v \in D}\frac1n \cdot \frac{k-(2\Delta-d'(v))}{k} = \frac{k-2\Delta}{kn}\delta+\frac{m'}{kn} \]
- Deduce that expected change in $\delta$ is difference of above, namely \[ -\frac{k-2\Delta}{kn}\delta = -a\delta. \]
- So after $t$ steps, $E[\delta_t] \le (1-a)^{t}\delta_0 \le (1-a)^tn$.
- Thus, probability $\delta>0$ at most $(1-a)^t n$.
- But now note $a > 1/n^2$, so $n^2\log n$ steps reduce to one over polynomial chance.
Note: couple depends on state, but who cares
- From worm's eye view, each chain is random walk
- so, all arguments hold
Counting vs. generating:
- we showed that by generating, can count
- by counting, can generate: