What is the rate of growth of $M_n := \max_{1 \le i \le n} U_i^{(n)}$, where $U_i^{(n)} \sim \operatorname{Uniform}[0,n]$? Is it "constant"?

Question

On pp. 370-374 (see this previous question) of Cramer's 1946 Mathematical Methods of Statistics, the author shows that for any continuous distribution $P$, if $X_1, \dots, X_n \sim P$ are i.i.d., then the RV:

$$ \Xi_n \overset{def}{=} n (1 - F(M_n)) \,, \quad \text{where }M_n \overset{def}{=} \max_{1 \le i \le n} X_i \,, $$

has the same distribution as the maximum of $n$ i.i.d. RV's $U_1, \dots, U_n$, where $U_i \sim \operatorname{Uniform}(0,n)$, inasmuch as he shows that they have the same density (cf. p.49 of Keener, Theoretical Statistics). (Here $F$ of course denotes the CDF of each of the observations $X_i$.)

Cramer says later that we can assume $\Xi_n$ "is bounded" - but in what sense precisely is that true?

Question: What is the almost sure rate of growth of the random variables $\Xi_n$? Of $\log(\Xi_n)$?

In particular, is it true that $\log(\Xi_n) = o(\log\log n)$ almost surely?

$\log(\Xi_n) = o(\log\log n)$ a.s. appears to be sufficient to show that $\max_{1 \le i \le n} X_i \sim \sqrt{2 \log n}$ a.s. where the $X_i \sim \mathscr{N}(0,1)$, using the argument found here, hence my interest.

In a community wiki "answer" below I have posted what I believe to be a proof that $\Xi_n = o(\log n)$ a.s., at least when the $X_i \sim \mathscr{N}(0,1)$, an assumption which would be considered acceptable for any accepted answer. Note that, it appears to be sufficient to show that for all $\varepsilon >0$, $\Xi_n = o((\log n)^{\varepsilon})$ a.s. in order to conclude $\log (\Xi_n) = o(\log \log n)$ a.s.

Note: For each $n$, $\Xi_n$ has the distribution of the maximum of $n$ i.i.d. uniforms supported on $[0,n]$ (not $[0,1]$ or $[0, \theta]$ for some fixed constant), so this problem does not seem completely trivial.

Note 2: Following the argument below, it seems it suffices to show that (assuming this is even true), for any $\epsilon >0$, $\delta > 0$ that:

$$ \sum_{n=1}^{\infty} \frac{(\log n)^\delta}{n (\exp ((\log n)^\delta ))^\epsilon } < \infty \,.$$

I haven't been able to figure out how to control (i.e. bound) the $\exp ( (\log n)^\delta )$ term/factor usefully. (Comparing with this, the case where $\alpha=1$ and $\beta < 1$, seems to show that this is actually false for $\delta < 1$ or small enough. Which would be OK since this would only be sufficient, not necessary, anyway.)

Note 3: If it really is true that $\Xi_n$ is stochastically dominated by an exponential random variable (with parameter $1$) for all $n$, then maybe it's possible to get the necessary asymptotic probabilistic bound more easily for exponentials and then use the stochastic dominance to conclude.

Answer 1

By the setting, $V_n = 1 - F(U_n)$ is a sequence of i.i.d. random variables with $V_n \sim \operatorname{Uniform}([0,1])$. Write

$$ \xi_n = \min\{V_1, \cdots, V_n\}, \qquad \Xi_n = n \xi_n.$$

Here we prove the following claim.

Claim. $\displaystyle \limsup_{n\to\infty} \frac{\Xi_n}{\log \log n} = 1 $ holds almost surely.

As usual, we show that one bounds the other.

Proof of $\ ``\leq\text{''}$. We first fix $\epsilon \in (0, 1)$ and $\alpha > 1$, and set $n_k = \lfloor \alpha^k \rfloor$. Then from the inequality $ \mathbb{P}( \Xi_n > t) = \left( 1 - \frac{t}{n} \right)^n \leq e^{-t} $, it follows that

$$ \sum_{k=1}^{\infty} \mathbb{P}(\Xi_{n_k} > (1+\epsilon)\log\log n_k) \leq \sum_{k=1}^{\infty} \frac{1}{\left( \log n_k \right)^{1+\epsilon}} < \infty $$

since $(\log n_k)^{-1-\epsilon} \asymp k^{-1-\epsilon}$ as $k\to\infty$. By Borel-Cantelli's lemma, $\Xi_{n_k} \leq (1+\epsilon)\log\log n_k$ eventually holds a.s. But for each $n \in [n_k, n_{k+1}]$, we have

