4
$\begingroup$

Suppose $X_{\max}$ is the maximum in a sequence $X_1,X_2,\ldots,X_n$ where each $X_i\sim\chi^2_k$ is an i.i.d. chi-squared random variable with $k$ degrees of freedom.

Since chi squared distribution has an exponential tail, for some fixed number of degrees of freedom $k$ we know that $\lim_{n\rightarrow\infty}\frac{X_{\max}}{\ln n}=c$ almost surely, with $c$ being a constant (see Example 3.5.6 on page 176 here). A weaker convergence in probability claim can be made using the convergence of the distribution of appropriately centered $X_{\max}$ to Gumbel (see summary in Table 3.4.4 on page 156 of the same reference).

However, what happens if both the number of degrees of freedom $k$ also increases, though at a rate that is slower than the increase in the number of random variables in the sequence $n$? For example, let $n=k^2$ (in general, my $n=\omega(k)$). Is there a result similar to the above, with $k\rightarrow\infty$ (which implies that $n\rightarrow\infty$)?

Does convergence of the distribution of $X_{\max}$ to Gumbel even apply with centering in the above-referenced Table 3.4.4 under these conditions? (the norming constant $d_n$ is negative when $n=k^2$ is substituted, so I think there is trouble here.)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

I am sure this must be written somewhere but since I don't know a reference, let me sketch the computation. I hope there is no error in computation below.

As I commented in your related post, what you are dealing with is the sum of $t=k/2$ exponentials (let's assume $k$ is even, the case of $k$ odd is not really that different). I will also assume that $\log n<<t$ since this seems to be the regime you care about; the adaptation to the other cases I leave to you, I did not check the details.

Thus, $X_1=\sum_{i=1}^t E_i$, with $E_i$ exponential variables. Thus, for $w<1$, $P(X_1>t+w\sqrt{t})$ is of order $1$ while for $w>1$ but $w<<\sqrt{t}$, as long as $t\to\infty$, you have Gaussian tails: $$P(X_1>t+w\sqrt{t})\sim c_1 e^{-c_2 w^2}/g(t)\,,$$ for some function $g(t)$ that is essentially of polynomial growth and which I have not computed - it is $\sqrt{t}$ for moderately large $w$'s but later it may change. (For this you need to appeal to known results on precise moderate deviations for sums of independent variables, e.g. as in Petrov's book on sums of independent random variables; there is a big difference in your original question between $t$ fixed and $t$ growing in $n$ in that the tail estimate change from Gaussian to exponential, and this affects the scaling.). When $w$ becomes of order $\sqrt{t}$ or larger, then you get a different tail estimate, but I do not discuss this case in details - basically you get into large deviations regime and beyond.

Now, just follow the derivation of the law of the max: you get, for the range you care about, $$P(X_{\max}<t+z)\sim (1-c_1e^{-c_2 (z/\sqrt{t})^2}/g(t))^n\sim e^{-c_1n e^{-c_2 (z/\sqrt{t})^2}/g(t)}.$$ Now you choose $z=c_2'\sqrt{t\log n}-c_3\log g(t)\sqrt{t/\log n}+z'\sqrt{t/\log n}$. Then, with appropriate choice of constants, $$P(X_\max<t+z)\sim e^{-c_1e^{-c_4 z'}}\,,$$ which is Gumbel (note that the centering is $t+c_2'\sqrt{t\log n}-c_3 (\log g(t))\sqrt{t/\log n}$). For this to work, I used that $\log n<<t$, so that $z/\sqrt{t}<<\sqrt{t}$.

Improve this answer
$\endgroup$
13
  • $\begingroup$ Thank you for the helpful answer! I don't see any problems with the mathematics in your derivation, though I need to locate Petrov's book and look up the constants $c_1$ and $c_2$, and function $g(t)$ (also, where do $c'_2$ and $z'$ come from?). It is fascinating how different the centering term is from the case when $k$ is constant. Looks like $\frac{X_{\max}-t}{\sqrt{t\log n}}\rightarrow c$ in probability (is that correct?) -- I wonder if that can be strengthened to "almost surely" (a topic for a different discussion). $\endgroup$
    – Bullmoose
    Commented Sep 22, 2013 at 20:43
  • 1
    $\begingroup$ Correct, in the range indicated. Yes, you can strengthen to a.s. - the tail estimates are good enough for that. I also did not look up the precise asymptotics in the literature and therefore am not sure what is $g(t)$ in the whole range - for moderately small $w$ it will be $\sqrt{t}$. $\endgroup$
    – ofer zeitouni
    Commented Sep 23, 2013 at 0:26
  • $\begingroup$ Again, thank you for your help! I have another question: you say "now you choose $z=c_2'\sqrt{t\log n}-c_3\log g(t)\sqrt{t/\log n}+z'\sqrt{t/\log n}$". I think what you are doing is finding $z=f(t,n,g(n),z')$ which allows $P(X_{\max}<t+z)$ to be expressed as Gumbel $e^{-c_1 e^{-c_4 z'}}$. However, when I try to plug in your expression for $z$, it doesn't work: there leftover terms involving $g(t)$, which doesn't cancel out. The expression I get by solving $ne^{-c_2(x/\sqrt{t})^2}/g(t)=e^{-c_4z'}$ is $z=\sqrt{t(\log(n)-\log(g(n))+c_4z')/g(n)}$. Could you please clarify what step I am missing? $\endgroup$
    – Bullmoose
    Commented Sep 23, 2013 at 3:44
  • $\begingroup$ just expand and use taylor. With my choice, $z/\sqrt(t)$ equals $c_2'\sqrt{\log n}-c_3\log g(t)/\sqrt{\log n}+z'/\sqrt{\log n}$. When squaring, and taking into account that $g(t)$ is essentially a power of $t$ (maybe this is what you did not use?) you get $C_1 \log n-C_2\log g(t)+C_3z'+o(1)$. It is true that the $C_1$ and $C_2$ terms are of the same order here, if $t$ is a power of $n$. BTW, it is $g(t)$, not really $g(n)$, but of course $n$ and $t$ are related in your application. $\endgroup$
    – ofer zeitouni
    Commented Sep 23, 2013 at 12:06
  • $\begingroup$ Thanks for the explanation! In my previous comment, I meant $g(t)$: $g(n)$ was a typo. I re-did my expansion of the square and see now that everything reconciles. The confusing term was $\frac{c_3^2\log^2(g(t))}{\log(n)}$, but as you point out, $g(t)$ is a power of $t$, and, in turn, $t$ (in my scenario) is a power of $n$, so the log in the denominator cancels out one of the logs in the numerator. $\endgroup$
    – Bullmoose
    Commented Sep 25, 2013 at 4:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .