Exercice 41

1. La variable $X_{i}$ suit une loi de Bernoulli ; il reste à calculer $P(X_{i}=1)$. On dénombre les listes présentant un record en $i$, c'est-à-dire telles que $\sigma(i)$ soit le plus grand des $i$ premiers termes :

• on choisit l'ensemble des valeurs occupant les $i$ premières places : $\binom{n}{i}$ choix ;

• la plus grande de ces valeurs est placée en position $i$, et les $i-1$ autres sont rangées dans les positions $1$ à $i-1$ : $(i-1)!$ choix ;

• les $n-i$ valeurs restantes sont rangées dans les positions suivantes : $(n-i)!$ choix.

Il y a donc $\binom{n}{i}(i-1)!\,(n-i)!=\frac{n!}{i}$ listes favorables, d'où : $$\boxed{P(X_{i}=1)=\frac{1}{i}\qquad\text{et}\qquad P(X_{i}=0)=1-\frac{1}{i}}$$ Ce résultat se comprend sans calcul : parmi les $i$ premiers termes, le plus grand occupe n'importe laquelle des $i$ positions avec la même probabilité.

2. Par linéarité, puisque $N=X_{1}+\dots+X_{n}$ : $$\boxed{E(N)=\sum_{i=1}^{n}\frac{1}{i}=H_{n}}$$

Interprétation : on retrouve le nombre harmonique $H_{n}$ de l'exercice 37 du chapitre 6, qui croît comme $\ln(n)$. Si l'on note pendant un siècle la température maximale de chaque année, sous l'hypothèse que le climat ne change pas, on n'attend en moyenne que $H_{100}\approx 5{,}19$ records : en observer beaucoup plus est un indice que l'hypothèse est fausse. Pour $n=8$, une simulation de $50\,000$ listes donne $2{,}720$ records en moyenne, contre $H_{8}\approx 2{,}718$.