Sur les permutations aléatoires

Menu

1. Nombre de points fixes.

On tire au hasard une permutation aléatoire $\omega$, et on s'intéresse à ses points fixes (c'est-à-dire aux éléments $i \in \lc 1,n \rc$ vérifiant $\omega(i)=i$ ).
On note $X$ la variables aléatoire égale au nombre de ses points fixes.

• Quelle est la probabilité de l'évènement $[X=n]$?
• Quelle est la probabilité de l'évènement $[X=n-1]$?
• Quelle est la probabilité de l'évènement $[X=n-2]$?
• Pour tout $i \in \lc 1,n \rc$, on note $Y_i$ la variable aléatoire égale à $1$ si le point $i$ est fixe et $0$ sinon.
  Déterminer la loi de $Y_i$.
  Pour $i\neq j$, les variables $Y_i$ et $Y_j$ sont-elles indépendantes?
• Relier $X$ aux $Y_i$, $1\leq i\leq n$, et en déduire l'espérance et la variance du nombre de points fixes d'une permutation aléatoire.
• Calculer la probabilité qu'une permutation aléatoire soit un dérangement, c'est-à-dire que l'évènement $[X=0]$ soit réalisé.
• Donner alors la loi de $X$.
• La variable $X$ dépend en fait de $n$; on la note donc $X_n$.
  Pour $k\in \mathbb{N}$, déterminer $\displaystyle \lim_{ n \rightarrow +\infty } \mathbb{P} ( X_n = k )$.

• $X=n$ signifie que tous les points sont fixes, la permutation $\omega$ est donc l'identité.
  Il n'y a qu'une seule façon de l'obtenir, donc la probabilité cherchée est : $$ \mathbb{ P} ( X=n ) = \frac{ 1}{ n! } $$
• $X= n-1$ est impossible: en effet, un point qui n'est pas fixe prend nécessairement la position d'un autre point, ce qui fait au minimum deux points non fixes; une permutation ne peut donc pas laisser un seul point non fixe.
  La probabilité cherchée est donc : $$ \mathbb{P} ( X=n-1 ) = 0 $$
• $X=n-2$ signifie que la permutation $\omega$ laisse seulement deux points non fixes.
  On choisit les deux points qui ne seront pas fixes: $\displaystyle \binom{n}{2}$ possibilités.
  On les permute: $1$ seule possibilité.
  Les autres points sont fixes: $1$ seule possibilité pour chaque.
  La probabilité cherchée est donc : $$ \mathbb{ P } ( X=n-2 ) = \frac{ \displaystyle \binom{n}{2} }{ n! } $$ On aurait pu aussi utiliser le fait que $S_n$ comporte $\displaystyle \binom{n}{2}$ transpositions (qui sont les permutations ayant exactement $n-2$ points fixes).
• $Y_i( \Omega ) = \{ 0;1 \}$ donc $Y_i$ suit une loi de Bernoulli de paramètre $\mathbb{ P } ( Y_i = 1 )$.
  $Y_i=1$ signifie que le point $i$ est fixe; les $n-1$ autres peuvent l'être ou ne pas l'être.
  Cela revient à permuter de manière quelconque ces $n-1$ autres points, donc : $$\mathbb{ P} ( Y_i=1 ) = \frac { (n-1)! }{ n! } = \frac{1}{n} $$ Ainsi $\displaystyle Y_i \sim \mathcal{ B } \left( \frac{ 1 }{ n } \right)$.
  De même, $\big[ Y_i = 1 \big] \cap \big[ Y_j = 1 \big]$ signifie que les points $i$ et $j$ sont fixes.
  Comme cela revient à permuter de manière quelconque les $n-2$ autres points : $$ \mathbb{ P } ( Y_i=1 , Y_j=1 ) = \frac{ (n-2) ! }{ n ! } = \frac{ 1 }{ n(n-1) } \neq \mathbb{P} ( Y_i=1) \times \mathbb{P} ( Y_j=1 ) $$ Ceci prouve que $Y_i$ et $Y_j$ ne sont pas indépendantes.
