ON THE LENGTH OF THE LONGEST INCREASING

SUBSEQUENCE IN A RANDOM PERMUTATION

Béla Bollobás and Svante Janson

Dedicated to Paul Erdős on his eightieth birthday.

Abstract. Complementing the results claiming that the maximal length L_{n} of an increasing subsequence in a random permutation of {1, 2, …, n} is highly concentrated, we show that L_{n} is not concentrated in a short interval: sup_{l} P(l ≤ L_{n} ≤ l + n^{1/16} log^{−3/8} n) → 0 as n → ∞.

1. Introduction

Ulam [9] proposed the study of L_{n}, the maximal length of an increasing subsequence of a random permutation of the set [n] = {1, 2, …, n}. Hammersley [4], Logan and Shepp [7], and Vers̆ik and Kerov [10] proved that E L_{n} ∼ 2\sqrt{n} and

L_{n}/\sqrt{n} ⟶^{p} 2 as n → ∞.  (1.1)

Frieze [3] showed that the distribution of L_{n} is sharply concentrated about its mean; his result was improved by Bollobás and Brightwell [2], who in particular proved that

Var(L_{n}) = O(n^{1/2}(log n/ log log n)^{2}).  (1.2)

(The log factors have recently been removed by Talagrand [8].) Somewhat surprisingly, it is not known that the distribution of L_{n} is not much more concentrated than claimed by (1.2). In fact, it has not even been ruled out that if w(n) → ∞ then P(|L_{n} − E L_{n}| < w(n)) → 0 as n → ∞. Our aim in this paper is to rule out this possibility for a fairly fast-growing function w(n), and to give a lower bound for Var(L_{n}), complementing (1.2).

Theorem 1.

P(|L_{n} − E L_{n}| ≤ n^{1/16} log^{−3/8} n) → 0 as n → ∞.

More generally, if a_{n} and b_{n} are any numbers such that

inf P(a_{n} ≤ L_{n} ≤ b_{n}) > 0, then (b_{n} − a_{n})/n^{1/16} log^{−3/8} n → ∞.

In particular, for sufficiently large n,

Var L_{n} ≥ n^{1/8} log^{−3/4} n.

There is still a wide gap between the upper and lower bound, and there is no reason to believe that the bounds given here are the best possible. In fact, a boot-strap argument

Typeset by AMS-TEX

Second author supported by the Göran Gustafsson Foundation for Research in Natural Sciences and Medicine

suggests that the range of variation is at least about n^{1/10}, see Theorem 2 below, and it is quite possible that the upper bound in (1.2) is sharp up to logarithmic factors, as conjectured in [2].

It is well-known that L_{n} also can be defined as the height of the random partial order defined as follows. Consider the unit square Q = [0, 1]^{2} with the coordinate order. Thus for (x, y), (x′, y′) ∈ Q set (x, y) ≤ (x′, y′) if and only if x ≤ x′ and y ≤ y′, let (ξ_{i})_{i=1}^{∞} be independent, uniformly distributed random points in Q and consider the induced partial order on the set (ξ_{i})_{i=1}^{n}.

Let μ > 0 be a constant and let m be the Lebesque measure in Q. Let us regard a Poisson process with intensity μdm in Q as a random subset of Q. Equivalently, let N be independent of (ξ_{i})_{1}^{∞}, with distribution Po(μ), and take the set {ξ_{i} : 1 ≤ i ≤ N}. Write H_{μ} for the height of the induced partial order on this set.

In [2] the proof of (1.2) was based on a study of H_{n}. In particular they proved that

P(|H_{n} − E H_{n}| > K_{1}λ\frac{n^{1/4} log n}{log log n}) ≤ e^{−λ^{2}}  (1.3)

for some constant K_{1}, every n ≥ 3 and every λ with 1 ≤ λ ≤ n^{1/4}/ log log n. For larger λ their proof yields

P(|H_{n} − E H_{n}| > K_{2}λ^{2} log λ) ≤ e^{−λ^{2}}.  (1.4)

These inequalities hold for non-integer n as well: and that if n ≥ 3 and 1 ≤ λ ≤ n^{1/4}/ log log n, then for every μ ≤ n, we have

