Asymptotics for minimum of a sequence of random variables

Question

This is a question that I'm sure has been investigated before, but I have found no good search terms for.

Let $X_i$ be a sequence of random variables, independent and uniformly distributed in $[0,1]$. Let $Y_n=\min(X_1,\dots,X_n)$.

Is there an asymptotic which $Y_n$ almost surely follows? More precisely, is there some function $f:\mathbb N\to\mathbb R_+$ such that, almost surely, $Y_n\sim f(n)$?

If we ignore the fact that $Y_i$ are not independent, a Borel-Cantelli argument suggests $f(n)=\frac{\log n}{n}$: for any $c$, $\mathbb P(Y_n>c)=(1-c)^n\sim e^{-cn}$ for small $c$. Letting $c=d\frac{\log n}{n}$, this is asymptotic to $n^{-d}$, which has finite sum for $d>1$ and infinite for $d<1$, so we get $\limsup_{n\to\infty}\frac{Y_n}{(\log n)/n}\leq 1$ almost surely, with equality if we pretend we have independence.

Is the $\limsup$ of $\frac{Y_n}{(\log n)/n}$ actually equal to $1$ almost surely? Is the limit equal to $1$ almost surely? If not, what is the "lower" asymptotic for $Y_n$? For instance, do we at least have $Y_n=\Theta(\frac{\log n}{n})$ almost surely?

Note: I am aware that $nY_n$ converges to an exponential distribution, but I don't think that really helps answer the question, as we are interested in the entire sequence of $Y_n$ rather than their individual terms.

Answer 1

do we at least have $Y_n=\Theta(\frac{\log n}{n})$ almost surely?

The answer to this is no. It is not even true that $Y_n=\Theta(\frac{h(n)}{n})$ almost surely (a.s.) for any (deterministic or random) function $h$ such that $h(n)\to\infty$ a.s. (as $n\to\infty$). Indeed, suppose the contrary: that $\liminf_n nY_n=\infty$ a.s. Then, by the Fatou lemma, $$ \infty=E\infty\le\liminf_n EnY_n =\liminf_n n\frac1{n+1}=1, $$ a contradiction. $\quad\Box$

---

Let us now show that $Y_n\not\sim f(n)$ a.s. for any deterministic positive function $f$.

To prove this, suppose the contrary: that $Y_n\sim f(n)$ a.s. for some deterministic positive function $f$. Take any positive sequence $(a_n)$ such that $\sum_n a_n=\infty$. Then $$\sum_n P(X_n<a_n/2)=\sum_n a_n/2=\infty.$$ So, by the Borel--Cantelli lemma, events $\{X_n<a_n/2\}$ a.s. occur infinitely often (i.o.), that is, for infinitely many values of $n$. Therefore and because $\{X_n<a_n/2\}\subseteq\{Y_n<a_n/2\}$, we see that events $\{Y_n<a_n/2\}$ a.s. occur i.o. Recalling now the assumption that $Y_n\sim f(n)$ a.s., we conclude that $f(n)\le a_n$ i.o. In particular, $f(n)\le \frac1{n\ln n}=o(1/n)$ i.o.

So, $$Z_n:=nY_n\sim nf(n)=o(1) \tag{1}\label{1}$$ a.s. for $n=n_k$ and $k\to\infty$, where $(n_k)$ is a strictly increasing deterministic sequence of positive integers. Also, $EZ_n^2<2$. So, for $n$ as above, $$\begin{aligned} 1\leftarrow EZ_n&=EZ_n\,1(Z_n<4)+EZ_n\,1(Z_n\ge4) \\ &\le EZ_n\,1(Z_n<4)+EZ_n^2/4 \\ &<EZ_n\,1(Z_n<4)+1/2\to1/2 \end{aligned}$$ by \eqref{1} and dominated convergence. So, we have a contradiction. $\quad\Box$

---

In fact, $Y_n\not\sim f(n)$ even in probability for any positive deterministic function $f$.

