Exact sampling of skew young diagrams

Background

Introduction

A Young diagram (“YD", denoted $\lambda$ ) 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 ${\lambda }_s$ ) as a pair of two YD's in this way: ${\lambda }_s=({\lambda }_U,{\lambda }_L)$ where ${\lambda }_U,{\lambda }_L$ are YD's such that ${\lambda }_U\ge {\lambda }_L$ . For example, the shaded region in [link] is a SYD whose ${\lambda }_U$ is the YD in [link] and ${\lambda }_L$ has columns of height 3,2,1,1. A SYD ${\lambda }_s=({\lambda }_U,{\lambda }_L)$ is greater than a YD $\lambda$ if ${\lambda }_L=\lambda$ . A SYD ${\lambda }_s=({\lambda }_U,{\lambda }_L)$ is equal to a YD $\lambda$ if ${\lambda }_U={\lambda }_L=\lambda$ .

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

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

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

where $|{\lambda }_s|$ denotes the size of the diagram ${\lambda }_s$ or, simply, the number of boxes in the diagram (i.e. for ${\lambda }_s$ in [link] , $|{\lambda }_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 $\times$ 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.