P(|H_{μ} − E H_{μ}| > K_{3}λ\frac{n^{1/4} log n}{log log n}) ≤ e^{−λ^{2}}.  (1.5)

It is rather curious that our proof of a lower bound will use these results together with, as well as the following estimate from [2]:

0 ≤ 2n^{1/2} − E H_{n} ≤ K_{4}n^{1/4} log^{3/2} n/ log log n.  (1.6)

Remark. It is shown in [2] that (1.3) holds for L_{n} as well. (The same is true for (1.4) and (1.5).) Similarly, Theorem 1 holds for H_{n} too; this follows from the proof of Theorem 1 below, with a few simplifications.

The variables L_{n} and H_{n} may be defined, more generally, for random subsets of the d-dimensional cube [0, 1]^{d}. The results in [2] include this generalization, and it would be interesting to find lower bounds for the variance. Unfortunately, and somewhat surprisingly, the method used here does not work when d ≥ 3. We try to explain this failure at the end of the paper.

2. Proof of Theorem 1

The idea behind the proof is that L_{n} essentially depends only on the points in a strip of measure n^{−α} for some α > 0 (α = 1/8 if we ignore logarithmic factors). The number of points in this strip is approximately Poisson distributed with expectation n^{1−α}; hence the random variation of this number is of order n^{(1−α)/2} and the relative variation is n^{−(1−α)/2}. This ought to correspond to a relative variation in the height of the same order n^{−(1−α)/2}, ignoring the further variation due to the random position of the points, which would give a variation of order at least n^{1/2} · n^{−(1−α)/2} = n^{α/2}.

We introduce some notation. For a Borel set S ⊂ Q, let

N_{n}(S) = |{i ≤ n : ξ_{i} ∈ S}|

be the number of those of our n random points that lie in S, and let L_{n}(S) be the height of the partial order defined by these N_{n}(S) points; similarly, let H_{n}(S) be the height of the partial order defined by the restriction of our Poisson process to S. Finally, let S_{δ} = {(x, y) ∈ Q : |x − y| ≤ δ} be the strip of width 2δ along the diagonal. We shall deduce our theorem from two lemmas. The first of these claims that the height only depends on the points in S_{δ} for a fairly small value of δ.

Lemma 1. If K is sufficiently large, then with δ_{n} = Kn^{−1/8} log^{3/4}n (log log n)^{−1/2} we have

P(L_{n} ≠ L_{n}(S_{δ_{n}})) → 0 as n → ∞.

Proof. We claim that K = max(3K_{3}^{1/2}, 2K_{4}^{1/2}) will do, where K_{3} and K_{4} are the constants in (1.5) and (1.6). In fact, we shall prove slightly more than claimed, namely that the probability that the set {ξ_{i} : 1 ≤ i ≤ n} contains a point ξ_{i} ∉ S_{δ_{n}} that belongs to a maximal chain is o(1). Since the probability that a Poisson process Ξ in Q with intensity n has exactly n points with probability at least e^{−1}n^{−1/2}, it suffices to show that the corresponding probability for the Poisson process Ξ is o(n^{−1/2}).

Let M be the number of points in Ξ \ S_{δ} that belong to a maximal chain in Ξ. Then

M = ∑_{ξ∈Ξ} f(ξ, Ξ),

where

f(ξ, Ξ) = I(ξ ∉ S_{δ}) · I(ξ belongs to a maximal chain in Ξ).

Hence, using an easily proved formula for Poisson processes (see, e.g., [5, Lemma 2.1], and [6, Lemma 10.1 and Exercise 11.1]),

E M = E ∑_{ξ∈Ξ} f(ξ, Ξ) = ∫_{Q} E f(z, Ξ ∪ {z})n dm(z)

= ∫_{Q\S_{δ}} P(z belongs to a maximal chain in Ξ ∪ {z})n dm(z).  (2.1)

Fix z = (x, y) ∉ S_{δ} and let s = (x + y)/2, t = (x − y)/2, Q_{1} = [0, x] × [0, y] and Q_{2} = [x, 1] × [y, 1]. Then, writing |R| for the area of a set R ⊂ Q, we have

