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"?

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$

Tags:

Probability Theory

Asymptotics

Order Statistics

Upper Lower Bounds

Probability Limit Theorems

Related

Arranging $n$ balls in $k$ bins so that $m$ consecutive bins are empty Solutions to $a,\ b,\ c,\ \frac{a}{b}+\frac{b}{c}+\frac{c}{a},\ \frac{b}{a} + \frac{c}{b} + \frac{a}{c} \in \mathbb{Z}$ If rank$(T)\le$rank$(T^3)$, then intersection of range and null space of $T$ is zero Six Octagons on a Surface with $\chi=-2$ $\text{SL}_2(\mathbb Z)$ acts on upper plane $\mathbb H$. What kind of points have non-trivial stabilizer? And how many orbits are there? When change of variable makes an empty interval Sequence such that every subsequence can have a different real limit Can an uncountable group have a countable number of subgroups? Sizes of a pair of sequences with identical sums of pairs Proof verification for $\lim_{n\to\infty}\frac{1}{n}(1+\sqrt2+\dots + \sqrt{n}) = +\infty$ In mathematics, which word should I use, "in" or "on" or "over"? Are there any two numbers such that multiplying them together is the same as putting their digits next to each other?

Recent Posts