ESSEC 2011 Maths 2Maths appliquées

Dans ce problème, on étudie un procédé élémentaire pour mélanger un jeu de cartes et on s’intéresse au nombre de répétitions nécessaires pour considérer que le jeu est bien mélangé.

On considère un jeu de \(N\) cartes numérotées \(C_{1},\dots, C_{N}\) et regroupées dans un paquet sur une table. Un joueur bat les cartes et repose le paquet sur la table. Une carte située au sommet de la pile est dite en position \(1\), celle qui se trouve immédiatement en dessous est dite en position \(2\), etc. En particulier, la carte située en position \(N\) désigne la carte située en bas de la pile. On prendra garde à bien distinguer la position d’une carte dans le paquet du numéro qu’elle porte.

On suppose qu’initialement les cartes sont rangées dans l’ordre croissant de leur numéro, c’est-à-dire que, pour tout \(i\in\left[\kern-0.15em\left[ {1,N} \right]\kern-0.15em\right]\), la carte \(C_i\) est en position \(i\). Ainsi, à l’instant initial, la carte \(C_{1}\) se trouve sur le dessus du paquet, tandis que la carte \(C_{N}\) se trouve en dessous du paquet.

Pour \(k \in\left[\kern-0.15em\left[ {1,N} \right]\kern-0.15em\right]\), on appelle insertion à la \(k\)-ième place l’opération qui consiste à prendre la carte située au-dessus du paquet et à l’insérer entre la \(k\)-ième et la \((k+1)\)-ième place. Une insertion à la première place ne change pas l’ordre des cartes. Une insertion à la \(N\)-ième place consiste à faire glisser la carte située au-dessus du paquet pour la mettre sous le paquet.

Le battage par insertions du jeu de cartes consiste à effectuer une suite d’insertions aléatoires, en choisissant, à chaque instant, uniformément au hasard dans \(\left[\kern-0.15em\left[ {1,N} \right]\kern-0.15em\right]\) la place à laquelle l’insertion a lieu, indépendamment des insertions précédentes.

Le résultat du mélange est une permutation des \(N\) cartes. On note \(S_N\) l’ensemble des permutations des \(N\) cartes et on rappelle que \(\mathrm{Card}(S_N) = N!\).

On effectue une suite d’insertions aléatoires et on admet que l’on peut modéliser cette expérience par un espace probabilisé \((\Omega,\mathcal{A},\mathbb{P})\) que l’on ne cherchera pas à préciser.

Pour toute variable aléatoire \(X\) on notera \(\mathbb{E}(X)\) et \(\mathbb{V}(X)\) l’espérance et la variance de \(X\) lorsqu’elles existent.

On note alors :

• pour tout \(n\in\mathbb{N}^\ast\), \(P_n\) la variable aléatoire égale au numéro \(k\) de la place choisie lors de la \(n^{\grave{e}me}\) insertion,

• \(T_{1}\) la variable aléatoire égale au nombre d’insertions effectuées lorsque, pour la première fois, la carte située sur le dessus du paquet est glissée en dernière position, c’est-à-dire le premier instant où la carte \(C_{N}\) se trouve remontée de la position \(N\) à la position \(N-1\),

• \(T_{2}\) la variable aléatoire égale au nombre d’insertions effectuées lorsque, pour la première fois, la carte \(C_{N}\) se trouve remontée en position \(N-2\),

• plus généralement, pour \(i\) dans \(\left[\kern-0.15em\left[ {1,N-1} \right]\kern-0.15em\right]\), on note \(T_{i}\) la variable aléatoire égale au nombre d’insertions effectuées lorsque, pour la première fois, la carte \(C_{N}\) atteint la position \(N-i\).

On considère enfin les variables aléatoires \(\Delta_1,\dots,\Delta_{N-1}\) et \(T\) les variables aléatoires définies par : \[\Delta_{1}=T_{1},\quad \forall i\in \left[\kern-0.15em\left[ {2,N-1} \right]\kern-0.15em\right],\ \Delta_{i}=T_{i} -T_{i-1} \quad \text{et} \quad T=T_{N-1}+1\]

On admet que les conditions de l’expérience permettent d’affirmer que les variables aléatoires \(\Delta_1,\dots,\Delta_{N-1}\) sont indépendantes.

Par exemple, si \(N=4\) et si les sept premières insertions se font successivement aux places \(3,2,4,1,3,4,2\), alors les différentes configuration du paquet de cartes sont les suivantes :

