Perfect Sampling for Some Mixtures of Distributions

Mark Huber

Dept. of Mathematics and Institute of Statistics and Decision Sciences

Duke University

mhuber@math.duke.edu

www.math.duke.edu/~mhuber

Searching for the Light Side...

Markov chains

Quicker, easier

Not true algorithms for generating variates

Flaw: unknown mixing time

Luke: Is the dark side stronger?

Yoda: No, no, no. Quicker, easier, more seductive.

Star Wars: The Empire Strikes Back

Give a little, get a little

Markov chains

Quicker, easier

Not true algorithms for generating variates

Flaw: unknown mixing time

Perfect Samplers

Gives exact samples, i.i.d. (without knowing a normalizing constant)

True algorithms—no need for diagnostics

Can be difficult to design

The Randomness Recycler

RR gives exact samples (Fill & H. '99)

Framework for designing perfect samplers

Moderately more complex to implement

Applicable to smaller range of problems

Move ahead 1 chain

Two sided interval permutations

Ising and Potts model

Mixtures of fixed distributions

Perfect Samplers

Complete Couplers
Coupling from the past (Propp,Wilson '96)
(3 problems: noninterruptible, read twice,
not linear time because of underlying chain)
FMMR (Fill, Machida, Murdoch, Rosenthal '00)
Read once CFTP (Wilson '00)
Linear time CFTP (Haggestrom, Steif '96)

Finding the Distribution
Strong stationary stopping times
(Aldous,Diaconis '87), (Diaconis, Fill '90)
Randomness recycler (Fill, H. '99)

The Problem

Have unknown mixture of known distributions:

Prior on parameters:

Draws from the mixture:

What is the posterior like?

The Posterior

The posterior

Normalize

where

and either or is 1

Other perfect sampling work...

First perfect sampling method (Hobert, Robert, Titterington '99)

Coupling From the Past

For two mixtures have monotonicity

Wraps around Markov chain (auxilliary var.)

Bounding chains (H. '99)

Only use auxilliary variables

RR very different from CFTP

Features of RR

Why use RR?

Interruptible (no impatience bias)

Read-once

Can beat Markov chain based algorithms

Online

Update samples as more data arrives

Suited to sampling from posteriors

RR disadvantages

Can't take advantage of monotonicity

Ingredients of RR

RR Posterior Problem

Starting distribution can sample from

Prior (can sample from)

Family of distributions make bridge between start and final distribution

Recycling method

Posterior using only some of data points

Main Idea of (cont.) RR

Inside any (positive density over a compact space) is the density we want:

Given a draw from accept as draw from with prob:

Pictorially

For our example

Consider first data points:

Ex:

Adding second term

Suppose have draw from

Note:

Accept as draw from with probability

Summarizing this move

If we didn't accept

Keep on trying

When at first you don't accept, try, try again...

Where

Note:

The End Result

After adding all the terms into the posterior:

This marks the end of Phase I of the algorithm

In Phase II, we try to eliminate the extra term:

Phase II

The Markov chain (auxilliary variables)

At

Write

Choose with prob

Choose new state

Introduce random changes to :

Idea: Markov chain steps suppose to move

distribution towards , so try them

Markov chain for mixtures

1) Given choose a particular beta term

2) Given a beta term, generate new

Proof that this works

Invariant dist: start in take a step

Now with extra terms

Now try: start in take a step

Extra factor

Me, myself, and

To eliminate extra term, use combinatorics:

Brave new density

Final Step

Same as posterior without data point

Use same type of move as in Phase II to add

term back into density

Cyclic procedure

MC step

(algebra)

Bins

Results

Take 100 points from

Runtime

Simple recycling: steps to get perfect sample

Open Problems

Even better recycling

Have several recycling methods

There exists best method—don't have it

No theoretical bounds yet on run time

More Mixtures

This RR method extends easily

Not known how effective

Conclusions

Randomness Recycler

Easy to set up everything but recycle part

(Natural setup for posterior sampling)

Good recycler essential to rapid algorithm

A good recycler is hard to find

I.I.D. samples

Neutral towards montonicity (at present)

Mixture Problems

Already CFTP method wins when

Now also RR method: interruptible, read-once

Unclear which best with mixtures

Mark Huber

2002-09-29T12:35:41

Mark Huber