Mark Huber

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

Duke University

mhuber@math.duke.edu

www.math.duke.edu/~mhuber

Time Dependent Update Functions for Perfect Sampling

A simple logic puzzle

Results for the Putnam Mathematical Competition in 2000

Harvard

MIT

1

2

3

4

Facts:

Harvard came in 3 (or better)

Duke

Caltech

Caltech came in 2 (or better)

Duke came in first

Permutations

Simple idea can form the basis for algorithms for generating weighted permutations

Each permutation given weight

Goal generate random variates from

In this talk

A weighted permutation problem

Perfect sampling with CFTP

Time dependent update functions

Bounding chains

BC for weighted permutations

does not work with original CFTP

Solving the permutation problem

A continuous example

A permutation problem

The Goal

Generate uniformly from the set of random linear extensions of a poset

Linear Extensions

A partial order on is

1) Reflexive

2) Antisymmetric

3) Transitive

A linear extension is a permutation where

Suppose throughout is a linear ext.

Let

Example

1

2

3

4

5

Some Linear Extensions

Say item 3 is in position 2

Questions

Question: How many linear extensions?

Bad news: #P complete

[Brightwell, Winkler 1991]

Good news: selfreducible so generating

samples leads to efficient (approx) counting

[Jerrum, Valiant, Vazirani 1986]

Question: Average # of inversions?

Variant of nonparametric Kendall's tau test

[Efron, Petrosian 1999]

Markov chain approach

Describe Markov chain via update function

Computer simulation of Markov chains	(use pseudorandom numbers)

Also known as

transition function

stochastic recursive scheme

Markov chain approach

One step in linear extensions chain

1] Choose uniformly from

2] Choose uniformly from

3] Let

4] If do nothing

Else

(Pick random position, flip fair coin,

if coin heads and does not violate partial order

then swap items at position and one to the right)

Example steps

State

1

2

3

4

5

Randomness

What's known

[Bubley, Dyer 1999] Different Markov chain	mixes steps

[Wilson 2004] Original chain mixes

[Felsner, Wernich 1997] Perfect sampling when poset two dimensional

This work: perfect sampling arbitrary poset

Perfect Sampling Algorithm

A perfect sampling algorithm has 3 properties:

1) Generates exact random variates from the	target distribution
2) Running time is random with exponential tails

3) No knowledge of the normalizing constant
(good since we do not know )

Comments

1) Usually samples are only approximately from

target distribution
2) Running time very unlikely to be much larger

than expected value (otherwise Dyer showed	any approximate sampler is a perfect sampler)
3) When known it is a direct sampler

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

Coupling From the Past

CFTP [Propp, Wilson '96]

Ingredients: update function for chain,

1) pretend have unknown stationary rand. var.

2) run chain forward fixed number of steps

3) if state becomes known, output

4) else call CFTP recursively

5) run chain forward fixed number of steps

An example

Example

Start T = -5

If had

then

output

First level of CFTP

Example

Start T = -5

Suppose I do not know

let

if

else ....

Second level of CFTP

Go back farther in time...

Start T = -100

Do not know

find

if

else ....

Third level of CFTP

Go back farther in time...

Start T = -1000

Do not know

then find

if

find

else [keep going back in time until success]

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 keep track of

Time dependent update functions

Original CFTP

Use same update function every time

(is a Markovian coupling)

Time dependent CFTP

Let update function change each step

(non-Markovian coupling)

Sufficient conditions on f

Our requirement

Suppose , then

for all values of

Proof that Time dependent CFTP works essentially same as original proof

Bounding Chains

Bounding chains

Is itself a Markov chain

Bound each dimension separately

Keeps set of possible values at each coordinate

For permuations, keep interval for each item

Pictorially

Trick from beginning

When bounding state

has all different

Running the bounding chain

Suppose bounding state

want to run the chain forward so that if

then

Active items

Call item active if

or

Why look at active

When all items active

Example starting bounding chain

Since item 1 preceeds 3 items,

1

2

3

4

5

Case by case

Choose

Choose

Case I: no active items at position

Action

bounding state unchanged

Case II

Case II: one active item at position

Worst case

Could be

Case II continued

Worst case

Action

If

Case III

Case III: one active item at position

Note: any other active item with

has

Action

If

Case IV

Case IV: active items at positions

4 subcases when

Case IV continued

See what happens in each subcase

Action

If do nothing

else

Time dependent

This update function is time dependent

The update depends on the state of the

bounding chain

The bounding chain state depends on

Analysis

Key fact: The number of active states can only stay the same or increase

Call position a hole if

Analysis

Roughly speaking: clear positions take a simple random walk on

Analysis

When a hole reaches it creates a new active item

Time for algorithm is time for all holes to reach state

Analysis continued

A hole needs moves in expectation to reach

A hole is moved one in every steps

There are at most holes at the start

Expected Running time

A potential proof

Create a potential function

Can show

CREDIT: Sloan Digital Sky Survey at Apache Point Observatory

A related problem

[Efron, Petrosian 1999] Quasar luminosity data is doubly truncated, making testing correlation difficult. They suggest nonparametic test: to find p-value, need samples from interval permutations

Analysis difficult

Unfortunately, holes cannot move freely in this example, and so currently no a priori estimates on the running time of this algorithm are known

On the other hand: who cares? Run the algorithm, if it's fast use it.

What are update functions?

Update functions are examples of couplings

A coupling runs two processes simultaneously

Marginally, each process looks like the original chain

Their moves can be dependent

A coupled process is faithful if

The coupling lemma says that the time until coupling is a bound on the mixing time of the Markov chain

Continuous problems

Time dependent couplings have already been used for continuous problems

Used for proving mixing times

Not for perfect sampling

time

coupling 1

coupling 2

Continuous Coupling

Type 1 coupling brings the states “close”

Type 2 coupling finishes the job

[Wilson 1999] Multishift coupling for type 2 works for unimodal distribution on moves

With time dependent CFTP, need much weaker type 2 coupling

Example

Continuous random walk on

Type 1 update function

Type 1 in action

Starting difference: 5 on [0,20]

Number of steps: 500

Final difference: 0.000000078

Type 2 coupler

Idea: Distribution of overlaps once close

A draw that lands in shared density region works for both processes

Multishift and time dependent

To perfectly sample

Use type 1 update function in time [-T,1]

Use type 2 update function at time 1 to finish

For most problems, this idea makes continuous no more difficult than discrete

Highlights

Adding time dependent update functions increases the power of CFTP for perfect sampling

For linear extensions, provides fastest known method of generating samples

Also works for interval permuations

Considerably simplifies algorithms for continuous problems

References

G. Brightwell and P. Winkler, Counting linear extensions. Order 8(3): 1—17, 1991

R. Bubley and M. Dyer, Faster random generation of linear extensions, Disc. Math. 201 (1999) 81—88

B. Efron and V. Petrosian. Nonparametric methods for doubly truncated data. J. of Am. Stat. Assoc. Sep (1999) 824—834

S. Felsner and L. Wernisch. Markov chains for linear extension, the two-dimensional case. In Proc. of 8th Annual ACM-SIAM Symposium on Discrete Algorithms, (1997) 239—247

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

M. Huber. Fast perfect sampling from linear extensions (submitted)

References

M. Jerrum, L. Valiant, and V. Vazirani, Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43 (1986) 169—188

D. Wilson, Mixing times of lozenge tilings and card-shuffling Markov chains, Annals of Applied Probability, 2004

My website:

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

David Wilson's perfect sampling page

http://dbwilson.com/exact/

Mark Huber

2004-03-06T12:04:19