Pour une telle éventualité \(\omega\), on a : \[T_{1}( \omega) =3,\quad T_{2}( \omega) =5,\quad T_{3}( \omega) =6,\quad X( \omega) =7\]

Partie I - Description et premiers résultats

1. 1. Justifier que : \[\forall i\in \left[\kern-0.15em\left[ {2,N-1} \right]\kern-0.15em\right],\ T_{i}=\Delta_{1}+\Delta_{2}+\cdots+\Delta_{i}\]

   2. Pour tout \(i\in\left[\kern-0.15em\left[ {1,N-1} \right]\kern-0.15em\right]\), que représente la variable aléatoire \(\Delta_{i}\) ?

2. Déterminer la loi de \(\Delta_1\).

3. Soit \(i\in \left[\kern-0.15em\left[ {2,N-1} \right]\kern-0.15em\right]\).

   1. Établir que : \[\forall n \in \mathbb{N},\ \mathbb{P}(\Delta_i >n) = \left( \frac{N-i}{N} \right)^n\]

   2. Prouver alors que \(\Delta_i\) suit une loi usuelle que l’on précisera, qu’elle admet une espérance et une variance et que : \[\mathbb{E}(\Delta_i) = \frac{N}{i} \quad \text{et} \quad \mathbb{V}(\Delta_i) = N\, \frac{N-i}{i^2}\]

4. 1. Démontrer que : \[\forall n\geqslant 2,\ \mathbb{P}(T_{2}=n)=\sum\limits_{k=1}^{n-1}% \mathbb{P}\left( \Delta_{2}=n-k\right) \mathbb{P}\left( \Delta _{1}=k\right)\]

   2. Vérifier que : \[\forall n\geqslant 2,\ \sum\limits_{k=1}^{n-1}\left( \dfrac{1- \frac{1}{N} }% {1- \frac{2}{N}}\right) ^{k}=N\left( 1-\dfrac{1}{N}\right) \left[ \left( \dfrac{1- \frac{1}{N}}{1- \frac{2}{N}}\right) ^{n-1}-1\right]\]

   3. En déduire que : \[\forall n\geqslant 2,\ \mathbb{P}(T_{2}=n)=\frac{2}{N}\left[ \left( 1-\frac{1}{N}\right) ^{n-1}-\left( 1-\frac{2}{N}\right) ^{n-1}\right]\]

   4. Vérifier alors que : \[\sum_{n=2}^{+\infty}\mathbb{P}(T_2 = n) = 1\]

5. À l’instant \(T_{2}\), la carte \(C_{N}\) est située en position \(N-2\) et deux cartes se trouvent sous elle qui ont été insérées aux instants \(T_{1}\) et \(T_{2}\). Que valent alors les probabilités, qu’à l’instant \(T_{2}\):

   1. la carte insérée à l’instant \(T_{1}\) soit en place \(N-1\) et celle insérée à l’instant \(T_{2}\) en place \(N~\)?

   2. la carte insérée à l’instant \(T_{2}\) soit en place \(N-1\) et celle insérée à l’instant \(T_{1}\) en place \(N~\)?

6. À l’instant \(T_{3}\), la carte \(C_{N}\) est située en position \(N-3\) et trois cartes, insérées aux instants \(T_{1}\), \(T_{2}\) et \(T_{3}\), se trouvent sous elle. On note alors, pour \(i\in\{1,2,3\}\), \(a_{i}\) la position à l’instant \(T_3\) de la carte ayant été insérée à l’instant \(T_{i}\).

   1. Combien y a-t-il de résultats possibles pour le triplet \(\left( a_{1},a_{2},a_{3}\right)\)?

   2. Quelques exemples. Donner les probabilités qu’à l’instant \(T_3\) :

      • on obtienne \(\left( a_{1},a_{2},a_{3}\right) =\left( N-2,N-1,N\right)\),

      • on obtienne \(\left( a_{1},a_{2},a_{3}\right) =\left( N-2,N,N-1\right)\).

7. Justifier qu’il est raisonnable d’affirmer qu’à l’instant \(T\) toutes les configurations possibles du jeu de carte sont équiprobables ?

   On retiendra que si on arrête le battage des cartes par insertion exactement à l’instant \(T\), on a un paquet convenablement mélangé. Cependant le temps \(T\) étant aléatoire, il n’est pas possible d’arrêter de battre les cartes à cet instant précis, à moins de marquer la carte \(C_{N}\) bien sûr!

