q-RSK Sampling of Domino Tilings of the Aztec Diamond     domino-tilings

Setup: The Aztec diamond $\mathcal{A}_n$ of order $n$ consists of all unit squares $[i, i+1] \times [j, j+1]$ with $|i| + |j| < n$. It contains $2n(n+1)$ unit squares and is tiled by $n(n+1)$ dominoes.

Domino Types: Each domino is classified by orientation and parity:

• North (N): vertical domino with black square on top
• South (S): vertical domino with white square on top
• East (E): horizontal domino with black square on right
• West (W): horizontal domino with white square on right

The Shuffling Map $\mathcal{A}_n \to \mathcal{A}_{n+1}$:

1. Deletion: Find all $2 \times 2$ blocks containing exactly two dominoes that form either:
   • Two horizontal dominoes stacked (one N, one S), or
   • Two vertical dominoes side-by-side (one E, one W)
   These are called bad blocks. Delete all dominoes in bad blocks.
2. Sliding: Each remaining domino slides outward by one unit in its natural direction: $$\begin{aligned} \text{N dominoes} &\to \text{slide up (} +y \text{)} \\ \text{S dominoes} &\to \text{slide down (} -y \text{)} \\ \text{E dominoes} &\to \text{slide right (} +x \text{)} \\ \text{W dominoes} &\to \text{slide left (} -x \text{)} \end{aligned}$$
3. Creation: After sliding, empty $2 \times 2$ blocks appear. Each block is filled with exactly one of two choices:
   • Two horizontal dominoes (N on top, S on bottom), or
   • Two vertical dominoes (W on left, E on right)
   For uniform random tilings, each choice is made independently with probability $\tfrac{1}{2}$.

Key Properties:

• The map is a $2^{n+1}$-to-1 correspondence from tilings of $\mathcal{A}_{n+1}$ to tilings of $\mathcal{A}_n$
• Uniform measure on $\mathcal{A}_n$ lifts to uniform measure on $\mathcal{A}_{n+1}$
• Starting from the unique tiling of $\mathcal{A}_0$ and shuffling $n$ times samples uniformly from $\mathcal{A}_n$

Reference: arXiv:math/9201305 (opens in new tab) — Elkies, Kuperberg, Larsen, Propp, "Alternating-Sign Matrices and Domino Tilings" (1992).

q-Whittaker Deformation (q > 0)

Key Insight: The q-deformation modifies only Step 3 (Creation). Steps 1 and 2 remain unchanged.

In the classical case, block-filling is deterministic: geometric constraints force a unique cascade. In the q-Whittaker case, particles have probabilistic "stickiness"—even when a particle could move, it might stay with probability depending on $q$.

Step 3': q-Weighted Creation

Empty 2×2 blocks form islands—consecutive positions where new dominoes must be placed. For each island $[k, m]$:

1. Sample Bernoulli bit: $B \sim \text{Bernoulli}\left(\dfrac{x_i y_j}{1 + x_i y_j}\right)$
2. Special case: If $B = 1$ and $k = 0$, all particles jump (fill all blocks with same orientation).
3. Otherwise, sample stopping position:
   • Compute $f_k = \dfrac{1 - q^{\lambda_k - \bar\nu_k + 1}}{1 - q^{\bar\nu_{k-1} - \bar\nu_k + 1}}$
   • Sample $U \sim \text{Uniform}[0,1]$. If $U < f_k$: stop at $k$
   • Else, for $s = k+1, \ldots, m$:
     • Compute $g_s = 1 - q^{\lambda_s - \mu_s + 1}$
     • Sample $U \sim \text{Uniform}[0,1]$. If $U < g_s$: stop at $s$
   • If no stop occurs: all particles jump
4. Fill blocks based on stopping position $s$:
   • Blocks at positions $k, \ldots, s-1$: orientation A (e.g., vertical EW pair)
   • Block at position $s$: orientation B (opposite, e.g., horizontal NS pair)
   • Blocks at positions $s+1, \ldots, m$: orientation A

Domino Orientation Mapping: The stopped particle creates a domain wall:

References:

• arXiv:1407.3764 (opens in new tab) — Betea, Bouttier, Nejjar, Vuletić, "The free boundary Schur process and applications I"
• arXiv:1504.00666 (opens in new tab) — Matveev, Petrov, "q-randomized Robinson-Schensted-Knuth correspondences and random polymers"