Exercice 100

L'univers est $\mathfrak{S}_{n}$, muni de la probabilité uniforme. L'entier $i$ est un record de $\Sigma$ si et seulement si $\Sigma(i) = \max \Sigma\big(\llbracket 1\,,i \rrbracket\big)$ : cette condition ne fait intervenir que les valeurs prises sur $\llbracket 1\,,i \rrbracket$.

1. Soit $i < j$. On construit une permutation $\sigma$ dont $i$ et $j$ sont des records par choix successifs, dont le nombre ne dépend pas des choix précédents (lemme des bergers) :

• on choisit l'ensemble $A = \sigma\big(\llbracket 1\,,j \rrbracket\big)$, partie à $j$ éléments de $\llbracket 1\,,n \rrbracket$ : $\binom{n}{j}$ façons ;

• on choisit la restriction de $\sigma$ à $\llbracket j + 1\,,n \rrbracket$, bijection sur le complémentaire de $A$ : $(n - j)!$ façons (théorème 1) ;

• $j$ est un record si et seulement si $\sigma(j) = \max A$ : une seule façon ;

• il reste à placer les $j - 1$ valeurs de $A' = A \setminus \{\max A\}$ sur $\llbracket 1\,,j - 1 \rrbracket$. On choisit l'ensemble $B = \sigma\big(\llbracket 1\,,i \rrbracket\big) \subset A'$, de $\binom{j - 1}{i}$ façons ; $i$ est un record si et seulement si $\sigma(i) = \max B$ ; on place les autres valeurs de $B$ sur $\llbracket 1\,,i - 1 \rrbracket$, de $(i - 1)!$ façons, et celles de $A' \setminus B$ sur $\llbracket i + 1\,,j - 1 \rrbracket$, de $(j - 1 - i)!$ façons.

Chaque permutation de l'événement est obtenue exactement une fois, puisque tous les choix se lisent sur $\sigma$. Le nombre de ces permutations vaut $$\binom{n}{j}(n - j)!\,\binom{j - 1}{i}(i - 1)!\,(j - 1 - i)! = \frac{n!}{j!} \cdot \frac{(j - 1)!}{i!\,(j - 1 - i)!}\,(i - 1)!\,(j - 1 - i)! = \frac{n!}{j}\cdot\frac{1}{i},$$ et, en divisant par $n!$, $$\boxed{\mathrm{P}(I_{i} = 1, I_{j} = 1) = \frac{1}{ij} = \mathrm{P}(I_{i} = 1)\,\mathrm{P}(I_{j} = 1)}$$ Le résultat a été contrôlé par énumération de $\mathfrak{S}_{n}$ pour $n \leqslant 7$ ✓.

2. Les indicatrices $I_{i}$ suivent les lois $\mathcal{B}(\frac{1}{i})$, et, pour $i < j$, la question 1 et la proposition 23 (i) donnent $$\operatorname{Cov}(I_{i}, I_{j}) = \mathrm{E}(I_{i}I_{j}) - \mathrm{E}(I_{i})\,\mathrm{E}(I_{j}) = \frac{1}{ij} - \frac{1}{i}\cdot\frac{1}{j} = 0.$$ Les $I_{i}$ sont deux à deux décorrélées, et le théorème 13, avec la proposition 21, donne $$\boxed{\mathrm{V}(R_{n}) = \sum_{i=1}^{n} \frac{1}{i}\Big(1 - \frac{1}{i}\Big) = H_{n} - \sum_{i=1}^{n} \frac{1}{i^{2}} \leqslant H_{n}}$$ Pour $n = 100$, on trouve $\mathrm{E}(R_{100}) \approx 5{,}19$ et $\mathrm{V}(R_{100}) \approx 3{,}55$, soit un écart type d'environ $1{,}9$.

3. D'après le chapitre 20, $H_{n} - \ln n$ tend vers la constante d'Euler $\gamma$, donc $\frac{H_{n} - \ln n}{\ln n}$ tend vers $0$, et $H_{n} \sim \ln n$. Soit $\varepsilon > 0$, et $n_{0} \geqslant 2$ tel que $|H_{n} - \ln n| \leqslant \frac{\varepsilon}{2}\ln n$ pour $n \geqslant n_{0}$. Pour un tel $n$, l'inégalité triangulaire donne $$\Big|\frac{R_{n}}{\ln n} - 1\Big| \leqslant \frac{|R_{n} - H_{n}|}{\ln n} + \frac{|H_{n} - \ln n|}{\ln n} \leqslant \frac{|R_{n} - H_{n}|}{\ln n} + \frac{\varepsilon}{2}.$$ L'événement étudié est donc inclus dans $\big(|R_{n} - H_{n}| \geqslant \frac{\varepsilon}{2}\ln n\big)$. Comme $\mathrm{E}(R_{n}) = H_{n}$, l'inégalité de Bienaymé-Tchebychev et la question 2 donnent $$\mathrm{P}\Big(\Big|\frac{R_{n}}{\ln n} - 1\Big| > \varepsilon\Big) \leqslant \frac{4\mathrm{V}(R_{n})}{\varepsilon^{2}(\ln n)^{2}} \leqslant \frac{4H_{n}}{\varepsilon^{2}(\ln n)^{2}} \underset{n \to +\infty}{\sim} \frac{4}{\varepsilon^{2}\ln n},$$

À retenir. La variable $R_{n}$ n'est pas une somme de variables de même loi, et la loi faible des grands nombres ne s'applique pas telle quelle ; on refait sa démonstration, qui n'utilise que l'espérance, la variance et la décorrélation. La convergence est très lente : la majoration décroît comme $\frac{1}{\ln n}$, et les fluctuations de $R_{n}$ autour de $\ln n$ sont de l'ordre de $\sqrt{\ln n}$.