Partie II - Estimation du nombre d’insertions pour bien mélanger les cartes

On considère les suites \(\left( H_{n}\right) _{n\in\mathbb{N}^\ast}\) et \(\left( u_{n}\right) _{n\in\mathbb{N}^{\ast}}\) définies par: \[\forall n \in\mathbb{N}^\ast,\ H_{n}=\sum_{k=1}^{n}\frac{1}{k} \quad \text{et} \quad u_{n}=H_{n}% -\ln(n)\]

8. Justifier que : \[\mathbb{E}(T)=N H_{N} \quad \text{et} \quad \mathbb{V}(T)=N^{2}\left( \sum\limits_{k=1}^{N}\dfrac{1}{k^{2}% }\right) -N\, H_{N}\]

9. 1. Montrer que : \[\forall k\in\mathbb{N}^\ast,\ \frac{1}{k+1} \leqslant \int_k^{k+1} \frac{\mathrm{d}t}{t} \leqslant \frac{1}{k}\]

   2. En déduire que la suite \((u_n)_{n\in\mathbb{N}^\ast}\) est décroissante et que : \[\forall n\in\mathbb{N}^{\ast},\ \ln(n+1) \leqslant H_{n}\leqslant \ln(n) +1\]

   3. Déduire de ce qui précède que la suite \(\left( u_{n}\right)\) est convergente et que sa limite, notée \(\gamma\), appartient à \(\left[ 0,1\right]\).

10. 1. Établir que \[\mathbb{E}(T) \;\underset{N\to {+\infty}}{\sim}\;N\ln(N)\]

       et que : \[\mathbb{E}(T)=N\ln(N)+N\gamma + \circ(N)\]

    2. 1. Quelle est la nature de la suite \(\left( \dfrac{\mathbb{V}( T ) }{N^{2}}\right) _{N\in\mathbb{N}^{\ast}}\) ?

       2. Justifier qu’il existe une constante \(\alpha\), strictement positive, telle que : \[\mathbb{V}(T) \underset{N\to {+\infty}}\sim \alpha N^{2} \quad \text{et} \quad \mathbb{V}( T) \leqslant \alpha N^{2}%\]

11. On rappelle l’inégalité de Bienaymé-Tchebychev, valable pour une variable aléatoire \(X\) admettant une espérance et une variance: \[\forall\varepsilon>0,\ \mathbb{P}\left( \left\vert X- \mathbb{E}(X) \right\vert \geqslant \varepsilon\right) \leqslant \frac{\mathbb{V}(X) }% {\varepsilon^{2}}%\] Soit \(N\) fixé et une constante \(c\) strictement plus grande que \(1\).

    1. Justifier que : \[\forall\omega\in\Omega,\ \left\vert T(\omega) -N\ln(N) \right\vert \leqslant \left\vert T(\omega) - \mathbb{E}(T) \right\vert +N\]

    2. Comparer les événements \(\left[ \left\vert T -N\ln(N) \right\vert \geqslant cN\right]\) et \(\left[ \left\vert T- \mathbb{E}(T) \right\vert \geqslant N\left( c-1\right) \right]\).

    3. Démontrer que : \[\mathbb{P}\! \left( \left\vert T -N\ln(N) \right\vert \geqslant cN\right) \leqslant\frac{\alpha}{\left( c-1\right) ^{2}}%\] où \(\alpha\) a été définie à la question 10.

    4. Le nombre \(N\) étant fixé, que vaut \(\lim\limits_{c\rightarrow+\infty }\mathbb{P}\! \left( \left\vert T-N\ln(N) \right\vert \geqslant cN\right) ~\)?

12. Démontrer aussi que pour tout \(\varepsilon>0\) : \[\lim\limits_{N\rightarrow+\infty}\mathbb{P}\! \left( \left\vert T-N\ln\left( N\right) \right\vert \geqslant \varepsilon N\ln(N) \right) =0\] On peut traduire ces résultats en disant que l’événement: « \(T\) s’écarte de \(N\ln(N)\) de manière significative » est un événement asymptotiquement rare.

    Pour information, pour un paquet de 32 cartes, on donne \(32\ln(32)\simeq110\) et pour un paquet de 52 cartes, \(52\ln (52)\simeq205\).