|Q_{1}|^{1/2} + |Q_{2}|^{1/2} = (s^{2} − t^{2})^{1/2} + ((1 − s)^{2} − t^{2})^{1/2}

≤ s − \frac{t^{2}}{2s} + 1 − s − \frac{t^{2}}{2(1 − s)}

= 1 − \frac{t^{2}}{2s(1 − s)}

≤ 1 − 2t^{2}

≤ 1 − \frac{1}{2}δ^{2}.

The random variables H_{n}(Q_{1}) and H_{n}(Q_{2}) have the same distributions as H_{μ_{1}} and H_{μ_{2}}, respectively, with μ_{i} = n|Q_{i}|, i = 1, 2. Setting δ = δ_{n}, inequality (1.6) implies that if n is large enough,

E H_{μ_{1}} + E H_{μ_{2}} ≤ 2μ_{1}^{1/2} + 2μ_{2}^{1/2} ≤ 2n^{1/2} − n^{1/2}δ_{n}^{2} ≤ E H_{n} − 1 − \frac{1}{2}n^{1/2}δ_{n}^{2}.

Hence, by applying (1.5) with λ = (2 log n)^{1/2}, we find that

P(z belongs to a maximal chain in Ξ ∪ {z}) = P(H_{n}(Q_{1}) + H_{n}(Q_{2}) + 1 ≥ H_{n})
≤ P(H_{μ_{1}} ≥ E H_{μ_{1}} + \frac{1}{6}n^{1/2}δ_{n}^{2}) + P(H_{μ_{2}} ≥ E H_{μ_{2}} + \frac{1}{6}n^{1/2}δ_{n}^{2})
+ P(H_{n} ≤ E H_{n} − \frac{1}{6}n^{1/2}δ_{n}^{2})
≤ 3 exp(−2 log n) = 3n^{−2}.

Consequently, (2.1) yields E M ≤ 3n^{−1}, and the result follows. □

Lemma 2. Suppose that δ_{n} ↘ 0 and that P(L_{n} ≠ L_{n}(S_{δ_{n}})) → 0 as n → ∞. If (α_{n}) is any sequence with α_{n} = o(δ_{n}^{−1/2}) then

sup_{x} P(|L_{n} − x| ≤ α_{n}) → 0 as n → ∞.

Proof. It is convenient to use couplings, and we begin by recalling the relevant definitions. A coupling of two random variables X and Y (possibly defined on different probability spaces), is a pair of random variables (X′, Y′) defined on a common probability space such that X′ =^{d} X and Y′ =^{d} Y. The notion of coupling depends only on the distributions of X and Y, so we may as well talk about a coupling of two distributions (which can be formulated as finding a joint distribution with given marginals).

We also define the total variation distance of two random variables X and Y (or, more properly, of their distributions L(X) and L(Y)) as

d_{T V} (X, Y) = sup_{A} | P(X ∈ A) − P(Y ∈ A)|,  (2.2)

taking the supremum over all Borel sets A. If (X′, Y′) is a coupling of X and Y then, clearly, d_{T V} (X, Y) = d_{T V} (X′, Y′) ≤ P(X′ ≠ Y′). Conversely, it is easy to construct a coupling of X and Y such that equality holds (such couplings are known as maximal couplings). Thus

d_{T V} (X, Y) = min P(X′ ≠ Y′),  (2.3)

where the minimum ranges over all couplings of X and Y. Moreover, provided the probability space where X is defined is rich enough, there exists a maximal coupling (X′, Y′) of X and Y with X′ = X.

We may assume that δ_{n} < 1 and α_{n} ≥ δ_{n}^{−1/4} → ∞. (All limits in the proof are taken as n → ∞.)

Let m = m(n) = ⌈6α_{n}\sqrt{n}⌉ ≤ 7α_{n}\sqrt{n}, and let μ = μ(n) = |S_{δ_{n}}|; thus

δ_{n} ≤ μ ≤ 2δ_{n}.

We use the facts that, for any n, p, λ_{1}, λ_{2},

