Gumbel Distribution as Limiting Distribution

The problem is the following:

Fix $n\geq 1$ and let $\{S_{n,i}\}_{i\geq 1}$ be i.i.d. random variables whose common distribution is equal to $X_1+\dots + X_n$ for $X_i=\pm 1$ with probability $1/2$. Define $$M_n^{(c)}= \max_{1\leq I \leq e^{cn}} S_{n,i}$$ Then prove that for $c\in (0, \log 2)$, there exists constants $c_1,c_2,c_3,c_4$ (which only depend on $c$) such that $$\lim_{n \to \infty} \mathbb{P}\left( \frac{M_n^{(c)}}{n}\leq c_1+c_2\frac{x+c_3}{n}+c_4\frac{\log(n)}{n}\right)=e^{-e^{-x}}$$

Determine the constants $c_1,c_2,c_3,c_4$ and show why the result fails when $c\geq \log2$.

Now I see that the right hand side is the Gumbel Distribution. And so I'd like to try to use the fact that if $X_i$ are i.i.d. and their CDF is $F(x)=1-e^{-x}$ (so they are exponentially distributed), and let $M_n=\max_{m\leq n}X_m$, then for any finite $y$, $\mathbb{P}(M_n-\log n \leq y) \rightarrow \exp(-e^{-y})$.

Or the following : if $X_1, X_2,\dots$ are i.i.d standard normal, define $b_n$ by $\mathbb{P}(X_i\geq b_n)=1/n$, and $M_n=\max (X_1,\dots, X_n)$, then $\mathbb{P}(b_n(M_n-b_n)\leq x) \rightarrow \exp(-e^{-x})$.

However, I do not really have any idea for this problem beyond the above facts about Gumbel Distribution. Any help is appreciated. Thank you.

1 Answer

You are correct in identifying that we are trying to obtain a Gumbel limit law, but the proof is a little more involved than the i.i.d. case. First, let $I$ be the large deviations rate function associated with $\{X_i\}$, i.e. \begin{align*} I(x):&=\sup_{\lambda\in\mathbb R}\Big(\lambda x-\log\mathbb E\left[e^{\lambda X_1}\right]\Big)\\ &=\begin{cases} x\tanh^{-1}(x)+\frac12\log(1-x^2)&\text{if }|x|<1,\\ +\infty&\text{otherwise.} \end{cases} \end{align*} Let $\rho=\rho_c$ be the unique $\rho\in(0,1)$ such that $I(\rho)=c$. (Observe that $I$ is strictly increasing on $(0,1)$ and $I(x)\to\log2$ as $x\uparrow1$, so this is possible if and only if $c\in(0,\log2)$.) The key estimate is from the Bahadur-Rao Theorem, which can be used to show there is some constant $C>0$ such that, provided $a_n=o(n^{1/2})$, $$\mathbb P\Big(S_{n,1}> n\rho-a_n\Big)\sim\frac{C}{\sqrt{n}}e^{-nI(\rho-a_n/n)}$$ as $n\to\infty$. Using the fact that $M_n^{(c)}\le y$ if and only if $S_{n,i}\le y$ for $1\le i\le e^{cn}$, we find $$\mathbb P\Big(M_n^{(c)}\le n\rho-a_n\Big)=\Big(1-\mathbb P\big(S_{n,1}> n\rho-a_n\big)\Big)^{e^{cn}}\sim\left(1-\frac{C}{\sqrt{n}}e^{-nI(\rho-a_n/n)}\right)^{e^{cn}}.$$ Setting $a_n=\frac1{2I'(\rho)}\log n-z$ and using the Taylor expansion of $I$ about $\rho$, we have $$I(\rho-a_n/n)=c-\frac12\frac{\log n}n+\frac{I'(\rho)z}n+O\left(\frac{\log^2n}{n^2}\right).$$ Hence $$\frac{1}{\sqrt{n}}e^{-nI(\rho-a_n/n)}=\frac{e^{-I'(\rho)z+O(\log^2n/n)}}{e^{cn}},$$ and so \begin{align*} \mathbb P\left(M_n^{(c)}\le n\rho-\frac1{2I'(\rho)}\log n+z\right)&\sim\left(1-\frac{Ce^{-I'(\rho)z+O(\log^2n/n)}}{e^{cn}}\right)^{e^{cn}}\\ &\to\exp\left(-Ce^{-I'(\rho)z}\right). \end{align*} To finish off, we just need to make a substitution to get rid of $C$ and $I'(\rho)$, and then identify the appropriate constants. To that end, let $x=\frac1{I'(\rho)}(z-\log C)$, and observe that we have shown $$\lim_{n\to\infty}\mathbb P\left(\frac{M_n^{(c)}}n\le\rho+I'(\rho)\frac{x+\log C/I'(\rho)}{n}-\frac1{2I'(\rho)}\frac{\log n}n\right)=e^{e^{-x}}$$ as required.

To show that we do not have such a limit for $c\ge\log2$, observe that $$\mathbb P(M_n^{(c)}<n)=\Big(1-\mathbb P(S_{n,1}=n)\Big)^{e^{cn}}=\Big(1-2^{-n}\Big)^{e^{cn}}\sim e^{-e^{(c-\log 2)n}},$$ so in particular $$\liminf_{n\to\infty}\mathbb P\Big(M_n^{(c)}=n\Big)\ge1-\frac1e.$$