Aditya Makkar
Longest Increasing Subsequence

Introduction

Finding a longest increasing subsequence is a well-known problem in computer science (note that I use the article "a" instead of "the" because there could be multiple longest subsequences): Given a sequence {a1,…,an}\{a_1, \ldots, a_n\} of real numbers, we want to find a subsequence {ai1,…,aik}\{a_{i_1}, \ldots, a_{i_k}\} such that 0≤i1<⋯<ik≤n0 \le i_1 < \cdots < i_k \le n, ai1≤⋯≤aika_{i_1} \le \cdots \le a_{i_k}, and the subsequence is as long as possible. It has a very easy dynamic programming solution with a time complexity of O(n2)O(n^2) and a slightly more involved solution with a time complexity of O(nlog⁡n).O(n \log n). But we are not interested in these algorithms in this blog post.

We are interested in studying the asymptotics of the length of the longest increasing subsequences of a sequence whose elements are coming from a random permutation. This simple to state problem will take us on a beautiful journey touching topics from combinatorics and probability theory. In particular, we will get to see the very elegant technique of Poissonization.

Problem

Let us start by stating precisely what we are trying to prove. To do that we first define some notation. For any integer n≥1n \ge 1, let SnS_n be the group of permutations of order nn, i.e., it contains all permutations of {1,2,…,n}\{1, 2, \ldots, n\} and hence SnS_n contains n!n! elements. If π∈Sn\pi \in S_n then a subsequence of π\pi is a sequence {π(i1),…,π(ik)}\{\pi(i_1), \ldots, \pi(i_k)\} such that 1≤i1<⋯<ik≤n.1 \leq i_1 < \cdots < i_k \leq n. It is an increasing subsequence if π(i1)<⋯<π(ik)\pi(i_1) < \cdots < \pi(i_k) and similarly for the decreasing subsequence. Consider the uniform measure μn\mu_n on the discrete measurable space (Sn,2Sn)(S_n, 2^{S_n}), i.e., μn(π)=1/n!\mu_n(\pi) = 1 / n! for any π∈Sn.\pi \in S_n. For π∈Sn\pi \in S_n define Ln(π)L_n(\pi) to be the maximal length of an increasing subsequence of π\pi, i.e., Ln(π)L_n(\pi) is the largest kk such that there are integers 1≤i1<⋯<ik≤n1 \leq i_1 < \cdots < i_k \leq n so that π(i1)<⋯<π(ik).\pi(i_1) < \cdots < \pi(i_k). Similarly define Dn(π)D_n(\pi) to be the maximal length of a decreasing subsequence of π.\pi.

Since LnL_n is a random variable we can consider its expectation ℓn=E[Ln]\ell_n = \mathbb{E}[L_n] on the probability space (Sn,2Sn,μn).(S_n, 2^{S_n}, \mu_n). It can be explicitly written as

ℓn=1n!∑π∈SnLn(π).\begin{aligned} \ell_n = \frac{1}{n!} \sum_{\pi \in S_n} L_n(\pi).\end{aligned}

We want to study the limiting properties of the sequence {ℓn}n∈N.\{\ell_n\}_{n \in \mathbb N}. Specifically we will show that

ℓnn→γ almost surely\begin{aligned} \frac{\ell_n}{\sqrt{n}} \to \gamma \text{ almost surely}\end{aligned}

for some constant γ.\gamma. It is known that γ=2.\gamma = 2. We will not be showing this, but we will show that 1≤γ≤e.1 \le \gamma \le e.

Combinatorial results

We now prove some useful combinatorial results. The first result is called the Erdős–Szekeres theorem. We will need to prove lower and upper bounds for ℓn/n.\ell_n / \sqrt{n}.

