TAOCP 5.1.4 Exercise 29

Section 5.1.4: Tableaux and Involutions

Exercise 29. [HM25] Prove that a random permutation of $n$ elements has an increasing subsequence of length $\ge t$ with probability $\le \binom{n}{t}/t!$. This probability is $O(1/\sqrt{n})$ when $l = c\sqrt{n} + O(1)$, and $O(\exp(-c\sqrt{n}))$ when $l = 3\sqrt{n}$, $c = 6\ln 3 - 6$.

Verified: yes
Solve time: 1h15m

Solution

1. Upper bound for the probability

Let (\pi) be a uniformly random permutation of ({1,2,\dots,n}). For any fixed subset (S \subseteq {1,\dots,n}) of size (t), the values (\pi(i)) for (i \in S) are equally likely to appear in any of the (t!) possible orders. Exactly one of those orders is strictly increasing. Hence the probability that the restriction of (\pi) to (S) is an increasing subsequence is (1/t!).

Define the indicator random variable
[ X_S = \begin{cases} 1 & \text{if } \pi|S \text{ is strictly increasing},\ 0 & \text{otherwise}. \end{cases} ] Then (\Pr(X_S = 1) = 1/t!). The total number of increasing subsequences of length exactly (t) is
[ X = \sum{|S|=t} X_S. ] By linearity of expectation, [ \mathbb{E}[X] = \sum_{|S|=t} \frac{1}{t!} = \binom{n}{t}\frac{1}{t!}. ]

If (\pi) contains an increasing subsequence of length (\ge t), then it certainly contains one of length exactly (t) (take any (t) elements of that subsequence). Therefore the event ({\text{LIS} \ge t}) is contained in ({X \ge 1}). By Markov’s inequality, [ \Pr(\text{LIS} \ge t) \le \Pr(X \ge 1) \le \mathbb{E}[X] = \frac{\binom{n}{t}}{t!}. ]

2. Asymptotic behaviour of the bound

We analyse the quantity
[ B(n,t) = \frac{\binom{n}{t}}{t!} = \frac{n!}{t!^2,(n-t)!}. ]

Using Stirling’s formula in the form [ k! = \sqrt{2\pi k}\left(\frac{k}{e}\right)^k \left(1 + O!\left(\frac{1}{k}\right)\right), ] we obtain [ \frac{n!}{t!^2,(n-t)!} = \frac{\sqrt{2\pi n},(n/e)^n}{\bigl(\sqrt{2\pi t},(t/e)^t\bigr)^2 \cdot \sqrt{2\pi(n-t)},((n-t)/e)^{n-t}} \left(1+o(1)\right) ] [ = \frac{1}{2\pi}\sqrt{\frac{n}{t^2(n-t)}}; e^{,t}; \frac{n^n}{t^{2t}(n-t)^{n-t}} \left(1+o(1)\right). ]

Taking logarithms, [ \log B(n,t) = n\log n - n - 2(t\log t - t) - (n-t)\log(n-t) + (n-t) - \frac{1}{2}\log\bigl(2\pi t^2(n-t)/n\bigr) + o(1). ]

Assume (t = o(n)) (which holds for the regimes we study). Expand ((n-t)\log(n-t)): [ (n-t)\log(n-t) = n\log n - t\log n - t + \frac{t^2}{2n} + O!\left(\frac{t^3}{n^2}\right). ]

Substituting this expansion gives [ \log B(n,t) = n\log n - n - 2t\log t + 2t - \left(n\log n - t\log n - t + \frac{t^2}{2n}\right) - \frac{1}{2}\log\bigl(2\pi t^2(n-t)/n\bigr) + o(1) ] [ = t\log n - 2t\log t + 2t - \frac{t^2}{2n} - \frac{1}{2}\log\bigl(2\pi t^2(n-t)/n\bigr) + o(1). ]

Now write (t = \alpha\sqrt{n} + O(1)) with a constant (\alpha > 0). The (O(1)) term does not affect the leading asymptotic behaviour. Then (n-t = n - \alpha\sqrt{n} + O(1)), and [ \frac{t^2}{2n} = \frac{\alpha^2}{2} + O!\left(\frac{1}{\sqrt{n}}\right), ] [ \frac{1}{2}\log\bigl(2\pi t^2(n-t)/n\bigr) = \frac{1}{2}\log\bigl(2\pi \alpha^2 n\bigr) + o(1) = \frac{1}{2}\log n + O(1). ]

Thus [ \log B(n,t) = 2\alpha\sqrt{n}(1 - \log\alpha) - \frac{1}{2}\log n + O(1). ]

Exponentiating, [ B(n,t) = \Theta!\left(\frac{1}{\sqrt{n}}\right) \exp!\bigl(2\alpha\sqrt{n}(1 - \log\alpha)\bigr). ]

3. First regime: (t = c\sqrt{n} + O(1))

The bound is (O(1/\sqrt{n})) precisely when the exponential factor is constant, i.e. when (1 - \log c = 0). Hence (c = e). For this value, [ \Pr(\text{LIS} \ge t) \le B(n,t) = O!\left(\frac{1}{\sqrt{n}}\right). ]

4. Second regime: (t = 3\sqrt{n})

Here (\alpha = 3). The exponent becomes [ 2 \cdot 3\sqrt{n} (1 - \log 3) = 6\sqrt{n}(1 - \log 3) = -(6\log 3 - 6)\sqrt{n}. ] Let (c = 6\log 3 - 6). Then [ B(n,3\sqrt{n}) = O!\left(\frac{1}{\sqrt{n}} e^{-c\sqrt{n}}\right) = O!\left(e^{-c\sqrt{n}}\right), ] because the polynomial factor (1/\sqrt{n}) is dominated by the exponential decay. Hence [ \Pr(\text{LIS} \ge 3\sqrt{n}) = O!\left(e^{-c\sqrt{n}}\right) \quad \text{with } c = 6\log 3 - 6. ]

This completes the proof. ∎