Return to 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$.)

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$.)

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.

##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$.)

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$.)

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.

##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 don't ecpect to understand the $\sqrt 2$.)

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.

##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$.)