TAOCP 5.1.4 Exercise 40

Section 5.1.4: Tableaux and Involutions

Exercise 40. [HM43] Suppose a random Young tableau has been constructed by successively placing the numbers $1, 2, \ldots, n$ in such a way that each possibility is equally likely when a new number is placed. For example, the tableau (1) would be obtained with probability $\frac{1}{2} \cdot \frac{1}{4} \cdot \frac{1}{4} \cdot \frac{1}{4} \cdots$ using this procedure. The resulting shape $(n_1, n_2, \ldots, n_m)$ will have $m \approx \sqrt{6n}$ and $\sqrt{k} + \sqrt{n_{k+1}} \approx \sqrt{m}$ for $0 \le k \le m$.

Verified: no
Solve time: 1h54m

Solution to Exercise 40 (HM43)

We analyze the random process that builds a standard Young tableau by inserting the numbers (1,2,\ldots,n) one at a time. At each step the next number is placed in an outer corner of the current diagram, each corner being chosen with equal probability. We want the asymptotic shape ((n_1,n_2,\ldots,n_m)) of the resulting Young diagram.

1. Continuous‑time embedding
Instead of the discrete process, consider the following continuous‑time Markov chain. Start with the empty diagram. Attach an independent exponential clock of rate (1) to every outer corner of the current diagram. When a clock rings, add the next box at that corner, remove its clock, and attach new clocks of rate (1) to the newly created outer corners. Because all active clocks always have the same rate, the probability that a particular corner is the next to fire is exactly (1/(\text{number of corners})). Hence the sequence of shapes obtained in this continuous‑time process has the same distribution as the sequence in the original discrete process. In particular, the shape after (n) discrete steps is distributed exactly as the shape at the instant the (n)-th box is added in the continuous‑time process.

2. Connection to last‑passage percolation
The continuous‑time corner growth model described above is equivalent to a directed last‑passage percolation model on (\mathbb{Z}^2) with i.i.d. exponential((1)) weights. To see this, assign to each lattice point ((i,j)) ((i,j\ge 1)) an independent exponential((1)) waiting time. The time needed to add the box at position ((i,j)) (with (i) the column index and (j) the row index) is the maximum weight of a directed path from ((1,1)) to ((i,j)) using steps ((1,0)) and ((0,1)). The shape at time (t) is the set of boxes whose passage time is (\le t); its outer boundary consists of the points where the passage time equals (t).

3. Limit shape
A fundamental result of Rost (1981) and Gärtner (1988) on exponential last‑passage percolation states that, as (t\to\infty), the random set of points reached by time (t), when scaled by (t), converges almost surely to a deterministic set whose boundary is the curve [ \sqrt{x} + \sqrt{y} = \sqrt{t}\qquad (0\le x\le t,;0\le y\le t), ] where (x) measures the horizontal extent (row length) and (y) the vertical extent (row index). In other words, if (h(x,t)) denotes the height of the boundary at coordinate (x), then [ h(x,t) = (\sqrt{t} - \sqrt{x})^2\quad\text{for }0\le x\le t. ]

4. Area and number of rows
The total number of boxes (n) is the area under the boundary curve. Computing the area: [ n = \int_0^t (\sqrt{t} - \sqrt{x})^2,dx = \int_0^t (t - 2\sqrt{t}\sqrt{x} + x),dx = t^2 - 2\sqrt{t}\cdot\frac{2}{3}t^{3/2} + \frac{1}{2}t^2 = \frac{t^2}{6}. ] Hence (t \sim \sqrt{6n}). The number of rows (m) is the (y)-intercept of the boundary, i.e. the value of (h(0,t)=t). Therefore [ m \sim t \sim \sqrt{6n}. ]

5. Row lengths
For a given row index (k) (with (0\le k\le m)), the length (n_k) of that row satisfies, by the limit shape, [ \sqrt{k} + \sqrt{n_k} \approx \sqrt{t} \approx \sqrt{m}. ] The exercise uses (n_{k+1}) instead of (n_k); this is an inconsequential shift of (1) in the index for large (k).

Conclusion
The random Young tableau constructed by successively placing (1,2,\ldots,n) with uniform choice of an outer corner at each step has, with high probability, a shape ((n_1,n_2,\ldots,n_m)) satisfying [ m \approx \sqrt{6n}\qquad\text{and}\qquad \sqrt{k} + \sqrt{n_{k+1}} \approx \sqrt{m}\quad (0\le k\le m). ]