13. Dans cette question on considère un jeu de \(N=32\) cartes et on cherche à modéliser le mélange des cartes à l’aide d’un programme Python. Pour cela, on peut modéliser le jeu de carte à l’aide d’une variable Jeu contenant un tableau de \(32\) cases Jeu[0], …, Jeu[31] telle que, pour tout \(i\in\left[\kern-0.15em\left[ {1,32} \right]\kern-0.15em\right]\), la valeur stockée dans Jeu[i-1] soit égale au numéro de la carte située en position numéro \(i\) dans le jeu.

    On se propose pour cela de compléter le programme suivant :

    import numpy as np
    import numpy.random as rd
    def Insertion(Jeu):
        k=...................
        c=Jeu[0]
        for i in range(0,k-1):
            Jeu[i]=..........
        Jeu[k-1]=............
        return Jeu
    def X(N):
        Jeu=.................
        n=0
        while ...............:
            Insertion(Jeu)
            n=...............
        return n
    N=32
    NbSimuls=10**3
    Simul=np.zeros(NbSimuls)
    for k in range(0,NbSimuls-1):
        Simul[k]=............
    print(...................)
    

    • Compléter les lignes (4), (7) et (8) de la fonction Insertion de telle sorte que l’appel de Insertion(Jeu) simule une insertion à un instant donné.

    • Compléter la ligne (11) afin que la variable Jeu contienne la configuration initiale du paquet de cartes, c’est-à-dire les entiers de \(1\) à \(32\) rangés dans l’ordre croissant.

    • Compléter les lignes (13) et (15) de la fonction X afin que l’appel de X(N) effectue une simulation de l’expérience et renvoie la valeur prise par la variable aléatoire \(T\).

    • Compléter les lignes (21) et (22) du programme afin que celui-ci réalise \(10^3\) simulations de l’expérience et renvoie la valeur moyenne des valeurs prises par \(T\) lors de ces expériences.

Partie III - Distance variationnelle à la loi uniforme

Pour tout entier naturel \(n\) non nul, on cherche à savoir si la probabilité que le jeu de cartes se retrouve dans une situation donnée à l’instant \(n\) est proche de la probabilité uniforme, ce qui indiquerait que le jeu est bien battu.

Pour cela, on note \(\mathcal{B}=\mathcal{P}(S_N)\) (ensemble des parties de \(S_N\)) et on note :

• \(\pi\) la probabilité uniforme sur \((S_N,\mathcal{B})\), c’est-à-dire la probabilité vérifiant : \[\forall B \in \mathcal{B},\ \pi(B) = \frac{\mathrm{Card}(B)}{N!}\] et en particulier : \[\forall \sigma \in S_n,\ \pi( \{ \sigma \} ) = \frac{1}{N!}\]

• \(\mu_n\) (pour \(n\in\mathbb{N}^\ast\)), la probabilité sur \((S_N,\mathcal{B})\) telle que, pour toute configuration \(\sigma\) de \(S_N\), \(\mu_{n} ( \{ \sigma \} )\) soit égale à la probabilité qu’à l’instant \(n\) le tas de cartes se trouve dans la configuration \(\sigma\) ; on a alors pour pour toute partie \(A\) de \(S_N\) : \[\mu_{n}(A) =\sum\limits_{\sigma\in A}\mu_{n} ( \{ \sigma \} )\]

On peut mesurer la qualité du mélange à un instant donné \(n\) en estimant l’écart entre \(\mu_{n}\) et \(\pi\). On définit pour cela une distance \(d\) entre ces probabilités de la façon suivante : \[d ( \mu_{n},\mathbb{P}) =\max\left\{ \left\vert \mu_{n}(A) -\pi(B) \right\vert ,\ A\subset\mathcal{S}_{N}\right\}\]

14. Soit \(A\) une partie de \(S_N\), \(n\in\mathbb{N}^{\ast}\) et \(E_{n}\) l’événement de \(\mathcal{B}\) : « à l’instant \(n\) le paquet de cartes se trouve dans une configuration qui appartient \(A\) ». On a donc : \[\mu_n(A) = \mathbb{P}(E_n)\]

    1. Expliquer, en utilisant la question 7, l’égalité suivante : \[\pi (A) = \mathbb{P}_{[ T \leqslant n ] } ( E_{n} )\]

       En déduire que : \[\mathbb{P}( E_{n}\cap [T \leqslant n] ) =\pi(A) \, \mathbb{P}( T \leqslant n )\]

    2. Établir que : \[\mathbb{P}( E_{n}\cap [ T >n] ) \leqslant \mathbb{P}(T >n )\]

    3. Montrer que : \[\mu_{n}(A) \leqslant \pi(A) +\mathbb{P}( T >n )\]

