Perfect Sampling: The Basics

Mark Huber

Dept. of Mathematics and Inst. of Statistics and Decision Sciences

Duke University

mhuber@math.duke.edu

www.math.duke.edu/~mhuber

The Problem

Given finite measure over
Generate random variates:

Why this is hard:	is often unknown

Examples: Ising model, #P-complete problems,
numerical integration

Direct is not perfect

Exact Sampling

Direct Sampling

Perfect Sampling

draws exactly from

without knowing

computing

Acceptance Rejection

Acc/Rej Algorithm:

1) Let

2) If accept

Else goto step 1

Features

Running Time Geometric:

No need to know

Properties of Perfect Sampling

Generates exactly from desired distribution

Running time is random (Las Vegas algorithm)

No knowledge of normalizing constant needed

Direct sampling uses knowledge of

The Good News

Generates exactly from desired distribution

Can be used for continuous or discrete

True algorithms
(Markov chain methods are not algorithms unless the mixing time is known)

Useful even if running time unknown

The Bad News

Not a magic solution to slow Markov chains

Requires more effort than Metroplis-Hastings

Methods more complex

Perfect Sampling Methods

Protocols

Techniques

General frameworks for creating perfect sampling algorithms

Specific tricks and methods for turning the protocols into algorithms

Protocols

Coupling Markov chains

Coupling from the past (Propp, Wilson 1996)

Fill, Machida, Murdoch, Rosenthal (1999)

Read-Once CFTP (Wilson 2000)

High noise CFTP (Häggström, Steif 2000)

Modified Acceptance/Rejection

Popping Algorithms (Propp, Wilson 1998)

Randomness Recycler (Fill, Huber 2001)

Techniques

Monotonicity (Propp, Wilson 1996)

Multigamma coupling (Murdoch, Green 1998)

Bounding chains (Häggström, Nelander 1999),

(H. 1999, 2004)

Multishift coupling (Wilson 2000)

How to build a better coupler:

Coupling from the Past

How to describe a Markov chain?
Update function (Propp, Wilson 1996)
Stochastic Recursive Scheme (Borovkov, Foss 1992)
Complete coupling (H. 2004)

Given a sequence of independent, identical uniforms:

...a deterministic function , and starting state :

A simple example

Transposition chain on permutations
Suppose differ by one transposition

Example permuation:
3 4 7 2 1 6 5

Say card is in position

Chain is just swapping two cards at random

More than one complete coupling...

Method 1

Let

Swap cards and

Method 2

Let

Swap cards at positions and

The best one...

Best method

Let

Swap card and card in position

The Key Fact:

This chain can be run without knowing !

Bounding chain

Begin with unknown stationary state

? ? ? ? ? ? ?

Choose card and position

Swap card and position

? ? ? 3 ? ? ?

Continuing...

The next steps:

? ? ? 3 ? ? ?

2 ? ? 3 ? ? ?

2 ? ? 3 ? 5 ?

2 ? 3 ? ? 5 ?

5 ? 3 ? ? 2 ?

5 3 2 1 6 7 4

Once we have a coupler

CFTP(T)

1) Generate iid

2) If then return

3) Else let

return

It works

Thm: As long as is constant with positive probability for some , CFTP terminates with probability 1 and is a perfect sampling algorithm

Drawbacks

Read-Twice: need to store

Noninterruptible: cannot abort algorithm without biasing the sample

As slow as underlying Markov chain

Bounding chain: formal definition

Original state space:

Bounding chain state space:

A chain on bounds one on if they can be coupled so that

Other coupling methods

Mononicity: an update function is monotonic if

(for some partial ordering of )

Track minimum and maximum states

max

min

stat

More useful facts

Techniques exist for continuous state spaces: multigamma, multishift couplers specially designed

Bounding chains with Metropolis-Hastings works with continuous or discrete spaces

CFTP always as good as (and usually faster) than acceptance rejection

Acceptance/Rejection Revisited

Acc/Rej(n)

1) For

2) Generate

3) If for some

start algorithm over again

4) Return

3

4

1

4

2

1

5

7

6

3

4

Why no one does this

Running Time

Solution: Recycle!

Randomness Recycler

Framework (Fill, Huber 2001)

Build up variate one coordinate at a time

If accept that coordinate, keep going

Else recycle what you can, keep going

Acc

Example: permuations

Acc

Acc

Rej

What is distribution of

given rejected?

Effect of rejection

The events of interest

The calculation

The result:

Can recycle all but the last element!

The RR algorithm

Randomness Recycler for Permuations(n)

1) For

2) Generate

3) If for some

goto step 2)

4) Return

Compare and Constrast

Randomness Recycler

Faster

Interruptible

Read-Once

Forward direction (no recursion)

Harder to build

Related to strong stationary times of Markov chains

Coupling from the past

Can utilize existing Markov chains for problems

Noninterruptible, Read-Twice, slower

(can fix exactly one of these with modifications)

Related to coupling times of Markov chains

Running times for permutations

Randomness Recycler

Coupling from the past

Another Example

Hard core gas model

(physics: gases, computer science: network failures)

Assign each node in a graph

Given constants

activity

independent set

In pictures

identically small

1

0

1

1

0

0

0

0

0

0

0

1

1

1

1

1

0

0

0

0

0

0

1

1

identically large

0

1

1

Markov chain

1

0

1

0

0

Gibbs Sampler

1) Let

2) Let

3) If all neighbors of
have and
let

4) Else let

1

0

1

0

Bounding chain

When

Always set

?

?

A Good Move

?

?

?

?

0

?

?

?

?

?

?

?

?

Bounding chain

If

Don't know

A Bad Move

0

0

0

When , more good

moves than bad moves

?

?

0

0

?

?

?

?

?

?

Randomness Recycler

0

0

RR for Hard Core Gas model

1) Start with

2) While

3) Let

4) Let

5) If no conflicts accept

and set

6) Else reject and recycle

1

0

Recycle

0

1

0

0

Suppose

Causes conflict

0

1

0

1

Recycle by resetting neighbors of

0

0

0

1

1

0

Analysis

Randomness Recycler

Coupling from the past

Runtime Valid

Perfect Sampling Summary

True algorithms
no need to know mixing time of anything

Several different types
Coupling from the past (and variants)
Randomness Recycler

No knowledge of normalizing constant needed

Works on continuous and discrete problems

References

A. A. Brovkov and S. G. Foss, Stochastically recursive sequences and their generalizations. Siberian Advances in Mathematics, 2(1): 16—81, 1992

J. A. Fill and M. L. Huber. The Randomness Recycler: A new approach to perfect sampling. In Proc 41st Sympos. on Foundations of Comp. Sci., 503—511, 2000

O. Haggstrom and J. E. Steif. Propp-Wilson algorithms and finitary coding for high noise Markov random fields. Combin. Probab. Computing, 9:425—439, 2000

M. Huber. Perfect sampling using bounding chains. Annals of Applied Probability, 2004, to appear

M. Huber. Perfect sampling with bounding chains. PhD thesis, Cornell University, 1999

References

D. J. Murdoch and P. J. Green. Exact sampling from a continuous state space. Scand. J. Statist., 25(3):483—502, 1998

J. G. Propp and D. B. Wilson. Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures & Algorithms, 9(1—2):223--252, 1996

D. B. Wilson. How to couple from the past using a read-once source of randomness. Random Structures & Algorithms, 16(1):85—113, 2000

My website:

http://www.math.duke.edu/~mhuber

David Wilson's perfect sampling page

http://dbwilson.com/exact/

Mark Huber

2003-11-22T21:59:19