Large deviations for increasing sequences on the plane (Q1271286): Difference between revisions

Start with a homogeneous rate one Poisson point process on the plane. A sequence \((x_1,t_1)\), \((x_2,t_2),\ldots, (x_m,t_m)\) of these points is called increasing if \(x_1<x_2<\cdots<x_m\) and \(t_1<t_2<\cdots<t_m\). For \(-\infty<a<b<\infty\) and \(0\leq s<t\), let \({\mathbb L}((a,s),[b,t])\) equal the maximal number of points on an increasing sequence contained in the rectangle \((a,b]\times(s,t]\). These random variables are independent for disjoint rectangles, the translation invariance of the Poisson points gives stationarity, and there is a built-in superadditivity. It is known that a nonrandom limit \(\gamma(x,t)=\lim_{n\to\infty}n^{-1}{\mathbb L}((0,0),(nx,nt))\) exists a.s. for \(x,t\geq 0\). Moreover, \(\gamma(x,t)=c\sqrt{xt}\) for the constant \(c=\lim_{n\to\infty}n^{-1}L_n\). Originally \(c\) was defined through a random permutation. Choose a permutation on \(n\) symbols uniformly at random among the \(n!\) possible permutations, and let \(\Lambda_n\) be the length of the longest increasing subsequence of the permutation. Then the same constant \(c\) appears as the limit \(c=\lim_{n\to\infty}n^{-1/2}\Lambda_n\). \textit{A. M. Vershik} and \textit{S. V. Kerov} [Sov. Math., Dokl. 18, 527-531 (1977); translation from Dokl. Akad. Nauk SSSR 233, 1024-1027 (1977; Zbl 0406.05008)] proved that \(c=2\). The proof is combinatorial and makes use of Young diagrams. In the paper under review, the large deviations from the limit laws \(n^{-1}L_n\to 2\) and \(n^{-1/2}\Lambda_n\to 2\) are discussed. The rate function for lower tail deviations is derived from a result of \textit{B. F. Logan} and \textit{L. A. Shepp} [Adv. Math. 26, 206-222 (1977; Zbl 0363.62068)] about Young diagrams of random permutations. For the upper tail we use a coupling with Hammersley's particle process and convex-analytic techniques.