CFTP Sampling of q-Weighted Partitions     misc

Coupling From The Past (CFTP) is an algorithm for exact sampling from a target distribution. Here we sample partitions $\lambda$ contained in an $M \times N$ rectangle with probability proportional to $q^{|\lambda|}$, where $|\lambda|$ is the number of boxes.

Parameters:

• $N$: Width of the bounding rectangle
• $a = M/N$: Aspect ratio (so $M = \lfloor aN \rfloor$)
• $q$: Weight parameter. When $q < 1$, smaller partitions are favored; when $q > 1$, larger partitions are favored.

Glauber Dynamics: At each step, pick a corner (addable or removable position) uniformly at random:

• If addable: add box with probability $q/(1+q)$
• If removable: remove box with probability $1/(1+q)$

CFTP: Run two coupled chains from extremal states (empty and full rectangle). When they coalesce, we have an exact sample from the stationary distribution.

Limit Shape: As $N \to \infty$ with $q = e^{-\gamma/N}$ for fixed $\gamma > 0$, the rescaled partition boundary converges to a deterministic curve given by the implicit equation: $$A e^{-\gamma y} + B e^{-\gamma x} = 1$$ where $A = \frac{1-e^{-\gamma}}{1-e^{-\gamma(1+a)}}$ and $B = \frac{1-e^{-\gamma a}}{1-e^{-\gamma(1+a)}}$. The red curve shows this limit shape.

Reference: A. Vershik, "Statistical mechanics of combinatorial partitions, and their limit shapes," Functional Analysis and Its Applications 30 (1996), 90-105.