d_{T V} (Bi(n, p), Po(np)) ≤ p

and

d_{T V} (Po(λ_{1}), Po(λ_{2})) ≤ |λ_{1} − λ_{2}|/ max(λ_{1}, λ_{2})^{1/2},

see e.g. [1, Theorems 2.M and 1.C]. Hence

d_{T V} (N_{n}(S_{δ_{n}}),N_{n+m}(S_{δ_{n}})) = d_{T V} (Bi(n, μ), Bi(n + m, μ))
≤ d_{T V} (Bi(n, μ), Po(nμ)) + d_{T V} (Po(nμ), Po((n + m)μ))
+ d_{T V} (Po((n + m)μ), Bi(n + m, μ))
≤ μ + mμ/(nμ)^{1/2} + μ
= mn^{−1/2}μ^{1/2} + 2μ ≤ 7\sqrt{2}α_{n}δ_{n}^{1/2} + 4δ_{n} ≤ 14α_{n}δ_{n}^{1/2}.

Choose a maximal coupling (N′_{n}, N′_{n+m}) of N_{n}(S_{δ_{n}}) and N_{n+m}(S_{δ_{n}}), and let (ξ′_{i})_{i=1}^{∞} be a sequence of independent random points, uniformly distributed in S_{δ_{n}}; assume also that (ξ′_{i}) is independent of (N′_{n}, N′_{n+m}). Let L′(N) be the height of the partial order defined by {ξ′_{i} : i ≤ N}. Then (L′(N′_{n}), L′(N′_{n+m})) is a coupling of L_{n}(S_{δ_{n}}) and L_{n+m}(S_{δ_{n}}), and thus

d_{T V} (L_{n}(S_{δ_{n}}), L_{n+m}(S_{δ_{n}})) ≤ P(L′(N′_{n}) ≠ L′(N′_{n+m}))
≤ P(N′_{n} ≠ N′_{n+m}) = d_{T V} (N_{n}(S_{δ_{n}}), N_{n+m}(S_{δ_{n}}))
≤ 14α_{n}δ_{n}^{1/2}.

Furthermore, using L_{n+m}(S_{δ_{n+m}}) ≤ L_{n+m}(S_{δ_{n}}) ≤ L_{n+m}, we see that

d_{T V} (L_{n}, L_{n+m})
≤ P(L_{n} ≠ L_{n}(S_{δ_{n}})) + P(L_{n+m} ≠ L_{n+m}(S_{δ_{n}})) + d_{T V} (L_{n}(S_{δ_{n}}), L_{n+m}(S_{δ_{n}}))
≤ P(L_{n} ≠ L_{n}(S_{δ_{n}})) + P(L_{n+m} ≠ L_{n+m}(S_{δ_{n+m}})) + 14α_{n}δ_{n}^{1/2}
→ 0.

Hence a maximal coupling (L′_{n}, L′_{n+m}) of L_{n} and L_{n+m} satisfies P(L′_{n} ≠ L′_{n+m}) → 0.

We next define another coupling of L_{n} and L_{n+m}, now trying to push the variables apart. Observe that necessarily nδ_{n} → ∞, since otherwise, for some C < ∞ and arbitrarily large n,

E L_{n}(S_{δ_{n}}) ≤ E N_{n}(S_{δ_{n}}) = n|S_{δ_{n}}| ≤ 2nδ_{n} ≤ 2C,

which contradicts L_{n}/\sqrt{n} ⟶^{p} 2 and P(L_{n} ≠ L_{n}(S_{δ_{n}})) → 0. Hence m = O(α_{n}n^{1/2}) = o(δ_{n}^{−1/2}n^{1/2}) = o(n).

In particular, we may assume that n > 3m. Set Q_{1} = [0, \frac{m}{3n}]^{2} and Q_{2} = (\frac{m}{3n}, 1]^{2}. Then

L_{n+m} ≥ L_{n+m}(Q_{1}) + L_{n+m}(Q_{2}).  (2.4)

