<< Chapter < Page Chapter >> Page >
This module summarizes the research done by the Exact Sampling: Coupling from the Past PFUG of Rice University's VIGRE program during the summer of 2010. VIGRE is a program of Vertically Integrated Grants for Research and Education in the Mathematical Sciences under the direction of the National Science Foundation. A PFUG consists of Postdocs, Faculty, Undergraduates and Graduate students who work together on a common problem. We want to sample skew Young diagrams that fit in an a x b box with a specified probability distribution. We have two problems. In the first problem, we want to sample skew Young diagrams that fit in an a x b box that are greater than or equal to a fixed Young diagram. In the second problem, we want to sample skew Young diagrams that fit in an a x b box that are greater than one of two fixed Young diagrams.

Background

Introduction

A Young diagram (“YD", denoted λ ) is a finite collection of squares arranged in such a way that the leftmost column is the tallest column and each subsequent column has height equal to or less than the preceding column. For example, the shaded region in [link] is a YD. There is a natural partial ordering of Young diagrams–a YD is “larger" than a second YD if it contains the entire second YD. We will define a skew Young diagram (“SYD", denoted λ s ) as a pair of two YD's in this way: λ s = ( λ U , λ L ) where λ U , λ L are YD's such that λ U λ L . For example, the shaded region in [link] is a SYD whose λ U is the YD in [link] and λ L has columns of height 3,2,1,1. A SYD λ s = ( λ U , λ L ) is greater than a YD λ if λ L = λ . A SYD λ s = ( λ U , λ L ) is equal to a YD λ if λ U = λ L = λ .

Young Diagram in a 9 × 6 box
Skew Young Diagram in a 9 × 6 box

To explain our problem, let us first define what a probability distribution is:

Definition: A probability distribution, π , on a finite set S is a function that assigns a nonnegative real number, π ( s ) , (the “probability" of choosing s) to each element s S such that

s S π ( s ) = 1 .

We want to sample from SYD's that fit in an a × b box with this probability distribution:

π ( λ s ) q | λ s | , 0 < q 1

where | λ s | denotes the size of the diagram λ s or, simply, the number of boxes in the diagram (i.e. for λ s in [link] , | λ s | = 15 ).

Propp and Wilson developed an algorithm for exact sampling by altering the Markov Chain Monte Carlo algorithm [link] . Sampling by the Markov Chain Monte Carlo simulation does not return a value exactly according to the probability distribution desired, but instead samples according to a distribution whose values are within a small error of the corresponding values of the desired distribution. It is not exact sampling because it is forward simulation and can only be exact if a Markov Chain is taken infinitely many steps into the future, which is impossible. So instead of forward simulation, Propp and Wilson sample by taking steps of the Markov Chain from an indefinite point in the past to the present and have proven that this algorithm, called Coupling from the Past (“CFTP"), samples exactly according to a given probability distribution [link] .

Propp and Wilson's CFTP can be used to sample from lattice paths in an a × b square lattice that start in the top left corner and take only downward and leftward steps, terminating in the bottom right corner [link] . Thankfully, there is a bijection between YD's and lattice paths–every lattice path corresponds to a unique YD consisting of the unit boxes under the path (and vice versa). Thus, there is a one-to-one correspondence between lattice paths and YD's. Due to this bijection, CFTP [link] may be applied to sample from YD's.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, The art of the pfug. OpenStax CNX. Jun 05, 2013 Download for free at http://cnx.org/content/col10523/1.34
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'The art of the pfug' conversation and receive update notifications?

Ask