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

A heat bath algorithm is simply a procedure of updating the vertices $i$ one at a time based on the conditional probabilities given by $\pi$ . All vertices must be chosen infinitely often so that there is no bias towards any assignments, $\sigma$ . The following equation provided by Propp and Wilson [link] indicates how $i$ will be updated:

where $t$ is time, and $u_t$ is a random real number in $[0,1]$ chosen according to the uniform distribution. All $u_t$ 's are chosen independently of each other [link] .

We may order sets of configurations by the following definition: $\sigma \le \tau$ iff $\sigma \left(i\right)\le \tau \left(i\right)$ $\forall i\in V$ , where $\uparrow >\downarrow$ . Two configurations are incomparable if one is not greater than the other. We also say that a probability distribution, $\pi$ , is monotonic if and only if

or equivalently, $\pi \left({\sigma }_{\downarrow }^i\right)\pi \left({\tau }_{\uparrow }^i\right)\ge \pi \left({\sigma }_{\uparrow }^i\right)\pi ({\tau }_{\downarrow }^i$ ). If the probability distribution is monotonic (or “attractive"), then the partial ordering of $\sigma$ and $\tau$ is preserved after the heat bath algorithm is applied. To see why this is true, note that if the inequality in formula [link] holds, then $\pi \left({\sigma }_{\downarrow }\right)$ must be greater than or equal to $\pi ({\tau }_{\downarrow }$ ). The proof is as follows:

If we choose the same $u_t$ for both $\sigma$ and $\tau$ , it is impossible for ${\sigma }_{\uparrow }^i$ and ${\tau }_{\downarrow }^i$ to occur simultaneously. Therefore after any amount of time, $t$ , whatever configuration $\tau$ becomes after $t$ updates must remain greater than or equal to whatever configuration $\sigma$ becomes after $t$ updates. This preservation of partial ordering leads to the theorem proved by Propp and Wilson:

Theorem: If one runs the heat bath for an attractive spin system under the coupling-from-the-past protocol, one will generate states of the system that are exactly governed by the target distribution, $\pi$ [link] .

Exact sampling of yd's in an a $\times$ B box

Expanding the Monotone Monte Carlo Algorithm to YD's is fairly simple, if we treat each YD as a configuration set, $\sigma$ , in a spin system. The unit squares are vertices $i$ in the vertex set of all $i$ in the a $\times$ b box, where $i$ spins up if $i$ is in the YD $\sigma$ and $i$ spins down otherwise. The configurations are selected according to the probability distribution

where $\left|\sigma \right|$ denotes how many vertices in $\sigma$ spin up. The vertices are updated according to the conditional probabilities given by $\pi$ . There are three equations to update by: 1) if $\sigma \left(i\right)=\uparrow$ is improbable, $f_t(\sigma$ , $u_t)={\sigma }_{\downarrow }^i$ ; 2) if $\sigma \left(i\right)=\downarrow$ is improbable $f_t(\sigma$ , $u_t)={\sigma }_{\uparrow }^i$ ; 3) if both $\sigma \left(i\right)=\uparrow$ and $\sigma \left(i\right)=\downarrow$ have positive probability, update $i$ according to the equation

where $t$ is time, and $u_t$ is a random real number in $[0,1]$ chosen according to the uniform distribution where all $u_t$ 's are chosen independently of each other.

It is easy to demonstrate using the three equations that for all possible $\sigma ,\tau$ , and $i$ , formula [link] holds given $\sigma \le \tau$ . Essentially, we have 5 possible cases:

1.) If $i$ is chosen to be a box in $\sigma$ such that ${\sigma }_{\downarrow }^i$ is not a valid YD, then ${\tau }_{\downarrow }^i$ is not a valid YD either, since $\sigma \le \tau$ . Therefore $\pi \left({\sigma }_{\downarrow }^i\right)=0$ and $\pi \left({\tau }_{\downarrow }^i\right)=0$ . Formula [link] becomes $0=0$ .

2.) If $i$ is chosen to be a box such that both ${\sigma }_{\downarrow }^i$ and ${\sigma }_{\uparrow }^i$ are YD's, but ${\tau }_{\downarrow }^i$ is not a valid YD, then