Exact sampling of skew young diagrams  (Page 6/7)

The probability distribution on the yd's

Each YD, $\lambda$ , such that $\lambda \ge {\lambda }_0\cup {\lambda }_1$ corresponds to two SYD's: $(\lambda -{\lambda }_0)$ and $(\lambda -{\lambda }_1)$ . These two SYD's are given $\pi (\lambda -{\lambda }_0)\propto q^{\left|\lambda \right|-|{\lambda }_0|}$ and $\pi (\lambda -{\lambda }_1)\propto q^{\left|\lambda \right|-|{\lambda }_1|}$ . Thus we define

Each YD, $\lambda$ , such that $\lambda \ge {\lambda }_0$ but $\lambda \ngeqq {\lambda }_1$ has only one corresponding SYD: $(\lambda -{\lambda }_0)$ . Thus, we define

Similarly, we define

Also,

Tripling from the past

The first method we devised for sampling SYD's according to the probability distribution in formula [link] was simply to “triple” the young diagrams ${\lambda }_0,{\lambda }_1$ , and ${\lambda }_{\text{full}}$ , and then remove the boxes in either ${\lambda }_0$ or ${\lambda }_1$ based on the conditional probabilities based on $q^{|{\lambda }_s|}$ . Unfortunately, we found a simple counterexample that proved that this method does not work because the partial ordering of YD's is not preserved due to the monotonicity of our probability distribution on YD's as stated in "The Probability Distribution on the YD's" breaking in some places (see [link] for the counterexample).

The “black box" approach

Since the method of tripling from the past did not work, we devised another method which we call the black box approach. With this approach, we change the probability distribution by giving positive probability proportional to $X\left(\lambda \right)$ to young diagrams $\lambda$ such that $\lambda \ngeqq {\lambda }_0,\lambda \ngeqq {\lambda }_1,$ and $\lambda \ge {\lambda }_0\cap {\lambda }_1$ . Then we sample according to this new distribution, and if the sampled YD ${\lambda }_{\text{temp}}$ satisfies all of the following:

discard ${\lambda }_{\text{temp}}$ and sample another YD according to the new distribution until the sampled YD ${\lambda }_{\text{temp}}$ satisfies: ${\lambda }_{\text{temp}}\ge$ at least one of ${\lambda }_0,{\lambda }_1$ . When we sample a ${\lambda }_{\text{temp}}$ such that ${\lambda }_{\text{temp}}\ge$ at least one of ${\lambda }_0,{\lambda }_1$ , then we output ${\lambda }_{\text{temp}}$ and rename it $\lambda$ . It is easily seen that the output, $\lambda$ , has been sampled according to the probability distribution stated in "The Probability Distribution on the YD's" . See [link] for a schematic of the Black Box Approach.

Theorem: The following values of X give a monotonic distribution for sampling:

We will begin by numbering the possible categories of $\sigma$ and $\tau$ as follows:

We will label ${\sigma }_{\downarrow }^i$ first, ${\sigma }_{\uparrow }^i$ second, ${\tau }_{\downarrow }^i$ third, and ${\tau }_{\uparrow }^i$ fourth. For example, 1234 represents the situation where ${\sigma }_{\downarrow }^i$ belongs to category 1, ${\sigma }_{\uparrow }^i$ belongs to category 2, ${\tau }_{\downarrow }^i$ belongs to category 3, and ${\tau }_{\uparrow }^i$ belongs to category 4.

The possible situations for ${\sigma }_{\downarrow }^i$ and ${\sigma }_{\uparrow }^i$ are the following: 11, 12, 13, 14, 22, 24, 33, 34, and 44. The values of $\frac{\pi \left({\sigma }_{\downarrow }^i\right)}{\pi \left({\sigma }_{\uparrow }^i\right)}$ for each situation are the following:

$11:\frac{1}{q}$

$12:\left(\frac{1}{q}\right)\left(\frac{1}{1+q^{|{\lambda }_1|-|{\lambda }_0|}}\right)$

$13:\left(\frac{1}{q}\right)\left(\frac{1}{1+q^{|{\lambda }_0|-|{\lambda }_1|}}\right)$

$14:\left(\frac{1}{q}\right){(q^{|{\lambda }_1|-|{\lambda }_0|}+2+q^{|{\lambda }_0|-|{\lambda }_1|})}^{-1}$

$22:\frac{1}{q}$

$24:\left(\frac{1}{q}\right)\left(\frac{1}{1+q^{|{\lambda }_0|-|{\lambda }_1|}}\right)$

$33:\frac{1}{q}$

$34:\left(\frac{1}{q}\right)\left(\frac{1}{1+q^{|{\lambda }_1|-|{\lambda }_0|}}\right)$

$44:\frac{1}{q}$

The possible situations for ${\tau }_{\downarrow }^i$ and ${\tau }_{\uparrow }^i$ are the same situations for ${\sigma }_{\downarrow }^i$ and ${\sigma }_{\uparrow }^i$ . Also, the values of $\frac{\pi \left({\tau }_{\downarrow }^i\right)}{\pi \left({\tau }_{\uparrow }^i\right)}$ are the same values for $\frac{\pi \left({\sigma }_{\downarrow }^i\right)}{\pi \left({\sigma }_{\uparrow }^i\right)}$ for each situation.

In order to prove monotonicity, we need to show that for all possible combinations of ${\sigma }_{\downarrow }^i,{\sigma }_{\uparrow }^i,{\tau }_{\downarrow }^i$ , and ${\tau }_{\uparrow }^i$ , the inequality from formula [link] holds. In all of the following cases, we will prove that either the inequality holds or the combinations of ${\sigma }_{\downarrow }^i,{\sigma }_{\uparrow }^i,{\tau }_{\downarrow }^i$ , and ${\tau }_{\uparrow }^i$ are impossible.