Laws of Iterated Logarithm for Random Matrices and Random Permutation

Question

The law of iterated logarithm asserts that if $x_1,x_2,\dots$ are i.i.d $\cal N(0,1)$ random variables and $S_n=x_1+x_2+\cdots+x_n$, then $$\limsup_{n \to \infty} S_n/\sqrt {n \log \log n} = \sqrt 2, $$ almost surely.

1. Random matrices

Let $(x_{ij})_{1 \le i < \infty, 1 \le j \le i }$ be an array of i.i.d random $\cal N(0,1)$ variables, define $x_{ji}=x_{ij}$ and let $M_n$ be the $n$ by $n$ matrix obtained by restricting the array to $1 \le i \le n, 1 \le j \le n$.

Let $\lambda(n)$ denote the maximum eigenvalue of $M_n$. The variance and limiting distribution of the maximum eigenvalue (for these and related classes of matrices) were discovered by Tracy and Widom.

Question 1: What is the law of iterated logarithm for this scenario? Namely, can one identifies functions $F(n)$ and $G(n)$ such that

$\limsup_{n \to \infty} (\lambda (n)- {\bf E}(\lambda(n))/ F(n) = 1,$ almost surely, and

$\liminf_{n \to \infty} (\lambda (n)- {\bf E}(\lambda(n))/ G(n) = -1$ almost surely.

Update (May, 24, 2015): A full answer for the limsup (including constants) and a partial answer for the liminf was achieved by Elliot Paquette and Ofer Zeitouni: arxiv.org/abs/1505.05627 !

2. Random permutations

Choose a sequence of real numbers in the unit interval at random independently. Use the first $n$ numbers in the sequence to describe a random permutation $\pi$ in $S_n$. Look at the length $L_n$ of the maximum increasing sub-sequence of $\pi$. The expectation, variance and limiting distributions of the maximal increasing subsequence are known by the works of Logan-Shepp, Kerov-Vershik, (expectation) Baik, Deift & Johansson (variance and limiting distribution) and many subsequent works.

Question 2: What is the law of iterated logarithm for this scenario?

3. Motivation.

My initial motivation is to try to understand the law of iterated logarithm itself, and more precisely, to understand why do we have the $\sqrt {\log \log n}$ factor. (I cannot rationally expect to understand the $\sqrt 2$.)

Answer 1

My initial answer was wrong. Instead of completely deleting it, I left it at the bottom of the post. I use notation now that slightly differ from my original post.

As before, I give only a partial answer related to the max eigenvalue question and the limsup. Recall that the tail estimates for the max eigenvalue is $$(P(\lambda_1(n) >2\sqrt{n}+tn^{-1/6})\sim e^{-Ct^{3/2}}$$ (see e.g. Ledoux's reviews or http://math.univ-lyon1.fr/~aubrun/recherche/smalldeviations/smalldeviations.pdf).

Now, the question is what is the scale in which the recentered and rescaled maximal eigenvalues start behaving like independent random variables. In my original post I essentially claimed this starts happening at scale roughly $n$. This is wrong: the correct scale is given by the so-called GUE minor process (described by Baryshnikov in 2001). Relevant to Gil's problem is the scaling limit computed by Forrester and Nagao: http://arxiv.org/pdf/0801.0100.pdf. They show that the correct scaling in $n^{2/3}$, that is that the (centered and rescaled) maximal eigenvalues of the GUE(n) and GUE(m) decorelate if $m-n>>n^{2/3}$ and are strongly correlated in $m-n<<n^{2/3}$. Using that, and Borel Cantelli, one gets the correct scale. The limsup can be taken over the sequence $a_n=n^3$ instead of $n$. If you go over that sequence, you get from Borel-Cantelli that you cannot exceed $t_{a_n}a_n^{-1/6}$ infinitely often as long as $$\sum_n e^{-C t_{a_n}^{3/2}}<\infty.$$ This will happen as soon as $t_{a_n}^{3/2}>C'\log n$, i.e. $t_{a_n}\sim C'' (\log n)^{2/3}$. Unravelling the definitions, this will give you an upper bound on the limsup that is $t_n\sim (\log n)^{2/3}$; that is, this will show that the function $F(n)$ is at most $C (\log n)^{2/3}/n^{1/6}$. The lower bound on the limsup will follows a similar pattern, using the asymptotic independence stated above, and will give the same function $F(n)$. One can also compute constants (for the a.s. convergence) in the same manner.

Filling in the details in the above is beyond a mathoverflow answer, I may return to it in detail later.

I speculate that the liminf will use the lower tail estimates, which are of the form $e^{-Ct^{3})}$. Working with the same argument would then give $(\log n)^{1/3}/n^{1/6}$ as the correct scaling.

OLD (WRONG) POST:

The following is a partial answer with some hints on how to complete it; I may revisit it later with more details. The answer below refers to the max eigenvalue question, to the limsup, and does not attempt to get the constants, only the scale.

First, the upper bound: recall that the tail estimates for the max eigenvalue is $$(P(\lambda_1(n) >2\sqrt{n}+t\sqrt{n})\sim e^{-Cnt^{3/2}}$$ (see e.g. Ledoux's reviews or http://math.univ-lyon1.fr/~aubrun/recherche/smalldeviations/smalldeviations.pdf). Also recall (a kindly neighbor next door, A. Dembo, pointed out the usefulness of this observation in the current context) that the sequence $\lambda_1(n)$ is monotone in $n$. So, the limsup can be taken over a sequence $a_n=(1+\epsilon)^n$ instead of $n$. If you go over that sequence, you get from Borel-Cantelli that you cannot exceed $t_{a_n}\sqrt{a_n}$ infinitely often as long as $$\sum_n e^{-C t_{a_n}^{3/2} a_n}<\infty.$$ This will happen as soon as $a_nt_{a_n}^{3/2}>C'\log n$, i.e. $t_{a_n}\sim C'' (\log n/a_n)^{3/2}$. Unravelling the definitions, this will give you an upper bound on the limsup that is $t_n\sim (\log \log n /n)^{2/3}$; that is, this will show that the function $F(n)$ is at most $C (\log \log n)^{2/3}/n^{1/6}$.

(Remark to @Carlo Beenakker: the difference with TSAW is that the tail estimates there are proportional to $t^3$, not $t^{3/2}$; This will be in line with the liminf computation in the RM case, in which case I expect the same discrepency in exponents of the $\log \log n$ as you noted, see below.)

For the lower bound (on the limsup), you need to take a sequence that is sparse enough so that you have approximate independence. Here is a leap of faith, that would require a separate proof: if you take an $N\times N$ GUE and resample the top $\epsilon N\times \epsilon N$ entries, the maximum eigenvalue does not change much if $\epsilon$ is small. I believe this follows from delocalization results for the eigenvectors of GUE, but have not checked details. If that is true, then for an exponentially growing sequence $a_n=C^n$, the sequence $\lambda_1(a_n)$ will behave like an i.i.d. sequence, to which you now can again apply the independent Borel-Cantelli to match the previous upper bound.

I speculate that the liminf will use the lower tail estimates, which are of the form $e^{-C(nt^{3/2})^2}$. Working with the same argument would then give $(\log \log n/n^2)^{1/3}$ as the correct scaling.

Answer 2

Noting that the largest eigenvalue of a random matrix and the maximal increasing subsequence of a random permutation are both expressed by the Tracy-Widom distribution, I might broaden your question to appearances of the law of iterated logarithm in connection with Tracy-Widom. The application I am aware of involves the self-interacting one-dimensional stochastic process called "true self-repelling motion". The law of iterated logarithm of the position $X_t$ at time $t$ for this process was derived by Laure Dumaz in Large deviations and path properties of the true self-repelling motion: almost surely,

$$\lim {\rm sup}_{t\rightarrow\infty}\frac{X_t}{t^{2/3}(\ln\ln t)^{1/3}}=2^{-2/3}\frac{3}{|a_1|},$$

with $a_1$ the first (negative) zero of the derivative of the Airy function.

---

What strikes me, when comparing with the usual scaling for Brownian motion, is that the factor $t$ in the denominator and the iterated logarithm appear with different powers. Simply looking at the different scaling of the root-mean-square displacement ($t^{2/3}$ rather than $t^{1/2}$), I would have expected the same power $2/3$ for both. I would guess an intuitive explanation must be quite subtle.