CFTP Sampling of q-Weighted Partitions (General Boundary)     misc

Coupling From The Past (CFTP) is an algorithm for exact sampling from a target distribution. Here we sample partitions $\lambda$ contained in a given boundary partition $\mu$ with probability proportional to $q^{|\lambda|}$.

Boundary Types:

• Rectangle: $N \times M$ rectangle (all rows have length $N$)
• Staircase: Shape $(k, k-1, \ldots, 1)$ for a given $k$
• Custom: Specify any partition using notation like 50,40,30 or multiplicative form 50^3,40^2,10^5

Parameters:

• $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 uniformly at random:

• If addable (and within boundary): 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 partition and boundary partition). When they coalesce, we have an exact sample from the stationary distribution.

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