Indeed, suppose that $Y_n\sim f(n)$ in probability for some positive deterministic function $f$. Then, by the Fatou lemma, $$1=E\lim_n\frac{Y_n}{f(n)}\le \liminf_n\frac{EY_n}{f(n)} =\liminf_n\frac{1}{(n+1)f(n)},$$ so that $f(n)\lesssim1/n$. So, $nf(n)\to c$ for some real $c\ge0$, $n=n_k$, and $k\to\infty$, where $(n_k)$ is some strictly increasing sequence of positive integers. So, for such $n$ and $Z_n$ as above, $$Z_n\to c$$ in probability. Also, $EZ_n\to1$, $EZ_n^2\to2$, and $EZ_n^4\to24$. Take now any real $A>0$. Then $$E(Z_n-c)^2=E(Z_n^2-2cZ_n+c^2)\to C:=2-2c+c^2,$$ whereas, for $n$ as above, $$\begin{aligned} E(Z_n-c)^2 &=E(Z_n-c)^2\,1((Z_n-c)^2\le A)+E(Z_n-c)^2\,1((Z_n-c)^2>A) \\ &\le E(Z_n-c)^2\,1((Z_n-c)^2\le A)+E(Z_n-c)^4/A \\ &\le E(Z_n-c)^2\,1((Z_n-c)^2\le A)+(EZ_n^4+c^4)/A \\ &\to 0+(24+c^4)/A \end{aligned}$$ by dominated convergence. We conclude that $0<C\le(24+c^4)/A$ for all real $A>0$, a contradiction. $\quad\Box$

Answer 2

For $g(n)$ a decreasing function, we have $\limsup Y_n/g(n)\geq 1$ if and only if $Y_n> g(n)(1-\epsilon)$ infinitely often. Based on an approach suggested by Aleksei Kulikov, if $n \in [2^k, 2^{k+1}]$ then this implies $X_m > g(n) (1-\epsilon) \geq g(2^{k+1} ) (1-\epsilon)$ for all $m \leq 2^k $ for infinitely many $k$. This is an event with probability $\approx e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ and it can only occur with positive probability for infinitely many $k$ if the sum of these probabilities $\sum_{k=1}^\infty e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ is positive (this direction of Borel-Cantelli not requiring independence).

So $\limsup Y_n/g(n)\geq 1$ with probability $0$ for $g(n) = C \log \log n/n$ as soon as $C>2$.

---

Let $A_n$ be the event that $Y_{2^n} \geq C (\log n)/2^n$. Then $\mathbb P(A_n) \approx n^{-C}$. For $n<m$, the intersection $A_n \cap A_m$ occurs when $X_k \geq C ( \log n)/2^n$ for $k\leq 2^n$ and $X_k \geq C (\log m)/2^m$ for $2^m < k \leq 2^n$ which has probability $$\approx e^{ - C ( \log n + \frac{2^m-2^n}{2^m} \log m )} = e^{ C 2^{n-m} \log m} e^{ - C \log n} e^{-C \log m}. $$

This is $(1+o(1) ) n^{-C} m^{-C}$ as long as $m-n > \log N$, since $e^{ C 2^{ -\log_2 N } \log m } \leq e^{ C 2^{-\log N} \log N} = 1+o(1)$. When $m$ is close to $n$, this probability is still bounded by $e^{- C\log n}$. This gives

$$\sum_{m,n \leq N} \mathbb P(A_n \cap A_m) \leq (1+o(1))\sum_{n,m\leq N} n^{-C} m^{-C} + \sum_{\substack{ n,m \leq N \\ |n-m| \leq \log \log N}}e^{ - C \log n} \approx (1+o(1)) ((1-C) N^{1-C})^2 + 2 (1-C) N^{1-C} \log N = (1+o(1)) ((1-C) N^{1-C})^2 $$ as long as $C<1$.

Now $\sum_{n=1}^N \mathbb P(A_n) \approx N^{1-C} / (1-C)$.

So the ratio$$ \frac{ (\sum_{n=1}^N \mathbb P(A_n) )^2}{ \sum_{m,n \leq N} \mathbb P(A_n \cap A_m) }$$ converges to $1$. By Kochen-Stone, this implies that $A_n$ occurs infinitely often with probability $1$.

In other words, $\limsup Y_n / (\log \log n/n) \geq 1$ with probability $1$.

---

So $\limsup Y_n / (\log \log n/n) \in [1,2]$ with probability $1$. We cannot change the limsup by changing finitely many values of $X_n$ to something nonzero and so by Kolmogorov's zero-one law, there is a fixed deterministic value in $[1,2]$ that the limsup approaches. I am not sure if this is possible to compute.

Answer 3

(This is to address the previous comment by the OP. Since the previous answer is already long, this is being done in a separate answer.)

The answer to the mentioned comment is the following: there is no positive nonincreasing deterministic sequence $(g_n)$ such that $g_n\to0$ (as $n\to\infty$) and $\liminf_n \frac{Y_n}{g_n}=1$ a.s.