15. Soit \(A\) une partie de \(S_N\) et \(n\in\mathbb{N}^{\ast}\). On note \(\overline{A}\) l’événement contraire de \(A\).

    1. Exprimer \(\mu_{n} ( \overline{A} ) -\pi( \overline {A})\) en fonction de \(\mu_{n}(A) -\pi(A)\).

    2. Déduire des questions précédentes la majoration: \[\left\vert \mu_{n}(A) -\pi(A) \right\vert \leqslant \mathbb{P}( T >n )\]

16. Montrer que : \[\forall n\in\mathbb{N}^{\ast},\ 0\leqslant d ( \mu_{n},\pi ) \leqslant \mathbb{P}\left( T >n\right)\]

    puis déterminer la limite de \(d ( \mu_{n},\pi )\) lorsque \(n\) tend vers \({+\infty}\).

Partie IV - Une majoration de \(\mathbb{P}(T >n )\)

Dans cette partie, nous nous intéressons provisoirement à un collectionneur de timbres. Celui-ci reçoit chaque jour une lettre affranchie avec un timbre choisi au hasard uniformément parmi les \(N\) timbres en vigueur. On étudie ici le nombre de jours que doit attendre le collectionneur pour posséder la collection complète des \(N\) timbres. Le jour 0 il n’a aucun timbre. On note alors:

• pour tout entier \(k \in \left[\!\left[1, N\right]\!\right]\), \(S_k\) le nombre aléatoire de jours que doit attendre le collectionneur pour que le nombre de timbres différents qu’il possède passe de \(k-1\) à \(k\),

• \(S=S_1+S_2+\cdots+S_N\), soit la variable aléatoire correspondant au nombre de jours à attendre pour posséder la collection complète des \(N\) timbres,

• en supposant les \(N\) timbres en vigueur numérotés de 1 à \(N\), pour tout \(j \in \left[\!\left[1, N\right]\!\right]\), \(B_j^m\) l’événement « le jour \(m\), le collectionneur n’a toujours pas reçu de lettre affranchie avec le timbre numéro \(j\) ».

On admet que les variables aléatoires \(S_1,\dots,S_N\) sont indépendantes.

17. Déterminer la loi de \(S_{1}\).

18. Pour tout entier \(k\left[\kern-0.15em\left[ {2,N} \right]\kern-0.15em\right]\), déterminer la loi de la variable \(S_{k}\).

19. En déduire que la variable \(S\) suit la même loi de probabilité que la variable \(T\) étudiée dans les parties précédentes.

    Ce résultat sera utilisé pour estimer la probabilité \(\mathbb{P}(T>n)\).

20. Soit \(m \in\mathbb{N}^{\ast}\).

    1. Exprimer l’événement \([ S> m]\) à l’aide des événements \(B_{1}^{m},B_{2}^{m},...,B_{N}^{m}\).

    2. Que vaut \(\mathbb{P}(B_j^m )\) pour tout entier \(j \in \left[\!\left[1, N\right]\!\right]\) ?

    3. On rappelle que pour tout entier \(n \geqslant 2\) et pour toute famille d’événements \(A_1, \dots, A_n\) , on a l’inégalité: \(\displaystyle \mathbb{P}\!\left(\bigcup_{i=1}^n A_i\right) \leqslant \sum_{i=1}^n \mathbb{P}(A_i)\) En déduire : \[\mathbb{P}( S> m) \leqslant N \!\left( 1-\frac{1}{N}\right) ^{m}\]

21. 1. Montrer que : \[\forall x\in \left] -1,{+\infty}\right[,\ \ln(1+x)\leqslant x\]

    2. En déduire que : \[\forall m \in\mathbb{N}^\ast,\ \mathbb{P}( T > m ) \leqslant N \mathrm{e}^{-\frac{m}{N}}%\]

22. On reprend les notations introduites dans les questions précédentes.

    1. Soit \(c>0\) fixé. Montrer que pour \(n\) entier supérieur ou égal à \(N\ln (N)+cN\) on a : \[d(\mu_{n},\pi)\leqslant \mathrm{e}^{-c}\]

    2. Application numérique. On estime qu’une distance en variation à la loi uniforme de 0,2 est acceptable.

       Avec un jeu de 32 cartes, combien de battages par insertions doit-on faire pour considérer le paquet mélangé de façon acceptable?