$$ \frac{\Xi_{n}}{\log\log n} = \frac{n \xi_n}{\log\log n} \leq \frac{n_{k+1} \xi_{n_{k+1}}}{\log\log n_k} = \frac{n_{k+1}\log\log n_{k+1}}{n_k \log\log n_k} \frac{\Sigma_{n_k}}{\log\log n_{k+1}}, $$

and so, taking limsup as $k\to\infty$ shows that

$$ \limsup_{n\to\infty} \frac{\Xi_n}{\log\log n} \leq \alpha(1+\epsilon) \quad \text{a.s.} $$

But since this is true for any $\epsilon > 0$ and $\alpha > 1$, letting $\epsilon \to 0$ and $\alpha \to 1$ along subsequence (so that we only care about countable intersection of events) proves the desired inequality.

Proof of $\ ``\geq\text{''}$. This part is much harder. Define $X_n$ and $T_n$ as follows:

• $T_0 = 0$, and $T_{n} = \inf \{ m > T_{n-1} : \xi_m < \xi_{T_{n-1}} \}$ for $n \geq 1$. (Here, the convention $\xi_0 = 1$ is used.) In other words, $T_n$'s record the $n$-th time instance at which $\xi_n$ becomes smaller.

• $X_0 = 1$, and $X_{n} = \xi_{T_{n}} / \xi_{T_{n-1}}$.

Then $(X_n)_{n=1}^{\infty}$ are i.i.d. with $X_n \sim \operatorname{Uniform}([0,1])$, and $T_{n} - T_{n-1} \sim \operatorname{Geometric}(X_0 \cdots X_{n-1})$ for $n \geq 1$. Now we fix $\epsilon \in (0, 1)$ and focus on the extreme behavior of

$$\tau_n := X_1 \cdots X_{n-1} (T_n - T_{n-1}).$$

To this end, write $\mathcal{F}_n = \sigma( X_0, \cdots, X_n, T_0, \cdots, T_n)$ for the natural filtration of $(X_n)$ and $(T_n)$. Then $\tau_n$ is $\mathcal{F}_n$-measurable, and

$$ \mathbb{P}(\tau_n > (1-\epsilon)\log n \mid \mathcal{F}_{n-1}) \geq \left( 1 - X_1\cdots X_{n-1} \right)^{\frac{(1-\epsilon)\log n}{X_1 \cdots X_{n-1}}} $$

By the strong law of large numbers, $X_1 \cdots X_n = e^{-(1+o(1))n}$, and so, this lower bound is $\asymp n^{-(1-\epsilon)}$ a.s. This tells that $\sum_{n=1}^{\infty} \mathbb{P}(\tau_n > (1-\epsilon)\log n \mid \mathcal{F}_{n-1}) = \infty$ a.s., and so, by the generalized second Borel-Cantelli lemma, it follows that

$$ \tau_n > (1-\epsilon)\log n\quad \text{infinitely often} \quad \text{a.s.} \tag{1} $$

On the other hand, for $n \geq 3$,

$$ \mathbb{P}(\tau_n > 2019\log n) \leq \mathbb{E} \left[ \left( 1 - X_1\cdots X_{n-1} \right)^{\frac{2019\log n}{X_1 \cdots X_{n-1}}-1} \right] \leq \frac{c}{n^{2019}} $$

where $c > 0$ is an absolute constant. (We can pick $c = \mathbb{E}[(1-X_1 X_2)^{-1}] = \pi^2/6$, for instance, although this value is not important.) So by the Borel-Cantelli lemma, $\mathbb{P}(\tau_n \leq (1+\epsilon)\log n \text{ i.o}) = 1$. Moreover, by the strong law of large numbers again, $\mathbb{P}(X_1 \cdots X_n \geq e^{-(1+\epsilon)n} \text{ eventually}) = 1$. Therefore

$$ T_n = \sum_{k=1}^{n} \frac{\tau_k}{X_1 \cdots X_k} \leq \sum_{k=1}^{n} e^{(1+\epsilon)k} 2019 \log k + \mathcal{O}(1) \leq C e^{(1+\epsilon)n}\log n $$

for some random variable $C$ which a.s. finite and positive. Using this inequality,

$$ \frac{\Xi_{T_n - 1}}{\log\log T_n} = \frac{X_1 \cdots X_{n-1} (T_n - 1)}{\log \log T_n} \geq \frac{\tau_n}{\log n + O(1)}. \tag{2} $$

Combining $\text{(1)}$ and $\text{(2)}$, it follows that