Theorem 1 [Erdős–Szekeres theorem]: In any sequence {a1,a2,…,amn+1}\{a_1, a_2, \ldots, a_{mn+1}\} of mn+1mn+1 distinct real numbers, there exists either an increasing subsequence ai1<⋯<aim+1a_{i_1} < \cdots < a_{i_{m+1}} of length m+1m+1, where i1<⋯<im+1i_1 < \cdots < i_{m+1}, or a decreasing subsequence aj1>⋯>ajn+1a_{j_1} > \cdots > a_{j_{n+1}} of length n+1n+1, where j1<⋯<jn+1.j_1 < \cdots < j_{n+1}.

For 1≤i≤mn+11 \leq i \leq mn+1 define tit_i to be the length of a longest increasing subsequence starting at aia_i, i.e., the first element of a longest increasing subsequence must be aia_i and the rest of the aa's must have indices greater than i.i.

If ti≥m+1t_i \geq m+1 for some ii then we are done since we then have an increasing subsequence of length m+1,m+1, so assume ti≤mt_i \leq m for all i.i. Since ti≥1t_i \geq 1, pigeonhole principle implies that there is some integer 1≤k≤m1 \leq k \leq m such that ti=kt_i = k for at least n+1n+1 ii's. Let ti=kt_i = k for all i∈(j1<⋯<jn+1).i \in (j_1 < \cdots < j_{n+1}). Now note that if ajl<ajl+1a_{j_l} < a_{j_{l+1}} for some 1≤l≤n1 \leq l \leq n, then we would obtain an increasing subsequence of length k+1k+1 starting at ajla_{j_l} because there is an increasing subsequence of length kk starting at ajl+1.a_{j_{l+1}}. But this contradicts the fact that tjl=k,t_{j_l} = k, and thus ajl>ajl+1a_{j_l} > a_{j_{l+1}} for all 1≤l≤n.1 \leq l \leq n. But now this gives us a decreasing subsequence aj1>⋯>ajn+1a_{j_1} > \cdots > a_{j_{n+1}} of length n+1.n+1.

The next two theorems prove lower and upper bounds for ℓn/n.\ell_n / \sqrt{n}.

Theorem 2: ℓn/n\ell_n / \sqrt{n} is lower bounded as follows: ℓn≥n for all n≥1.\begin{aligned} \ell_n \geq \sqrt{n} \text{ for all } n \geq 1.\end{aligned}
Theorem 1 implies that Ln(π)Dn(π)≥nL_n(\pi) D_n(\pi) \geq n for each π∈Sn.\pi \in S_n. Note that for each permutation π∈Sn\pi \in S_n there exists an inverse permutation π′\pi' such that Ln(π)=Dn(π′)L_n(\pi) = D_n(\pi'), and thus we can write ℓn\ell_n equivalently as ℓn=1n!∑π∈SnDn(π).\begin{aligned} \ell_n = \frac{1}{n!} \sum_{\pi \in S_n} D_n(\pi).\end{aligned} Therefore, averaging the two ways of computing the expectation ℓn\ell_n (Equations (1) and (4)) and using the AM-GM inequality we have
ℓn=1n!∑π∈SnL(π)+D(π)2≥1n!∑π∈SnL(π)D(π)≥1n!∑π∈Snn=n.\begin{aligned} \ell_n = \frac{1}{n!} \sum_{\pi \in S_n} \frac{L(\pi) + D(\pi)}{2} \geq \frac{1}{n!} \sum_{\pi \in S_n} \sqrt{L(\pi) D(\pi)} \geq \frac{1}{n!} \sum_{\pi \in S_n} \sqrt{n} = \sqrt{n}.\end{aligned}
Theorem 3: Upper bound: lim sup⁡n→∞ℓnn≤e.\begin{aligned} \limsup_{n \to \infty} \frac{\ell_n}{\sqrt{n}} \leq e.\end{aligned}

We start by getting an upper bound on the tail probabilities μn(Ln≥k)\mu_n(L_n \geq k) for 1≤k≤n1 \leq k \leq n by cleverly defining a random variable Xn,kX_{n,k}, writing its expectation in two different ways, and then comparing.

If π∈Sn\pi \in S_n and 1≤k≤n1 \leq k \leq n let Xn,k(π)X_{n,k}(\pi) be the number of increasing subsequences of π\pi which are of length k.k. These subsequences correspond exactly to those subsets S⊆{1,…,n}S \subseteq \{1, \ldots, n\} for which ∣S∣=k|S| = k and if S={i1<⋯<ik}S = \{i_1 < \cdots < i_k\} then π(i1)<⋯<π(ik).\pi(i_1) < \cdots < \pi(i_k). On the probability space (Sn,2Sn,μn)(S_n, 2^{S_n}, \mu_n), by the linearity of expectation, the expected value of Xn,kX_{n,k} is given by the number of ways to select subsets of {1,…,n}\{1, \ldots, n\} with size kk times the probability that a selection has all the elements in the increasing order. The number of ways is simply (nk)\binom{n}{k} and the probability is 1/k!1/k! and thus

E[Xn,k]=1k!(nk).\begin{aligned} \mathbb{E}[X_{n,k}] = \frac{1}{k!} \binom{n}{k}.\end{aligned}

The Taylor expansion of exe^x implies ex≥xk/k!.e^x \ge x^k / k!. Substituting x=kx = k in this inequality, we get k!≥(k/e)k.k! \geq (k/e)^k. Therefore, we get

E[Xn,k]=1k!(nk)=n(n−1)⋯(n−k−1)(k!)2≤nk(k/e)2k.\begin{aligned} \mathbb{E}[X_{n,k}] = \frac{1}{k!} \binom{n}{k} = \frac{n(n-1) \cdots (n-k-1)}{(k!)^2} \leq \frac{n^k}{(k/e)^{2k}}.\end{aligned}

Now for the discrete random variable Xn,kX_{n,k} we can also write

E[Xn,k]=∑i=0nμn(Xn,k≥i),\begin{aligned} \mathbb{E}[X_{n,k}] = \sum_{i=0}^n \mu_n(X_{n,k} \geq i),\end{aligned}

and thus μn(Xn,k≥1)≤E[Xn,k].\mu_n(X_{n,k} \geq 1) \leq \mathbb{E}[X_{n,k}]. Also note that Ln(π)≥kL_n(\pi) \geq k if and only if Xn,k(π)≥1.X_{n,k}(\pi) \geq 1. We thus get our tail probability,

μn(Ln≥k)=μn(Xn,k≥1)≤E[Xn,k]≤nk(k/e)2k.\begin{aligned} \mu_n(L_n \geq k) = \mu_n(X_{n,k} \geq 1) \leq \mathbb{E}[X_{n,k}] \leq \frac{n^k}{(k/e)^{2k}}.\end{aligned}

To make this more amenable to limiting analysis, fix an arbitrary δ>0\delta > 0 and let k=min⁡{⌈(1+δ)en⌉,n}k = \min\{\left\lceil(1+\delta)e\sqrt{n}\right\rceil, n\} in the inequality above to get

μn(Ln≥k)≤nk(k/e)2k≤(11+δ)2k≤(11+δ)2(1+δ)en.\begin{aligned} \mu_n(L_n \geq k) \leq \frac{n^k}{(k/e)^{2k}} \leq \left( \frac{1}{1+\delta} \right)^{2k} \leq \left( \frac{1}{1+\delta} \right)^{2(1+\delta)e\sqrt{n}}.\end{aligned}

Since Ln≤nL_n \leq n, we have

ℓn=E[Ln]≤μn(Ln<k)(1+δ)en+μn(Ln≥k)n≤(1+δ)en+O(e−cn)\begin{aligned} \ell_n = \mathbb{E}[L_n] \leq \mu_n(L_n < k) (1+\delta)e\sqrt{n} + \mu_n(L_n \geq k) n \leq (1+\delta)e\sqrt{n} + O(e^{-c\sqrt{n}})\end{aligned}

where cc is some positive constant that depends on δ.\delta.

Since δ\delta was arbitrary, we can let δ→0\delta \to 0 and then take lim sup⁡\limsup over nn to get (5).

Poissonization