• Comme les $Y_i$ ne prennent comme valeurs que $0$ ou $1$, la variable $\displaystyle \sum_{ i=1 }^n Y_i$ compte le nombre d'indice $i$ pour lesquels $Y_i$ prend la valeur $1$, et donc elle est égale au nombre de points fixes de la permutation aléatoire : $$ X = \sum_{ i=1 }^n Y_i $$
• Par linéarité de l'espérance : $$ \mathbb{ E } (X) = \sum_{i=1}^n \mathbb{E} ( Y_i ) = \sum_{ i=1 }^n \frac{1}{n} = 1$$ (Le lecteur cultivé aura remarqué que ce résultat est une conséquence directe de la formule de Burnside, puisque le groupe symétrique agit transitivement sur $\lc 1,n \rc$ : http://fr.wikipedia.org/wiki/Action_de_groupe_%28math%C3%A9matiques%29#Formule_des_classes.2C_formule_de_Burnside )
  D'autre part, par propriété de la variance : $$ V (X) = \sum_{i=1}^n V( X_i ) + 2 \sum_{ 1\leq i<j \leq n} \hbox{Cov} ( Y_i,Y_j ) $$ On sait que $V ( Y_i ) = \displaystyle \frac{1}{n} \left( 1 - \frac{1}{n} \right)$.
  De plus $Y_i Y_j$ ne prend que les valeurs $0$ ou $1$, et suit donc une loi de Bernoulli de paramètre $\mathbb{ P } ( Y_iY_j = 1 )$.
  Mais $\big[ Y_iY_j = 1 \big] = \big[ Y_i=1 \big] \cap \big[ Y_j=1 \big]$, donc d'après le calcul de la question d), $Y_i Y_j$ suit la loi de Bernoulli de paramètre $\displaystyle \frac{1}{ n(n-1) }$.
  On en déduit que $\mathbb{E} ( Y_i Y_j ) = \displaystyle \frac{1}{ n(n-1) } $, puis que : $$ \hbox{Cov}  ( Y_i, Y_j ) = \mathbb{E} ( Y_i Y_j ) - \mathbb{E} ( Y_i) \mathbb{[E} ( Y_j) = \frac{1}{ n(n-1) } - \frac{1}{n^2} = \frac{1}{ n^2 (n-1) } $$ En remarquant que ce résultat ne dépend pas des valeurs de $i$ et $j$, et que la somme $\displaystyle \sum_{ 1\leq i<j \leq n } $ dispose de $ \displaystyle \binom{n}{2} $ termes, on obtient : $$ V(X) = n\times\frac{1}{n} \left( 1 - \frac{1}{n} \right)  + 2 \binom{n}{2} \times \frac{1}{ n^2(n-1) } = 1 $$
• On remarque que $ \displaystyle [X=0] = \bigcap_{i=1}^n \big[ Y_i=0 \big]$.
  Donc : $$\begin{array}{rcl} \mathbb{P} ( X=0 ) &=&\displaystyle 1 - \mathbb{P} \left( \bigcup_{i=1}^n \big[Y_i = 1 \big] \right) \\ &=&\displaystyle 1 - \sum_{k=1}^{n} (-1)^{k-1} \left( \sum_{ 1 \leq i_1 < i_2 < \dots < i_k \leq n } \mathbb{P} \big( [Y_{i_1} =1 ] \cap [ Y_{i_2} = 1 ] \cap \dots \cap [ Y_{i_k} = 1 ] \big) \right) \end{array}$$ d'après la formule du crible de Poincaré.
  Or si $1\leq i_1 < \dots < i_k \leq n$, l'évènement $[Y_{i_1} =1 ] \cap [ Y_{i_2} = 1 ] \cap \dots \cap [ Y_{i_k} = 1 ] $ correspond aux permutations qui laisse fixes les points $i_1$, $\dots$, $i_k$, les $n-k$ autre points pouvant être fixes ou ne pas l'être.
  Ceci revient à permuter ces $n-k$ autres points, donc : $$ \mathbb{P} \big( [Y_{i_1} =1 ] \cap [ Y_{i_2} = 1 ] \cap \dots \cap [ Y_{i_k} = 1 ] \big) * = \frac{ ( n - k ) ! }{ n ! } $$ Comme cette quantité ne dépend pas des valeurs de $i_1$, $\dots$, $i_k$ (mais seulement de $k$), et comme la somme $\displaystyle \sum_{ 1 \leq i_1 < \dots < i_k \leq n } $ comporte $\displaystyle \binom{ n }{ k }$ termes, on a : $$ \sum_{1\leq i_1 < \dots < i_k \leq n } \mathbb{P} \big( [ Y_{i_1} = 1 ] \cap \dots \cap [ Y_{i_k} = 1 ] \big) = \binom{n}{k} \frac{ ( n-k ) ! }{ n ! } = \frac{ 1 }{ k ! } $$ Ainsi : $$ \mathbb{P} ( X=0 ) = 1 - \sum_{k=1}^n (-1)^{k-1} \frac{1}{ k! } = \sum_{k=0}^n \frac{ (-1)^k }{ k ! } $$ (Il est classique que cette quantité a pour limite $\displaystyle \frac{1}{ \hbox{e} } $ lorsque $ n \rightarrow +\infty$.)
• Pour commencer, remarquons que $X ( \Omega ) = \lc 0,n \rc $.
  En effet: une permutation a au minimum $0$ point fixe (c'est un dérangement), et au maximum $n$ points fixes (c'est l'identité).
  D'autre part si $k\in \lc 0,n \rc$ , l'évènement $[X=k]$ correspond aux permutations qui ont exactement $k$ points fixes.
  Pour les dénombrer, on compte le nombre de possibilités de choisir les $k$ points qui seront fixes et on multiplie par le nombre façons de permuter les $n-k$ autres points de telle sorte qu'ils soient tous non fixes.
  On a $\displaystyle \binom{n}{k} $ choix des $k$ points qui seront fixes.
  D'après f), $n! \mathbb{P} (X = 0 ) =n ! \displaystyle \sum_{k=0}^n \frac{ (-1)^k }{ k ! }$ correspond au nombre de permutations de $ \lc 1,n \rc $ qui ne laissent aucun point fixe.
  Donc le nombre de façons de permuter $n-k$ points de telle sorte qu'aucun ne soit fixe est : $ \displaystyle ( n-k ) ! \sum_{ i=0 }^{n-k} \frac{ (-1)^i }{ i ! } $.
  On en déduit que: $$ \mathbb{P} ( X=k ) = \frac{1}{ n ! } \binom{n}{k}  ( n-k ) ! \sum_{ i=0 }^{n-k} \frac{ (-1)^i }{ i ! } = \frac{1}{ k ! } \sum_{i=0}^{ n-k } \frac{ (-1)^i }{ i ! } $$
• Soit $ k \in \mathbb{N} $.
  On a : $$ \forall n \geq k, \quad \mathbb{P} ( X_n =k ) = \frac{1}{ k ! } \sum_{i=0}^{n-k} \frac{ (-1)^i }{ i ! } $$ donc : $$ \forall k\in\mathbb{N},\quad \lim_{n\rightarrow +\infty} \mathbb{P} ( X_n = k ) = \frac{ {\rm e}^{-1} }{ k ! } $$ On vient en fait de montrer que $ X_n \underset{ n\rightarrow +\infty}{ \overset{ ( \mathcal{L} ) }{ \longrightarrow } } \mathcal{P} ( 1 ) $.

MASQUER

2. Records vers le haut.

Soit $\omega:\lc1,n\rc\ra\lc1,n\rc$ une permutation.
Pour $k\in\lc2,n\rc$, on dit que $\omega$ possède un record vers le haut au rang $k$ lorsque : $\forall i\in\lc1,k-1\rc$, $\omega(k)>\omega(i)$.
Par convention, on dira que toute permutation $\omega$ possède un record vers le haut au rang $1$.
Si on interprète l'expérience aléatoire comme $n$ tirages successifs sans remise dans une urne de $n$ boules numérotées de $1$ à $n$, un record vers le haut au $k$-ième signifie que le numéro obtenu est strictement plus grand que les numéros obtenus aux tirages précédents.

1. Quelle est la probabilité qu'une permutation donne un seul record vers le haut? qu'elle donne $n$ records vers le haut?
2. 1. Pour $(k,j)\in\lc2,n\rc^2$, quelle est la probabilité qu'une permutation donne un record vers le haut au rang $k$ avec $\omega(k)=j$?
      (C'est-à-dire que les $n$ tirages sans remise donne le numéro $j$ au $k$-ième tirage et que les tirages précédents ont donné un numéro strictement inférieur à $j$).
   2. Pour $k\in\lc2,n\rc$, déterminer la probabilité qu'une permutation donne un record vers le haut au rang $k$.
   3. Comment aurait-on pu procéder pour trouver ce résultat directement?
3. On note $X_n$ le nombre de records obtenus.
   Pour tout $k\in\lc1,n\rc$, on note aussi $Y_k$ = $1$ si on a obtenu un record au rang $k$ et $0$ sinon.
   1. Pour $k\in\lc1,n\rc$, quelle est la loi de $Y_k$? Pour $k\neq j$, montrer que $Y_k$ et $Y_j$ sont indépendantes.
   2. En déduire $\mathbb{E}(X_n)$ et $V(X_n)$.
      Donner en un équivalent lorsque $n\to+\infty$.
   3. Déterminer la fonction génératrice de $X_n$. $ \newcommand{\stir}[2]{\displaystyle\genfrac{[}{]}{0pt}{}{#1}{#2}} $
   4. On définit les nombres de Stirling non signés de première espéce, notés $\stir{n}{k}$, par la formule : $X(X+1)\dots(X+n-1)=\displaystyle\sum_{k=1}^n \stir{n}{k} X^k$.
      Donner la loi de $X_n$ en fonction des $\stir{n}{k}$, pour $k\in\lc1,n\rc$.

1. On note $A$ l'évènement "la permutation ne donne qu'un seul record vers le haut".
   $\omega\in A$ signifie que seul le premier rang donne un record vers le haut.
   Ceci équivaut à la condition $\omega(1)=n$ (le premier tirage donne la boule numéro $n$).
   On a donc $\hbox{Card}(A)=(n-1)!$ et : $$\p(A)=\dfrac{(n-1)!}{n!}=\dfrac{1}{n}$$ On note $B$ l'évènement "la permutation donne $n$ records vers le haut".
   $\omega\in B$ signifie que $\omega(1)<\omega(2)<\dots<\omega(n)$, et donc que $\omega$ est l'application identité.
   Ainsi $\hbox{Card}(B)=1$ et : $$\p(B)=\dfrac{1}{n!}$$
2. 1. On note $E_{j,k}$ l'évènement "la permutation donne un record vers le haut au rang $k$ avec la valeur $j$".
      Si $j<k$ il est clair que $E_{j,k}=\emptyset$, et donc que $\p(E_{j,k})=0$.
      Supposons $j\geq k$.
      Dénombrons les permutations $\omega$ qui appartiennent à $E_{j,k}$ :
      • la valeur de $\omega(k)$ est fixée égale à $j$ : $1$ seule possibilité
      • les valeurs de $\omega(1)$, $\omega(2)$, $\dots$, $\omega(k-1)$ doivent être prises entre $1$ et $j-1$ : le nombre de possibilités est égal au nombre d'arrangements de $k$ éléments de $\lc1,j-1\rc$, c'est-à-dire à $\displaystyle\binom{j-1}{k-1}\times (k-1)!$
      • les valeurs de $\omega(k+1)$, $\omega(k+2)$, $\dots$, $\omega(n)$ sont choisies quelconques (deux à deux distinctes) parmi les $n-k$ valeurs restantes: $(n-k)!$ possibilités.
      On en déduit que $\hbox{Card}(E_{j,k})=\displaystyle\binom{j-1}{k-1}\times(k-1)!\times(n-k)!$ puis que : $$\p(E_{j,k})=\dfrac{\displaystyle\binom{j-1}{k-1}\times(k-1)!\times(n-k)!}{n!}$$
   2. On note $R_k$ l'évènement "la permutation donne un record vers le haut au rang $k$".
      On remarque que $R_k=\displaystyle\bigcup_{j=k}^n E_{j,k}$ et que les $E_{j,k}$, pour $j\in\lc k,n\rc$, sont deux à deux incompatibles.
      L'additivité de $\p$ donne donc : $$\begin{array}{rcl} \p(R_k)&=&\displaystyle\sum_{j=k}^n \p(E_{j,k})\\ &=&\displaystyle\sum_{j=k}^n \dfrac{\displaystyle\binom{j-1}{k-1}\times(k-1)!\times(n-k)!}{n!} \\ &=&\displaystyle \dfrac{(k-1)!\times (n-k)!}{n!} \sum_{j=k}^n \displaystyle\binom{j-1}{k-1} \\ &=&\displaystyle\dfrac{1}{k\displaystyle\binom{n}{k}} \sum_{j=k}^n \displaystyle\binom{j-1}{k-1}\end{array}$$ Mais : $$ \sum_{j=k}^n \displaystyle\binom{j-1}{k-1} = \sum_{j=k-1}^{n-1} \displaystyle\binom{j}{k-1} = \sum_{j=k-1}^{n-1} \left(\displaystyle\binom{j+1}{k} - \displaystyle\binom{j}{k} \right) = \displaystyle\binom{n}{k} - \displaystyle\binom{k-1}{k}=\displaystyle\binom{n}{k} $$ grâce à la formule d'additivité de Pascal et aux propriétés des sommes télescopiques.
      Finalement : $$\p(R_k)=\dfrac{1}{k} $$ Remarquez que cette formule est encore valable pour $k=1$.
   3. On peut retrouver directement ce résultat grâce au raisonnement suivant.
      Pour avoir un record vers le haut au rang $k$ :
      • on choisit les $k$ premiers nombres puis on les ordonne de telle sorte que le $k$-ème soit le plus grand : $\displaystyle\binom{n}{k}\times (k-1)!$ possibilités
      • on choisit ensuite les $n-k$ nombres restants et on les ordonne de façon quelconque : $\displaystyle\binom{n-k}{n-k}\times (n-k)!=(n-k)!$ possibilités.
      Le nombre total de possibilité étants $n!$ on a donc : $$\p(R_k)=\dfrac{ \displaystyle\binom{n}{k} (k-1)! (n-k)! }{ n!} = \dfrac{1}{k} $$
3. 1. D'après la question 2.b, $Y_k\sim\mathcal{B}\left(\dfrac{1}{k}\right)$.
      Supposons $k< j$.
      Déterminons $\p(Y_k=1,Y_j=1)=\p(''\hbox{record au }k-\hbox{ième et au }j-\hbox{ième rangs}'')$.
      Avec la technique de dénombrement du 3.c, on compte le nombre de permutations qui donnent un record aux rangs $k$ et $j$ (au moins) :
      • on choisit les $j$ premiers nombres : $\displaystyle\binom{n}{j}$ possibilités
      • le plus grand prend la position $j$ : $1$ possibilité
      • on choisit parmi les $j-1$ restants les $k$ premiers nombres : $\displaystyle\binom{j-1}{k}$ possibilités
      • on les ordonne de telle sorte d'avoir un record au rang $k$ : $(k-1)!$ possibilités
      • sur les $j$ premiers nombres choisis, il en reste $j-k-1$ à répartir entre les tirages
        $k+1$, $k+2$, $\dots$, $j-1$ donc $(j-k-1)!$ possibilités
      • on choisit ensuite les $n-j$ nombres restants et on les répartit sur les tirages $j+1$, $j+2$, $\dots$, $n$ : $\displaystyle\binom{n-j}{n-j}\times (n-j)!=(n-j)!$ possibilités.
      On en déduit que : $$\begin{array}{rcl} \p(Y_k=1,Y_j=1)&=&\dfrac{ \displaystyle\binom{n}{j}\times 1\times\displaystyle\binom{j-1}{k} \times (k-1)!\times (j-k-1)!\times (n-j)!}{n!}\\ &=&\dfrac{1}{k\times j}\\ &=&\p(Y_k=1)\times\p(Y_j=1)\\ &=&1\end{array}$$ On vérifie facilement que cette formule est vraie pour tout $k\neq j$.
      Puisque les variables $Y_k$ et $Y_j$ suivent des lois de Bernoulli, il est classique d'en déduire leur indépendance.
   2. On remarque que $X_n=\displaystyle\sum_{k=1}^n Y_k$, et donc par linéarité de l'espérance : $$\mathbb{E}(X_n)=\sum_{k=1}^n \mathbb{E}(Y_k) =\sum_{k=1}^n \dfrac{1}{k} $$ D'autre part, comme les $Y_k$, pour $k\in\lc1,n\rc$, sont deux à deux indépendants : $$ V(X_n)=\sum_{k=1}^n V(Y_k) = \sum_{k=1}^n \dfrac{1}{k}\left(1-\dfrac{1}{k}\right) = \sum_{k=1}^n \dfrac{1}{k}-\sum_{k=1}^n\dfrac{1}{k^2}$$ Il est classique que $\mathbb{E}(X_n)\underset{n\to+\infty}{\sim} \ln(n)$ et que $V(X_n)\underset{n\to+\infty}{\sim}\ln(n)$.
   3. Toujours grâce à l'indépendance des $Y_k$, on a pour tout $t\in\mathbb{R}$ : $$ G_{X_n}(t) = \prod_{k=1}^n G_{Y_k}(t)=\prod_{k=1}^n \left(\dfrac{1}{k}t+1-\dfrac{1}{k}\right)=\dfrac{1}{n!} \prod_{k=0}^{n-1} (t+k) $$
   4. On a donc, pour tout $t\in\mathbb{R}$ : $$ G_{X_n}(t)= \dfrac{1}{n!}\prod_{k=1}^n \stir{n}{k} t^k $$ On en déduit que $X_n(\Omega)=\lc1,n\rc$ et : $$\forall k\in\lc1,n\rc,\quad \p(X_n=k)= \dfrac{\displaystyle\stir{n}{k}}{n!} $$
      Pour aller plus loin :
      • il est intéressant de remarquer que le théorème central limite (et le lemme de Slutsky) donne $\dfrac{X_n-\ln(n)}{\sqrt{\ln(n)}} \underset{n\to+\infty}{\overset{(\mathcal{L})}{\ra} }\mathcal{N}(0,1)$.
      • si on note $Z_n$ le nombre de record vers le bas (il y a record vers le bas au rang $k$ si $\omega(k)<\omega(i)$ pour tout $i\in\lc 1,k-1\rc$), alors $Z_n$ a la même loi que $X_n$.

MASQUER

3. Nombre de cyles (= orbites) d'une permutation aléatoire.

On note $X_n$ le nombre de cycles d'une permutation aléatoire de $\lc1,n\rc$ dans sa décomposition canonique (en comptant les cycles de longueur $1$).

1. Etablir la relation suivante : $$\forall k\in\lc1,n+1\rc,\quad (n+1)\p(X_{n+1}=k)=\p(X_n=k-1)+n\p(X_n=k)$$
2. En déduire $\E(X_n)$.
   Donner en un équivalent lorsque $n\to+\infty$.
3. Déterminer la fonction génératrice de $X_n$. Que peut-on en déduire sur sa loi?
4. En déduire $V(X_n)$. Donner en un équivalent lorsque $n\to+\infty$.

1. $X_n(\Omega)=\lc1,n\rc$.
   Pour $k\in\lc1,n\rc$, on note $c_n(k)$ le nombre de permutations de $\lc1,n\rc$ qui se décompose en exactement $k$ cycles à supports disjoints, c'est-à-dire le cardinal de l'évènement $[X_n=k]$.
   Considérons une permutation $\omega$ de $\lc1,n+1\rc$ qui se décompose en exactement $k$ cycles à supports disjoints.
   Deux cas se présentent :
   • $\omega(n+1)=n+1$. La restriction de $\omega$ à $\lc1;n\rc$ est une permutation qui se décompose en exactement $k-1$ cycles à supports disjoints. Ce cas présente donc $c_{n}(k-1)$ possibilités.
   • $\omega(n+1)\neq n+1$. Le cycle qui contient $n+1$ est donc de longueur supérieur ou égale à $2$. En effaçant $n+1$ de ce cycle, on obtient une permutation de $\lc1,n\rc$ qui se décompose en exactement $k$ cycles à support disjoints. Obtenir un permutation $\omega$ de $\lc1,n+1\rc$ qui se décompose en $k$ cycles à supports disjoints, et telle que $\omega(n+1)\neq n+1$, revient donc à choisir une valeur $j\in\lc1,n\rc$ et une permutation de $\lc1,n\rc$ dans laquelle on ajoute $n+1$ juste avant $j$ dans le cycle qui contient $j$. Ce cas présente donc $n\times c_n(k)$ possibilités.
   D'après le lemme des bergers on a donc la relation de récurrence : $$ c_{n+1}(k)=c_n(k-1)+n c_n(k)$$ En divisant par $(n+1)!$ on en déduit que : $$ \forall k\in\lc2;n\rc,\quad (n+1)\p(X_{n+1}=k) = \p(X_n=k-1)+n\p(X_n=k) $$ et cette formule est vraie aussi si $k=1$ ou $k=n+1$.
2. 1. Donc : $$\begin{array}{rcl} (n+1)\E(X_{n+1})&=&\displaystyle(n+1)\sum_{k=1}^{n+1} k\p(X_{n+1}=k) \\ &=& \displaystyle\sum_{k=0}^n (k+1)\p(X_n=k)+n\sum_{k=1}^{n+1}k\p(X_n=k)\\ &=&\displaystyle(n+1)\E(X_n) + 1\end{array}$$ Comme $\E(X_1)=1$, on en déduit facilement par récurrence que : $$\E(X_n)=\sum_{k=1}^n \frac{1}{k}\underset{n\to+\infty}{\sim}\ln(n)$$
   2. De même pour tout $t\in\R$ : $$\begin{array}{rcl} (n+1)\times G_{X_{n+1}}(t) &=&\displaystyle(n+1) \sum_{k=1}^{n+1} t^k \p(X_{n+1}=k) \\ & =& \displaystyle\sum_{k=0}^{n+1} t^{k+1} \p(X_n=k) + n \sum_{k=1}^{n+1} t^k \p(X_n=k) \\ & =& \displaystyle(t+n) \times G_{X_n}(t) \end{array}$$ Comme $G_{X_1}(t)=t$ on en déduit par récurrence que : $$\forall t\in\R,\quad G_{X_n}(t)=\dfrac{1}{n!}\prod_{k=0}^{n-1}(t+k)$$ On reconnaît la fonction génératrice du nombre de records (vers le haut ou vers le bas): le nombre de cycles d'une permutation aléatoire a la même loi que son nombre de records.
      C'est en fait une conséquence d'un résultat non probabiliste appelé correspondance fondamentale de Foata: http://fr.wikipedia.org/wiki/Correspondance_fondamentale_de_Foata
   3. On a pour tout $t\notin\{-n+1,\dots,-1,0\}$ : $$G_{X_n}'(t) = G_{X_n}(t)\times\left(\sum_{k=0}^{n-1} \dfrac{1}{t+k}\right)$$ donc : $$G_{X_n}''(t) = - G_{X_n}(t)\times\left(\sum_{k=0}^{n-1}\frac{1}{(t+k)^2}\right) +G_{X_n}'(t)\times\left(\sum_{k=0}^{n-1}\frac{1}{t+k}\right) $$ On en déduit que $\E(X_n)=G_{X_n}'(1)=\displaystyle\sum_{k=1}^n\dfrac{1}{k}$ puis que : $$V(X_n)=G_{X_n}''(1)+G_{X_n}'(1)-G_{X_n}'(1)^2=\sum_{k=1}^n\dfrac{1}{k} -\sum_{k=1}^n\dfrac{1}{k^2}\underset{n\to+\infty}{\sim}\ln(n)$$

MASQUER