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](https://math.stackexchange.com/questions/4540856/proof-that-max-id-in-sqrtn-tends-to-0-when-sum-i-d-in2) yesterday which might be relevant.



Maximum of a sequence is $o(\sqrt{n})$
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.