More specifically, let $H$ denote the set of all positive nonincreasing deterministic sequences $h=(h_n)$ such that $h_n\to0$. Let us say that $h\in H$ is a lower bound for the $Y_n$'s if a.s. the events $\{Y_n<h_n\}$ occur only finitely often (f.o.), that is, only for finitely many values of $n$. Similarly, let us say that $h\in H$ is a lower bound for the $X_n$'s if a.s. the events $\{X_n<h_n\}$ occur only f.o.

The key observation is that $h\in H$ is a lower bound for the $Y_n$'s if and only if $h$ is a lower bound for the $X_n$'s. See the details on this at the end of this answer.

On the other hand, by the Borel--Cantelli lemma, $h\in H$ is a lower bound for the $X_n$'s if and only if $$\sum_n P(X_n<h_n)=\sum_n \min(1,h_n)<\infty.$$

Thus, $h\in H$ is a lower bound for the $Y_n$'s if and only if $$\sum_n h_n<\infty.$$

So, if $h\in H$ is a lower bound for the $Y_n$'s, then $ah$ is a lower bound for the $Y_n$'s for any real $a>0$. Moreover, if $h\in H$ is a lower bound for the $Y_n$'s, then $h/b\in H$ is a lower bound for the $Y_n$'s for some sequence $b\in H$ (so that $b_n\to0$).

We conclude that, indeed, there is no positive nonincreasing deterministic sequence $(g_n)$ such that $g_n\to0$ and $\liminf_n \frac{Y_n}{g_n}=1$ a.s.

Furthermore, for any positive real (deterministic) $A$ and $B$, there is no positive nonincreasing deterministic sequence $g=(g_n)$ such that $g_n\to0$ and $\liminf_n \frac{Y_n}{g_n}\in[A,B]$ a.s. Indeed, the latter condition would imply that $\frac A2\,g$ is a lower bound for the $Y_n$'s, while $2B\,g$ is not a lower bound for the $Y_n$'s -- which contradicts what was noted above: if $h\in H$ is a lower bound for the $Y_n$'s, then $ah$ is a lower bound for the $Y_n$'s for any real $a>0$.

Details: Note that $Y_n\le X_n$ for all $n$. So, a.s. $$(\text{the events $\{Y_n<h_n\}$ occur only f.o.}) \implies(\text{the events $\{X_n<h_n\}$ occur only f.o.}).$$ Vice versa, suppose that a.s. the events $\{X_n<h_n\}$ occur only f.o. -- that is, for some random positive integer $N$ and all $n>N$ we a.s. have $X_n\ge h_n$. For each $n$ there is some random $K_n\in\{1,\dots,n\}$ such that $Y_n=X_{K_n}$. Moreover, $Y_n\to0$ a.s. and $X_k>0$ for all $k$ a.s. So, $K_n\to\infty$ a.s. So, there is some random positive integer $N_1\ge N$ such that $k_n>N$ a.s. for all $n>N_1$. So, for all $n>N_1$, a.s. $$Y_n=X_{K_n}\ge h_{K_n}\ge h_n,$$ so that a.s. the events $\{X_n<h_n\}$ occur only f.o. Thus, $$(\text{the events $\{X_n<h_n\}$ occur only f.o.}) \implies(\text{the events $\{Y_n<h_n\}$ occur only f.o.})$$ and hence $$(\text{the events $\{Y_n<h_n\}$ occur only f.o.}) \iff(\text{the events $\{X_n<h_n\}$ occur only f.o.}). \quad\Box$$

Answer 4

By Iosif Pinelis's answer, there is no function we can really call the $\liminf$.

I think Will Sawin / Aleksei Kulikov showed $\limsup_{n \to \infty} \frac{Y_n}{\log\log n / n} = 1$ almost surely without realizing it.

Will Sawin's answer shows the lower bound. Here's how they showed the upper bound.

Take any $\lambda > 1$ and $\varepsilon > 0$, and note $$\mathbb{P}\bigl[Y_{\lambda^k} > (1+\varepsilon)\frac{\log k}{\lambda^k}\bigr] = \Bigl(1-(1+\varepsilon)\frac{\log k}{\lambda^k}\Bigr)^{\lambda^k} \approx k^{-1-\varepsilon},$$ which is summable in $k$. So, by Borel-Cantelli, $Y_{\lambda^k} \le (1+\varepsilon)\frac{\log k}{\lambda^k}$ for all large $k$. Now, for any large $n$, if $\lambda^k \le n < \lambda^{k+1}$, then $$Y_n \le Y_{\lambda^k} \le (1+\varepsilon)\frac{\log k}{\lambda^k} \le \lambda(1+\varepsilon)\frac{\log \log n}{n}.$$ By choosing $\lambda$ sufficiently close to $1$ and $\varepsilon$ to $0$, we're done.