Moreover, N_{n+m}(Q_{1}) ∼ Bi(n+m, (\frac{m}{3n})^{2}) with an expectation of (n+m)(\frac{m}{3n})^{2} > \frac{m^{2}}{9n} ≥ 4α_{n}^{2}; and it follows from Chebyshev’s inequality, that

P(N_{n+m}(Q_{1}) ≥ 2α_{n}^{2}) → 1.  (2.5)

Since the distribution of L_{n+m}(Q_{1}) conditional on N_{n+m}(Q_{1}) = ν equals the distribution of L_{ν} for any ν ≥ 1, we obtain from (1.1) that

P(L_{n+m}(Q_{1}) > 2α_{n}) → 1.  (2.6)

Similarly, n + m − N_{n+m}(Q_{2}) ∼ Bi(n + m, 1 − (1 − \frac{m}{3n})^{2}) with expectation

(n + m)(2\frac{m}{3n} − \frac{m^{2}}{9n^{2}} ) = (\frac{2}{3} + o(1))m,

and thus

P(N_{n+m}(Q_{2}) ≥ n) = P(n + m − N_{n+m}(Q_{2}) ≤ m) → 1.  (2.7)

We define L′′_{n} to be the height of the partial order defined by the first n of ξ_{1}, ξ_{2}, … that fall in Q_{2}; obviously L′′_{n} =^{d} L_{n}, so (L′′_{n}, L_{n+m}) is a coupling of L_{n} and L_{n+m}. Moreover, if N_{n+m}(Q_{2}) ≥ n, then L_{n+m}(Q_{2}) ≥ L′′_{n}, and thus (2.4), (2.6), (2.7) yield

P(L_{n+m} > L′′_{n} + 2α_{n}) → 1.  (2.8)

Combining this coupling with a maximal coupling (L′_{n+m}, L′_{n}) of L_{n+m} and L_{n} such that L′_{n+m} = L_{n+m}, we obtain a coupling (L′_{n}, L′′_{n}) of L_{n} with itself, i.e. two random variables

L′_{n} and L′′_{n} with L′_{n} =^{d} L′′_{n} =^{d} L_{n}, such that

P(L′_{n} > L′′_{n} + 2α_{n}) ≥ P(L_{n+m} > L′′_{n} + 2α_{n}) − P(L_{n+m} ≠ L′_{n}) → 1.

Finally we observe that for any real x,

P(L′_{n} > L′′_{n} + 2α_{n}) ≤ P(L′_{n} > x + α_{n}) + P(L′′_{n} < x − α_{n}) = P(|L_{n} − x| > α_{n})

and thus

sup_{x} P(|L_{n} − x| ≤ α_{n}) ≤ 1 − P(L′_{n} > L′′_{n} + α_{n}) → 0.  □

Theorem 1 follows immediately from the lemmas.

3. Further remarks

Note that the proof of Theorem 1 uses the concentration results in [2], and that stronger concentration results would imply a stronger version of Theorem 1, i.e. less concentration than given above. This leads to the following result, which shows that, at least for some n, the distribution of H_{n} is not strictly concentrated (with, say, exponentially decreasing tails) with a variation of much less than n^{−1/10}. (For simplicity we consider here H_{n}; presumably the same result is true for L_{n}.)

Theorem 2. If ε > 0 is sufficiently small, then there exist infinitely many n such that for some m ≤ n we have

P(|H_{m} − E H_{m}| > εn^{1/10}) > n^{−2}.

Proof. Assume on the contrary, and somewhat more generally, that for some γ, 0 < γ < 1/2, and all large n,

P(|H_{m} − E H_{m}| > n^{γ}) ≤ n^{−2}, m ≤ n.  (3.1)

The argument in the proof of [2, Theorem 9] then yields

2n^{1/2} − E H_{n} = O(n^{γ})  (3.2)

and Lemma 1 holds for H_{n}, by the argument above, with

δ_{n} = Kn^{γ/2−1/4},  (3.3)

provided K is large enough. Hence Lemma 2 (for H_{n}) shows that

P(|H_{n} − E H_{n}| ≤ α_{n}) → 0  (3.4)

whenever α_{n} = o(δ_{n}^{−1/2}), i.e., when