$$ \limsup_{n\to\infty} \frac{\Xi_n}{\log\log n} \geq \limsup_{n\to\infty} \frac{\Xi_{T_n - 1}}{\log \log T_n} \geq 1 - \epsilon \quad \text{a.s.}, $$

and since this is true for any $\epsilon \in (0, 1)$, the desired inequality follows. $\square$

Answer 2

Attempt: I don't feel comfortable that this is correct, but here we go. Because (according to Cramer), $\Xi_n$ is $Beta(1,n)$, and thus has the density $(1 - \frac{\xi}{n})^n$ with support $[0,n]$, we can conclude that every $\Xi_n$ is stochastically bounded (I think) by an exponential random variable with parameter $1$.

This is because of the inequality $-x \ge \log(1-x)$, since this implies that:

$$ -\frac{x}{n} \ge \log ( 1 - \frac{x}{n}) \iff -x \ge n \log (1 - \frac{x}{n}) \iff e^{-x} \ge \left( 1 - \frac{x}{n} \right)^n $$

where $e^{-x}$ is the PDF of an exponential(1).

The stochastic ordering doesn't seem to depend on the probabilistic dependence of the sequence of exponential random variables, so we can assume we have some sequence of $Y_n$ i.i.d. exponential(1) R.V.'s.

This is where it seems iffy to me: basically I will claim that the stochastic ordering of $\Xi_n \preceq Y_n$ for each individual $n$ somehow implies that the stochastic ordering transfers to the entire sequences of $\Xi_n$'s and $Y_n$'s.

So I believe it's the case (please correct me if I'm wrong) that some sequence of RVs $X_n$ is $O_p(1)$ if and only if for all $M>0$, $$\mathbb{P}(X_n > M \text{ i.o.}) = 0$$

