Exercice corrigé : Records d'une permutation aléatoire (type Mines-Ponts)

Soit $n\geqslant2$ et $\sigma$ une permutation choisie uniformément dans $S_n$. Pour $i\in[\![1,n]\!]$, on dit que $i$ est un record si $\sigma(i)>\sigma(j)$ pour tout $j<i$ (ainsi $1$ est toujours un record). On note $A_i$ l'événement « $i$ est un record » et $R_n$ le nombre de records. On pose $H_n=\sum_{k=1}^n\frac1k$.

1. Calculer $P(R_n=1)$ et $P(R_n=n)$.
2. Montrer que $P(A_i)=\frac1i$ pour tout $i\in[\![1,n]\!]$. En déduire $E(R_n)$.
3. Soient $1\leqslant i<j\leqslant n$. Montrer que $P(A_i\cap A_j)=\frac1{ij}$. Que vaut $\mathrm{Cov}(\mathbf 1_{A_i},\mathbf 1_{A_j})$ ?
4. En déduire $V(R_n)$, puis l'inégalité $V(R_n)\leqslant H_n$. Donner $E(R_4)$ et $V(R_4)$.
5. Montrer que $H_n\geqslant\ln(n+1)$.
6. Soit $\varepsilon>0$. Montrer que $P\Big(\Big|\dfrac{R_n}{H_n}-1\Big|\geqslant\varepsilon\Big)\leqslant\dfrac1{\varepsilon^2\ln(n+1)}$ et conclure quant au comportement de $R_n$ pour $n$ grand.