Transcript The Markov Chain Monte Carlo Method

The Markov Chain Monte Carlo
Method
Isabelle Stanton
May 8, 2008 Theory Lunch
Monte Carlo vs Las Vegas


Las Vegas Algorithms
are randomized and
always give the
correct results but
gamble with
computation time
Quicksort

Monte Carlo
algorithms have fixed
running time but may
be wrong

Simulated Annealing

Estimating volume
Markov Chains

a memoryless stochastic process, eg, flipping a
coin
1/6
1/6
2
1/6
3
4
1
1/6
6
1/6
5
1/6
1/6
Other Examples of Markov Chains

Shuffling cards

Flipping a coin

PageRank Model

Particle systems – focus of MCMC work
General Idea


Model the system using a Markov Chain
Use a Monte Carlo Algorithm to perform some
computation task
Applications




Approximate Counting - # of solutions to 3-SAT
or Knapsack
Statistical Physics – when do phase transitions
occur?
Combinatorial optimization – simulated
annealing type of algorithms
We'll focus on counting
Monte Carlo Counting

How do you estimate the volume
of a complex solid?

Render with environment maps
efficiently?

Estimate an integral numerically?
(Picnic) Knapsack
weighs 5
weighs 4
weighs 10
How
What
many
is a solution?
solutions
are there?
weighs 2
weighs 4
Holds 20
Counting Knapsack Solutions

Item weights: a = (a0,...an)

Knapsack size: a real number b


Estimate the number of {0,1} vectors, x, that
satisfy a*x ≤ b
Let N denote the number of solutions
Naїve Solution

Randomly generate x

Calculate a*x

If a*x ≤ b return 2n

else return 0

This will return N in expectation:

0*(2n-N) + N*2n / 2n
Is this fast?

Counterexample:

a = (1, ... 1) and b = n/3

Any solution has less than n/3 1's

There are (n choose n/3)*2n/3 solutions
no



Pr(sample x, ||x|| ≤ n/3) < (n choose n/3)*2-2n/3
In expectation, need to generate 2n/3 x's before
we get a single solution!
Any polynomial number of trials will grossly
underestimate N
Knapsack with MCMC


Let Mknap be a markov chain withstate space
Ω(b) = {x | a*x ≤ b}
This will allow us to sample a solution
Various Mknap
a=(0,.5,.5) b = 1.5
a=(0,1,1) b = 1.5
111
011
001
101
010
000
110
100
Mknap Transitions

Transitions

With probability 1/2, x transitions to x

Otherwise, select an i u.a.r.
111
from 0 to n-1 and flip
the ith bit of x.
0.5
101
011
If x' is a
110
1/6
1/6
1/6
solution,
transition there.
0.5
1/6
001
0.5
010
100
0.5
1/6
0.5
1/6
1/6
000
0.5
a=(0,1,1) b = 1.5
Connected?

Is Mknap connected?

Yes. To get from x to x' go through 0.
Ergodicity

What is the stationary distribution of Knapsack?



Sample each solution with prob 1/N
A MC is ergodic if the probability distribution
over the states converges to the stationary
distribution of the system, regardless of the
starting configuration
Is Mknap ergodic? Yes.
Algorithm Idea

Start at 0 and simulate Mknap for enough steps
that the distribution over the states is close to
uniform

Why does uniformity matter?

Does this fix the problem yet?
The trick

Assume that a0 ≤ a1 ... ≤ an (0,1,2,…,n-1,n)

Let b0 = 0 and bi = min{b, Σiaj}

|Ω(bi-1)| ≤ |Ω(bi)| - why?

|Ω(bi)| ≤ (n+1)|Ω(bi-1)| - why?
Change any element of Ω(bi)
to one of Ω(bi-1) by switching
the rightmost 1 to a 0
How does that help?



|Ω(b)| = |Ω(bn)| = |Ω(bn)|/|Ω(bn-1)| x
|Ω(bn-1)|/|Ω(bn-2)| x ... x |Ω(b1)|/Ω|(b0)| x |Ω(b0)|
We can estimate each of these ratios by doing
a walk on Ω(bi) and computing the fraction of
samples in Ω(bi-1)
Good estimate since
|Ω(bi-1)| ≤ |Ω(bi)| ≤ (n+1)|Ω(bi-1)|
Analysis



Ignoring bias, the expectation of each trial is
|Ω(bi-1)|/|Ω(bi)|
We perform t = 17ε-2n2 steps
Focus on Var(X)/E(X)^2 in analyzing efficiency
for MCMC methods
Analysis

If Z is the product of the trials,
E[Z] = П |Ω(bi-1)|/|Ω(bi)|

*Magic Statistics Steps*

Var(Z)/(E[Z])2 ≤ ε2/16

By Chebyshev's:
Pr[(1-ε/2)|Ω(b)| ≤ Z ≤ (1+ε/2)|Ω(b)| ] ≥ 3/4
Analysis



We used nt = 17ε-2n3 steps
This is a FPRAS (Fully Polynomial Randomized
Approximation Scheme)
Except... what assumption did I make?
Mixing Time



Assumption: We are close to the uniform
distribution in 17ε-2n2 steps
This is known as the mixing time
It is unknown if this distribution mixes in
polynomial time
Mixing Time


What does mix in polynomial time?

Dice – 1 transition

Shuffling cards – 7 shuffles

ferromagnetic Ising model at high temperature –
O(nlog n)
What doesn't?

ferromagnetic Ising model at low temperature –
starts to form magnets
Wes Weimer Memorial Conclusion Slide

The markov chain monte carlo
method models the problem
as a Markov Chain and then
uses random walks

Mixing time is important

P# problems are hard

Wes likes trespassing