Exact sampling of skew young diagrams

Even though the combinations of ${\sigma }_{\downarrow }^i$ and ${\sigma }_{\uparrow }^i$ are possible and combinations of ${\tau }_{\downarrow }^i$ and ${\tau }_{\uparrow }^i$ are possible, the following combinations of ${\sigma }_{\downarrow }^i$ , ${\sigma }_{\uparrow }^i$ , ${\tau }_{\downarrow }^i$ , and ${\tau }_{\uparrow }^i$ are impossible because $\sigma \le \tau$ : 1211, 1213, 1233, 1311, 1312, 1322, 1411, 1412, 1413, 1422, 1433, 2211, 2212, 2213, 2214, 2233, 2411, 2412, 2413, 2414, 2422, 2433, 3311, 3312,3313, 3314, 3322, 3324, 3411, 3412, 3413, 3414, 3422, 3424, 3433, 4411, 4412, 4413, 4414, 4422, 4424, 4433, 4434.

The following combinations of ${\sigma }_{\downarrow }^i$ , ${\sigma }_{\uparrow }^i$ , ${\tau }_{\downarrow }^i$ , and ${\tau }_{\uparrow }^i$ are possible and satisfy the inequality because $\frac{\pi \left({\sigma }_{\downarrow }^i\right)}{\pi \left({\sigma }_{\uparrow }^i\right)}$ and $\frac{\pi \left({\tau }_{\downarrow }^i\right)}{\pi \left({\tau }_{\uparrow }^i\right)}$ are equal: 1111, 1122, 1133, 1144, 1212, 1234, 1313, 1324, 1414, 2222, 2424, 3333, 3344, 3434, 4444.

The following combinations of ${\sigma }_{\downarrow }^i$ , ${\sigma }_{\uparrow }^i$ , ${\tau }_{\downarrow }^i$ , and ${\tau }_{\uparrow }^i$ are possible: 1112, 1113, 1114, 1124, 1134, 2234, 3334. They satisfy the inequality because

The following combinations of ${\sigma }_{\downarrow }^i$ , ${\sigma }_{\uparrow }^i$ , ${\tau }_{\downarrow }^i$ , and ${\tau }_{\uparrow }^i$ are impossible because the same location, i, is picked for $\sigma$ and $\tau$ : 1222, 1224, 1244, 1333, 1334, 1344, 1424, 1434, 1444, 2434, 2444, 3444.

Now the only two combinations left are 1214 and 1314. These combinations are possible and the inequality holds because

and

All possible combinations satisfy the inequality from formula [link] . Therefore, our distribution is monotonic.

So to conclude, in order to sample a SYD ${\lambda }_s$ that fits in an a $\times$ b box such that ${\lambda }_s\ge$ one of two fixed YD's ${\lambda }_0$ and ${\lambda }_1$ , we begin with the probability distribution given in "The Probability Distribution on the YD's" . Now couple the histories of YD's ${\lambda }_0\cap {\lambda }_1$ and ${\lambda }_{\text{full}}$ and output the diagram they both return, ${\lambda }_{\text{temp}}$ . If ${\lambda }_{\text{temp}}\ngeqq {\lambda }_0,{\lambda }_{\text{temp}}\ngeqq {\lambda }_1,\text{and}{\lambda }_{\text{temp}}\ge {\lambda }_0\cap {\lambda }_1$ , re-couple the histories of ${\lambda }_0\cap {\lambda }_1$ and ${\lambda }_{\text{full}}$ until the YD outputted is $\ge$ at least one of ${\lambda }_0$ or ${\lambda }_1$ . Rename the outputed YD $\lambda$ .Finally, select either ${\lambda }_0$ or ${\lambda }_1$ according to the conditional probabilities based on the distribution $\pi \left({\lambda }_s\right)\propto q^{|{\lambda }_s|}$ and remove the boxes in this diagram from $\lambda$ . Sampling the fixed YD ( ${\lambda }_0$ or ${\lambda }_1$ ) to remove from the sampled YD ( $\lambda$ ) can be represented by the following function:

where $u_t$ is a random variable sampled according to a uniform distribution on $[0,1]$ . Therefore the black box approach exactly samples according to the probability distribution from formula [link] .

Summary

This module summarizes the research done by the Exact Sampling: Coupling from the Past PFUG of Rice University's VIGRE program. 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 $\times$ b box with the probability distribution stated in formula [link] . We have two problems. In the first problem, we want to sample skew Young diagrams that fit in an a $\times$ 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 $\times$ b box that are greater than one of two fixed Young diagrams.

Acknowledgements

This Connexions module describes research conducted under Rice University's VIGRE program, supported by National Science Foundation grant DMS-0739420. We would like to point out that our PFUG was smaller than the typical PFUG–we did not receive assistance from graduate students or faculty. Thanks to our Postdoc mentor, Sevak Mkrtchyan, and the undergraduate members Joshua Cory and Georgene Jalbuena. The NSF grant only supported the undergraduate members of this PFUG.