So the claim is that because $\Xi_n \preceq Y_n$ for all $n$ (don't really understand how the PDF of one can uniformly dominate the PDF of another but both integrate to $1$, but whatever) that the following would hold:

$$ \mathbb{P}(\Xi_n > M \text{ i.o.}) \le \mathbb{P}(Y_n > M \text{ i.o.}) \,. $$

So we just have to show that $\mathbb{P}(Y_n > M \text{ i.o.}) = 0$ for all $M$, but that's easy (I think), since by our assumptions

$$ \mathbb{P}(Y_n > M \text{ i.o.}) =C_{\{ n_k \}}\lim_{K \to \infty} \prod_{k=1}^K \mathbb{P}(Y_{n_k} > M) =C_{\{ n_k \}}\lim_{K \to \infty} (e^{-M})^k =0$$

where $\{ n_k\}$ is some subsequence, and $C_{\{n_k\}}$ is some finite constant depending on the particular subsequence.

If anyone can fix this, or show why it's false and doomed to fail even with modifications, I would really appreciate it.

---

First let's go through a chain of trivialities in order to rephrase the problem in a way which makes it easier to solve (note that by definition $\Xi_n \ge 0$):

$$\Xi_n = o(\log n) \quad \iff \quad \lim_{n \to \infty} \frac{\Xi_n}{\log n} = 0 \quad \iff \quad \\ \forall \varepsilon > 0, \frac{\Xi_n}{\log n} > \varepsilon \text{ only finitely many times} \quad \iff \\ \forall \varepsilon >0, \quad \Xi_n > \varepsilon \log n \text{ only finitely many times} \,.$$

One also has that:

$$\Xi_n > \varepsilon \log n \quad \iff \quad n(1 - F(Z_n)) > \varepsilon \log n \quad \iff \quad 1 - F(Z_n) > \frac{\varepsilon \log n}{n} \\ \iff \quad F(Z_n) < 1 - \frac{\varepsilon \log n}{n} \quad \iff \quad Z_n \le \inf \left\{ y: F(y) \ge 1 - \frac{\varepsilon \log n}{n} \right\} \,. $$

Correspondingly, define for all $n$:

$$ u_n^{(\varepsilon)} = \inf \left\{ y: F(y) \ge 1 - \frac{\varepsilon \log n}{n} \right\} \,. $$

Therefore the above steps show us that:

$$\Xi_n = o(\log n) \text{ a.s.} \quad \iff \quad \mathbb{P}(\Xi_n = o(\log n)) = 1 \quad \iff \quad \\ \mathbb{P}(\forall \varepsilon > 0 , \Xi_n > \varepsilon \log n \text{ only finitely many times}) = 1 \\ \iff \mathbb{P}(\forall \varepsilon > 0, Z_n \le u_n^{(\varepsilon)} \text{ only finitely many times}) = 1 \\ \iff \mathbb{P}(\forall \varepsilon >0, Z_n \le u_n^{(\varepsilon)} \text{ infinitely often}) =0 \,. $$

Notice that we can write:

$$ \{ \forall \varepsilon >0, Z_n \le u_n^{(\varepsilon)} \text{ infinitely often} \} = \bigcap_{\varepsilon > 0} \{ Z_n \le u_n^{(\varepsilon)} \text{ infinitely often} \} \,.$$

The sequences $u_n^{(\varepsilon)}$ become uniformly larger as $\varepsilon$ decreases, so we can conclude that the events $$\{ Z_n \le u_n^{(\varepsilon)} \text{ infinitely often} \} $$ are decreasing (or at least somehow monotonic) as $\varepsilon$ goes to $0$. Therefore the probability axiom regarding monotonic sequences of events allows us to conclude that:

$$\mathbb{P}(\forall \varepsilon >0, Z_n \le u_n^{(\varepsilon)} \text{ infinitely often}) = \\ \mathbb{P} \left( \bigcap_{\varepsilon > 0} \{ Z_n \le u_n^{(\varepsilon)} \text{ infinitely often} \} \right) = \\ \mathbb{P} \left( \lim_{\varepsilon \downarrow 0} \{ Z_n \le u_n^{(\varepsilon)} \text{ infinitely often} \} \right) = \\ \lim_{\varepsilon \downarrow 0} \mathbb{P}(Z_n \le u_n^{(\varepsilon)} \text{ infinitely often}) \,.$$

Therefore it suffices to show that for all $\varepsilon >0$,

$$\mathbb{P}(Z_n \le u_n^{(\varepsilon)} \text{ infinitely often}) = 0 $$

because of course the limit of any constant sequence is the constant.

Here is somewhat of a sledgehammer result:

Theorem 4.3.1., p. 252 of Galambos, The Asymptotic Theory of Extreme Order Statistics, 2nd edition. Let $X_1, X_2, \dots$ be i.i.d. variables with common nondegenerate and continuous distribution function $F(x)$, and let $u_n$ be a nondecreasing sequence such that $n(1 - F(u_n))$ is also nondecreasing. Then, for $u_n < \sup \{ x: F(x) <1 \}$, $$\mathbb{P}(Z_n \le u_n \text{ infinitely often}) =0 \text{ or }1 $$ according as $$\sum_{j=1}^{+\infty}[1 - F(u_j)]\exp(-j[1-F(u_j)]) < +\infty \text{ or }=+\infty \,. $$

The proof is technical and takes around five pages, but ultimately it turns out to be a corollary of one of the Borel-Cantelli lemmas. I may get around to trying to condense the proof to only use the part required for this analysis as well as only the assumptions which hold in the Gaussian case, which may be shorter (but maybe it isn't) and type it up here, but holding your breath is not recommended. Note that in this case $\omega(F)=+\infty$, so that condition is vacuous, and $n(1-F(n))$ is $\varepsilon \log n$ thus clearly non-decreasing.

Anyway the point being that, appealing to this theorem, if we can show that:

$$\sum_{j=1}^{+\infty}[1 - F(u_j^{(\varepsilon)})]\exp(-j[1-F(u_j^{(\varepsilon)})]) = \sum_{j=1}^{+\infty}\left[ \frac{\varepsilon \log j}{j} \right]\exp(-\varepsilon \log j) = \varepsilon \sum_{j=1}^{+\infty} \frac{ \log j}{j^{1 + \varepsilon}} < + \infty \,. $$

Note that since logarithmic growth is slower than any power law growth for any positive power law exponent (logarithms and exponentials are monotonicity preserving, so $\log \log n \le \alpha \log n \iff \log n \le n^{\alpha}$ and the former inequality can always be seen to hold for all $n$ large enough due to the fact that $\log n \le n$ and a change of variables), we have that:

$$ \sum_{j=1}^{+\infty} \frac{\log j}{j^{1 + \varepsilon}} \le \sum_{j=1}^{+\infty} \frac{j^{\varepsilon/2}}{j^{1 + \varepsilon}} = \sum_{j=1}^{+\infty} \frac{1}{j^{1 + \varepsilon/2}} < +\infty \,,$$

since the p-series is known to converge for all $p>1$, and $\varepsilon >0$ of course implies $1 + \varepsilon/2 > 1$.

Thus using the above theorem we have shown that for all $\varepsilon >0$, $\mathbb{P}(Z_n \le u_n^{(\varepsilon)} \text{ i.o.}) = 0$, which to recapitulate should mean that $\Xi_n = o(\log n)$ almost surely.

We need to show still that $\log \Xi_n = o(\log \log n)$. This doesn't follow from the above, since, e.g.,

$$ \frac{1}{n} \log n = o(\log n) \,, - \log n + \log \log n \not= o(\log \log n) \,. $$

However, given a sequence $x_n$, if one can show that $x_n = o( (\log n)^{\delta})$ for arbitrary $\delta >0$, then it does follow that $\log(x_n) = o(\log \log n)$. Ideally I would like to be able to show this for $\Xi_n$ using the above lemma (assuming it's even true), but am not able to (as of yet).

Answer 3

I was able to get my hands on a 1999 version of Cramer's Mathematical Methods of Statistics. Let me cite the relevant section for this problem, with some appropriate rewording for better flow.

Let $M^v_n$ be the $v$th value from the top in a sample $X_1, \cdots, X_n \overset{\text{iid}}{\sim} F$. If we introduce $\Xi_n$ by the substitution \begin{align*} \Xi_n = n(1 - F(M_n^v)) \end{align*} This variable has density \begin{align*} f_{\Xi_n}(\xi) = \binom{n-1}{v-1}\left(\frac{\xi}{n}\right)^{v-1}\left(1-\frac{\xi}{n}\right)^{n-v} \end{align*}

Hence, for the maximum order statistic, $v=1$, we therefore have the density \begin{align*} f_{\Xi_n}(\xi) = \left(1-\frac{\xi}{n}\right)^{n-1} \end{align*} or a $n\text{Beta}(1, n)$ distribution. Previously, the OP and I had some confusion in the comments and chat about the formulation s/he described: \begin{align*} \Xi_n \overset{\mathcal{D}}{=}\max(U_1, \cdots, U_n), \qquad \text{where } U_i \overset{\text{iid}}{\sim} \text{Unif}(0, n) \end{align*} Since this would imply that $\Xi_n$ is instead $n\text{Beta}(n, 1)$ (see here). Indeed, if we were to define $m_n^v$ as the $v$th value from the bottom of the sample, and define \begin{align*} H_n = n F(m_n^v) \end{align*} We would also get \begin{align*} f_{H_n}(\eta) = \binom{n-1}{v-1}\left(\frac{\eta}{n}\right)^{v-1}\left(1-\frac{\eta}{n}\right)^{n-v} \end{align*} with $v = 1$ giving us that $H_n$ is also $n \text{Beta}(1, n)$.

Before we continue, let me provide a concrete definition of growth rates used in probability theory.

A sequence of random variables $X_n$ are said to be bounded in probability or stochastically bounded if, for all $\epsilon > 0$, there exists $M, N$ such that, for all $n > N$, we have \begin{align*} P(|X_n| < M) > 1-\epsilon \end{align*} We then say $X_n = O_p(a_n)$ if $X_n/a_n$ is stochastically bounded. Similarly, we say $X_n$ is stochastically convergent to zero if \begin{align*} \lim_{n\rightarrow \infty} P(|X_n| < M) = 1 \end{align*} for all $M > 0$, and write $X_n = o_p(a_n)$ if $X_n/a_n$ is stochastically convergent to zero.

Remark: For example, if $X_n \sim \mathcal{N}(0, \sin^2(n))$, then $X_n = O_p(1)$, since \begin{align*} P(|X_n| < M) = 2\Phi\left(\frac{M}{|\sin(n)|}\right) - 1 \ge 2\Phi(M) - 1 > 1 - \epsilon \end{align*} by choosing $M = \Phi^{-1}(1 - \frac{\epsilon}{2})+1$ and $N = 1$.

Back to the problem at hand, it turns out that \begin{align*} n\text{Beta}(1, n) \overset{\mathcal{D}}{\rightarrow} \text{Exp}(1) \end{align*} In other words, there exists a random variable $\Omega \sim \text{Exp}(1)$ such that \begin{align*} \Xi_n = \Omega + o_p(1) \end{align*} Since $\Omega = O_p(1)$, we have that $\Xi_n = O_p(1) + o_p(1) = O_p(1)$ by big-O/little-o arithmetic. Indeed, looking further into Cramer's book, he stated that \begin{align*} \lim_{n\rightarrow \infty} f_{\Xi_n}(\xi) = \frac{\xi^{v-1}}{\Gamma(v)}e^{-\xi} \end{align*} which is a $\text{Gamma}(n, 1)$ distribution, which is also $O_p(1)$. Hence, for any fixed $v$, $\Xi_n$ would be stochastically bounded.