α_{n}n^{γ/4−1/8} → 0.  (3.5)

If γ < 1/10, we may take α_{n} = n^{γ}, which then satisfies (3.5), and obtain a contradiction from (3.1) and (3.4). In order to obtain the slightly stronger statement in the theorem, we let γ = 1/10 and note that if

P(|H_{n} − E H_{n}| > εn^{1/10}) ≤ n^{−2} < 1/2  (3.6)

for every ε > 0 and n ≥ n(ε), then there exists a sequence ε_{n} → 0 such that

P(|H_{n} − E H_{n}| > ε_{n}n^{1/10}) < 1/2.  (3.7)

We now choose α_{n} = ε_{n}n^{1/10}, which satisfies (3.5), and obtain a contradiction from (3.4) and (3.7). Hence either (3.1) or (3.6), for some ε > 0, fails for infinitely many n, which proves the result. □

Finally, let us see what happens when we try to generalize the results to the random d-dimensional order defined by random points in Q_{d} = [0, 1]^{d}. Lemma 1 holds, with

δ_{n} = Kn^{−1/4d} log^{3/4}n (log log n)^{−1/2},  (3.8)

by essentially the same proof; we now define S_{δ} = {(x_{i})^{d} : |x_{i} − x_{j}| ≤ δ, i < j}, and note that |S_{δ}| ≍ δ^{d−1}. For Lemma 2, however, we need

α_{n} = o(n^{1/d−1/2}δ_{n}^{−(d−1)/2}),  (3.9)

in which case we may take m = Kn^{1−1/d}α_{n} for some large K. However, (3.8) and (3.9) imply α_{n} = o(n^{(7−3d)/8d}) = o(1) for d ≥ 3, so we do not obtain any result at all. (We also need α_{n} ≥ 1). The method of Theorem 2 yields no result either: we obtain δ_{n} = Kn^{γ/2−1/2d} and by (3.9) we have

α_{n} = o(n^{(3−d)/4d−γ(d−1)/4}),  (3.10)

which again contradicts α_{n} ≥ 1 for any γ > 0 when d > 3.

We can explain this failure in terms of the heuristics at the beginning of Section 2. We still have a relative variation of the number of points in the strip S_{δ} of order n^{−(1−α)/2}, for some α > 0, but this translates to a variation of the height of order only n^{1/d−1/2+α/2}, which does not give any non-trivial result (α is rather small). Of course, this does not preclude the possibility that there is a substantial variation of the height due to the random position of points in the strip.

References

1. A. D. Barbour, L. Holst and S. Janson, Poisson Approximation, Oxford Univ. Press, Oxford, 1992.

2. B. Bollobás and G. Brightwell, The height of a random partial order: concentration of measure, Ann. Appl. Probab. 2 (1992), 1009–1018.

3. A. Frieze, On the length of the longest monotone subsequence in a random permutation, Ann. Appl. Probab. 1 (1991), 301–305.

4. J.M. Hammersley, A few seedlings of research, Proc. 6th Berkeley Symp. Math. Stat. Prob. (1972), Univ. of California Press, 345–394.

5. S. Janson, Random coverings in several dimensions, Acta Math. 156 (1986), 83–118.

6. O. Kallenberg, Random Measures, Akademie-Verlag, Berlin, 1983.

7. B.F. Logan and L.A. Shepp, A variational problem for Young tableaux, Advances in Mathematics 26 (1977), 206–222.

8. Michel Talagrand, Concentration of measure and isoperimetric inequalities in product spaces (to appear).

9. S.M. Ulam, Monte Carlo calculations in problems of mathematical physics, Modern Mathematics for the Engineer (1961), E.F. Beckenbach Ed., McGraw Hill, New York.

10. A.M. Vers̆ik and S.V. Kerov, Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux, Dokl. Akad. Nauk. SSSR 233 (1977), 1024–1028. (Russian)

Béla Bollobás, Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, 16 Mill Lane, Cambridge CB2 1SB, England

  E-mail address: B.Bollobas@pmms.cam.ac.uk

Svante Janson, Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden

  E-mail address: svante.janson@math.uu.se