To be able to show (2) we will draw a correspondence between this problem of longest increasing subsequences and a seemingly unrelated problem called the Poissonized version. This Poissonized version will allow us to use the powerful Subadditive Ergodic Theorem (Theorem 5 below) to show (2).

To this end, assume an underlying probability space (Ω,F,P)(\Omega, \mathcal{F}, \mathbb{P}) and let NN be a Poisson random measure on R+2\mathbb{R}_+^2 with mean measure given by the Lebesgue measure on R+2.\mathbb{R}_+^2. In other words N:Ω×B(R+2)→R‾+N:\Omega \times \mathcal B(\mathbb R_+^2) \to \overline{\mathbb R}_+ is a transition kernel from (Ω,F)(\Omega, \mathcal{F}) to (R+2,B(R+2))(\mathbb R_+^2, \mathcal B(\mathbb R_+^2)) with ∫ΩP(dω)N(ω,A)=Leb(A)\int_\Omega \mathbb P(\mathrm{d} \omega) N(\omega, A) = \text{Leb}(A) for any A∈B(R+2).A \in \mathcal B(\mathbb R_+^2). We can view the random process as a sequence {(Xi,Yi)}i≥1\{(X_i, Y_i)\} _ {i \geq 1} of independent random variables taking values in R+2\mathbb R _ + ^2 and having a uniform probability measure (more correctly, Lebesgue measure on (R+2,B(R+2))(\mathbb R_+^2, \mathcal B(\mathbb R_+^2))). If we let Rs,tR_{s,t} denote the rectangle with vertices (s,s),(s,t),(t,t)(s,s), (s,t), (t,t) and (t,s)(t,s), then for each outcome ω∈Ω\omega \in \Omega, we can think of having Poisson(Leb(Rs,t))\text{Poisson}(\text{Leb}(R_{s,t})) distributed number of such points inside the rectangle Rs,t.R_{s,t}.

For s<t∈[0,∞)s < t \in [0, \infty) let Zs,tZ_{s,t} be the random variable denoting the length of the longest increasing path lying in the rectangle Rs,tR_{s,t}, i.e., Zs,tZ_{s,t} is the largest integer kk for which there are points (X1,Y1),…,(Xk,Yk)(X_1,Y_1), \dots, (X_k, Y_k) in the Poisson process with s<X1<⋯<Xk<ts < X_1 < \cdots < X_k < t and s<Y1<⋯<Yk<t.s< Y_1 < \cdots < Y_k < t.

Let τ(n)\tau(n) be the smallest value of t∈[0,∞)t \in [0, \infty) for which there are nn points in R0,t.R_{0,t}. Let the nn points in R0,τ(n)R_{0, \tau(n)} be written as {(Xi,Yi)}1≤i≤n\{(X_i, Y_i)\}{1 \leq i \leq n} such that 0<X1<⋯<Xn≤τ(n)0 < X_1 < \cdots < X_n \leq \tau(n) (the inequalities are strict almost surely since they have continuous distributions). Let πn∈Sn\pi_n \in S_n be the unique permutation such that Yπn(1)<⋯<Yπn(n)Y_{\pi_n(1)} < \cdots < Y_{\pi_{n}(n)} (It is not difficult to see the existence and the uniqueness). Then

πn is a uniformly random sample of Sn, and Z0,τ(n)=Ln(πn).\begin{aligned} \pi_n \text{ is a uniformly random sample of } S_n \text{, and } Z_{0, \tau(n)} = L_n(\pi_n).\end{aligned}

The second claim is obvious from the definition of πn.\pi_n. The first claim is equivalent to showing that if U1,…,UnU_1, \ldots, U_n are i.i.d. random variables with a uniform distribution on [0,1][0,1] and if U(1),…,U(n)U_{(1)}, \ldots, U_{(n)} are the order statistics, i.e., U(k)U_{(k)} is the kthk^\text{th} smallest among U1,…,UnU_1, \ldots, U_n, then the probability that U(1),…,U(n)U_{(1)}, \ldots, U_{(n)} is the same as Uπ(1),…,Uπ(n)U_{\pi(1)}, \ldots, U_{\pi(n)} for some fixed π∈Sn\pi \in S_n is 1/n!.1/n!. But this is obvious from the independence of UiU_i's. The next theorem is from Durrett:

Theorem 4: τ(n)/n→1\tau(n) / \sqrt{n} \to 1 almost surely.
Let SnS_n be the number of points in R0,n.R_{0,\sqrt{n}}. Since
(R0,n∖R0,n−1)∩(R0,m∖R0,m−1)=∅\begin{aligned} (R_{0, \sqrt{n}} \setminus R_{0, \sqrt{n-1}}) \cap (R_{0, \sqrt{m}} \setminus R_{0, \sqrt{m-1}}) = \varnothing\end{aligned}
for n≠mn \neq m, the definition of a Poisson random measure implies {Sn−Sn−1}n≥1\{S_n - S_{n-1}\}_{n \geq 1} are independent Poisson random variables with mean 1.1. The strong law of large numbers now implies Sn/n→1S_n / n \to 1 almost surely. For any ε>0\varepsilon > 0 we can find an nn large enough such that Sn(1−ε)<n<Sn(1+ε)S_{n(1-\varepsilon)} < n < S_{n(1+\varepsilon)} but then this means n(1−ε)≤τ(n)≤n(1+ε)\sqrt{n(1-\varepsilon)} \leq \tau(n) \leq \sqrt{n(1+\varepsilon)} which is same as the statement of the theorem since ε\varepsilon was arbitrary.

This theorem along with (6) implies Z0,n→ℓnZ_{0, \sqrt{n}} \to \ell_n almost surely, or written differently Z0,nn→ℓn2n almost surely.\begin{aligned} \frac{Z_{0,n}}{n} \to \frac{\ell_{n^2}}{n} \text{ almost surely.}\end{aligned}

Back to longest increasing subsequences

Having established the connection between the two ways of looking at the problem of longest increasing subsequences, we now freely jump between the two characterizations and use them to prove our results.

Define Ws,t=−Zs,t.W_{s,t} = - Z_{s,t}. We now check that Wm,n,0≤m<nW_{m,n}, 0 \le m < n satisfies the conditions required for the Subadditive Ergodic Theorem. I state the theorem below for completeness. Check out Theorem 6.4.1 in Durrett for a proof.

Theorem 5 [Subadditive Ergodic Theorem]: Suppose Wm,nW_{m,n} for 0≤m<n0 \le m < n satisfy:

  1. W0,m+Wm,n≥W0,nW_{0,m} + W_{m,n} \ge W_{0,n},

  2. {Wnk,(n+1)k,n≥1}\{W_{nk, (n+1)k}, n \ge 1\} is a stationary sequence for each kk,

  3. The distribution of {Wm,m+k,k≥1}\{W_{m,m+k}, k \ge 1\} does not depend on mm, and

  4. E[W0,1+]<∞\mathbb{E}[W_{0,1}^+] < \infty and inf⁡n≥11nE[W0,1]=β>−∞.\inf_{n \ge 1} \frac{1}{n} \mathbb{E}[W_{0,1}] = \beta > - \infty.

Then

Coming back to the problem, let 0<m<n0 < m < n then we claim Z0,m+Zm,n≤Z0,n.Z_{0,m} + Z_{m,n} \leq Z_{0,n}. To see this, fix ω∈Ω\omega \in \Omega and let Z0,m(ω)=aZ_{0,m}(\omega) = a and Zm,n(ω)=b.Z_{m,n}(\omega) = b. Then there exist

