Maximum of a sequence is $o(\sqrt{n})$

Question

Quick context: This is a transposition of exercise 6.3 of Remco Van der Hofstad (2016) and it is relevant to some problem i encoutered in my research.

For each $n \in \mathbb{N}$, define a series of positive numbers $w_i^n$ with $1\leq i\leq n$. Also denote an uniformly chosen numbers by $w_U = W_n$ where $U$ is picked uniformly in $\{1,...,n\}$ (meaning $\mathbb{P}(W_n = w_i^n) = 1/n$ for any $i\leq n$). We also suppose that :

a)$W_n$ converges in distribution to a positive variable in the sense that $\lim_{n\rightarrow\infty}\mathbb{P}(W_n < t) = \mathbb{P}(W < t)$

b) $\lim_{n\rightarrow\infty} \mathbb{E}W_n = \mathbb{E}W$

c) $\lim_{n\rightarrow\infty} \mathbb{E}W_n^2 = \mathbb{E}W^2$

The question is to show that A. if a) and b) hold then $\max_{i\leq n} w_i^n = o(n)$ and that B. if a), b) and c) then $\max_{i\leq n} w_i^n = o(\sqrt{n})$.

As for my approach, I have noticed A. and B. are proven the same way. To prove A. I wanted to use the Borel Cantelli Lemma to show that $w_i^n/n > \epsilon$ only a finite amount of times. We have :

\begin{equation} \sum_{ i\leq n } 1_{ w_i^n/n > \epsilon } = \sum_{ i\leq n} 1_{w_i^n > n\epsilon} \end{equation}

which can be rewritten as

\begin{equation} \sum_{ i\leq n } 1_{ w_i^n/n > \epsilon } = \sum_{ d = \lceil n\epsilon \rceil } d\mathbb{P}( W^n = d) \end{equation}

The rightmost part can be majored by something close to the expectation of $W$ regardless of $n$. My intuition tells me that taking $n$ to $\infty$ feel like it should be enough to finish the proof but i feel like i did not use all the hypotheses... I'm open to any ideas about the proof.

PS: I asked an adjacent question yesterday which might be relevant.

Answer 1

First suppose that hypotheses (a) and (b) hold. I will write $w_{i,n}$ instead of $w_i^n$ for clarity.

Given $\epsilon>0$, the Monotone convergence theorem implies that there exists $M$ such that $E(W)-E(W \wedge M) <\epsilon$, where $\wedge$ indicates minimum. By (a) and the bounded convergence theorem, $$E(W\wedge M)=\int_0^M P(W \ge t) \, dt =\lim_{n \to \infty} \int_0^M P(W_n \ge t) \, dt =\lim_{n \to \infty} E(W_n\wedge M)\,.$$ Invoking (b), we infer that $$\lim_{n \to \infty} \frac1n \sum_{\{i:\, w_{i,n}>M\} } (w_{i,n}-M): = \lim_{n \to \infty}E[W_n-(W_n \wedge M)]= \tag{*} $$ $$ = E(W)-E(W\wedge M) <\epsilon \,. $$ If, for some $n$, $$\max_i w_{i,n}>2\epsilon n +M \tag{**}\,,$$ then the sum on the LHS of $(*)$ is greater than $2\epsilon n$, so $(**)$ can only occur for finitely many $n$. Therefore, $$\limsup_{n \to \infty} \frac1n \max_i w_{i,n} \le 2\epsilon \,.$$ Since $\epsilon>0$ is arbitrary, we conclude that this limsup must equal $0$.

---

---

If we assume (a) and (c) hold (hypothesis (b) is not needed here) , then applying the above result to $w_{i,n}^2$ instead of $w_{i,n}$, yields that $$\limsup_{n \to \infty} \frac1n \max_i w_{i,n}^2 =0\,,$$ as required.