(X1(ω),Y1(ω)),…(Xa(ω),Ya(ω)),(Xa+1(ω),Ya+1(ω)),…,(Xa+b(ω),Ya+b(ω)) such that∙ 0<X1(ω)<⋯<Xa(ω)<m,∙ 0<Y1(ω)<⋯<Ya(ω)<m,∙ m<Xa+1(ω)<⋯<Xa+b(ω)<n , and  ∙ m<Ya+1(ω)<⋯<Ya+b(ω)<n.\begin{aligned} &(X_1(\omega), Y_1(\omega)), \ldots (X_a(\omega), Y_a(\omega)), (X_{a+1}(\omega), Y_{a+1}(\omega)), \ldots, (X_{a+b}(\omega), Y_{a+b}(\omega)) \text{ such that} \\ & \bullet \; 0 < X_1(\omega) < \cdots < X_a(\omega) < m, \\ &\bullet \; 0 < Y_1(\omega) < \cdots < Y_a(\omega) < m,\\ & \bullet \; m < X_{a+1}(\omega) < \cdots < X_{a+b}(\omega) < n \,\text{, and }\, \\ &\bullet \; m < Y_{a+1}(\omega) < \cdots < Y_{a+b}(\omega) < n. \end{aligned}

But then it's clear that 0<X1(ω)<⋯<Xa+b(ω)<n0 < X_1(\omega) < \cdots < X_{a+b}(\omega) < n, 0<Y1(ω)<⋯<Ya+b(ω)<n0 < Y_1(\omega) < \cdots < Y_{a+b}(\omega) < n and we have Z0,m(ω)+Zm,n(ω)≤Z0,n(ω).Z_{0,m}(\omega) + Z_{m,n}(\omega) \leq Z_{0,n}(\omega). Since ω\omega was arbitrary, our claim is true. Therefore, W0,m+Wm,n≥W0,nW_{0,m} + W_{m,n} \ge W_{0,n} and condition 1. is true.

For condition 2. we want to show that {Wnk,(n+1)k,n≥1}\{W_{nk, (n+1)k, n \geq 1}\} is a stationary and ergodic sequence for all k≥1.k \geq 1. This is clear from the observation that Zik,(i+1)kZ_{ik, (i+1)k} and Y0,kY_{0,k} have the same distribution, since Leb(Rik,(i+1)k)=Leb(R0,k)\text{Leb}(R_{ik, (i+1)k}) = \text{Leb}(R_{0,k}), and thus by the definition of the Poisson random measure the number of points in each rectangle is an i.i.d. Poisson random variable. Checking the condition 3. is similar to condition 2..

For condition 4. note that W0,1+=Z0,1W_{0,1}^+ = Z_{0,1} and Z0,1≤Poisson(1)Z_{0,1} \leq \text{Poisson}(1) since there are Poisson(1)\text{Poisson}(1) number of points inside [0,1]2[0,1]^2 and at most all of them can be arranged in the increasing order. Thus, E[W0,1+]<E[Poisson(1)]=1<∞.\mathbb{E}[W_{0,1}^+] < \mathbb{E}[\text{Poisson}(1)] = 1 < \infty. Now note that since W0,n=−Z0,nW_{0,n} = - Z_{0,n},

inf⁡n≥11nE[W0,n]=−sup⁡n≥11nE[Z0,n],\begin{aligned} \inf_{n \geq 1} \frac{1}{n} \mathbb{E}[W_{0,n}] = - \sup_{n \geq 1} \frac{1}{n} \mathbb{E}[Z_{0,n}],\end{aligned}
and thus to show the second part of condition 4. we need to show that sup⁡n≥11nE[Z0,n]<∞.\sup_{n \geq 1} \frac{1}{n} \mathbb{E}[Z_{0,n}] < \infty. But this is immediate from Equation (5) in Theorem 3 and Equation (7). Therefore, the subadditive ergodic theorem now implies
Z0,nn→γ a.s.,\begin{aligned} \frac{Z_{0,n}}{n} \to \gamma \text{ a.s.},\end{aligned}

where γ\gamma, due to Equations (3) and (5), lies in [1,e][1,e] and we are done since this implies (2).

Epilogue

I got introduced to this problem from an exam question in a math course I took recently. I recommend the book The Surprising Mathematics of Longest Increasing Subsequences by Dan Romik, which is freely available online, for a lot more content.