\documentclass[12pt,a4paper]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage[francais]{babel}
\usepackage{amsmath}

\setcounter{MaxMatrixCols}{10}
%TCIDATA{OutputFilter=Latex.dll}
%TCIDATA{Version=5.50.0.2890}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{LastRevised=Thursday, February 02, 2012 19:52:30}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}

\setlength \parindent{0pt}
\setlength \voffset{-2cm}
\setlength \headheight{0cm}
\setlength \headsep{0.1cm}
\setlength \textheight{25.5cm}
\setlength \hoffset{-2.5cm}
\setlength \textwidth{18cm}
\renewcommand{\theenumii}{\alph{enumii}}
\renewcommand{\labelenumii}{\theenumii)}
\lfoot{Corrig\'e ESSEC  eco 2011 }
\cfoot{}
\rfoot{ Page \thepage / 11}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0.4pt}
\pagestyle{fancy}

\input{tcilatex}

\begin{document}


{\textbf{C}orrig\'e ESSEC Maths II 2011} par Pierre Veuillez

Une question que se pose un joueur de cartes est de savoir combien de fois
il est n\'{e}cessaire de battre les cartes pour que le paquet soit
convenablement m\'{e}lang\'{e}. Ce probl\`{e}me d\'{e}crit un proc\'{e}d\'{e}
tr\`{e}s \'{e}l\'{e}mentaire pour m\'{e}langer les cartes et propose de r%
\'{e}pondre alors \`{a} cette question.

Consid\'{e}rons un jeu de $N$ cartes num\'{e}rot\'{e}es de $C_{1}$ \`{a} $%
C_{N}$ et dispos\'{e}es en un paquet sur une table. Un joueur bat les cartes
et repose le paquet sur la table. Le r\'{e}sultat du m\'{e}lange est une
permutation de ces $N$ cartes.

\textbf{Notations et Rappel :}

On note $S_{N}$ l'ensemble des permutations possibles pour ce paquet de $N$
cartes et on rappelle que $\func{card}\left( S_{N}\right) =N!$

On se place dans un espace probabilis\'{e} $\left( \Omega,\mathcal{A},\func{P%
}\right) $ avec $\Omega=S_{N},$ $\mathcal{A=P}\left( \Omega \right) $
l'ensemble des parties de $S_{N}$ et $\func{P}$ l'\'{e}quiprobabilit\'{e}
sur $\Omega$.

Pour toute variable al\'{e}atoire $X$ on notera $E\left( X\right) $ et $%
V\left( X\right) $ l'esp\'{e}rance et la variance de $X$ lorsqu'elles
existent.

On consid\`{e}re qu'un paquet est convenablement m\'{e}lang\'{e} lorsque
toutes les permutations sont \'{e}quiprobables, c'est-\`{a}-dire lorsque
pour toute permutation $\sigma$ de $S_{N}$ la probabilit\'{e} que le tas de
cartes se trouve dans la configuration $\sigma$ vaut $1/N!$

\textbf{Vocabulaire et notations:}

Une carte situ\'{e}e au sommet de la pile est dite en position n%
%TCIMACRO{\U{b0} }%
%BeginExpansion
${{}^\circ}$
%EndExpansion
1, celle qui se trouve imm\'{e}diatement en dessous est dite en position n%
%TCIMACRO{\U{b0}}%
%BeginExpansion
${{}^\circ}$%
%EndExpansion
2, etc. Ainsi une carte situ\'{e}e en position n%
%TCIMACRO{\U{b0}}%
%BeginExpansion
${{}^\circ}$%
%EndExpansion
$N$ d\'{e}signe la carte situ\'{e}e en bas de la pile.

On prendra garde \`{a} bien distinguer la position d'une carte dans le
paquet du num\'{e}ro qu'elle porte.

Partons d'un tas de cartes rang\'{e}es initialement dans l'ordre suivant :

pour tout $i$ \'{e}l\'{e}ment de $\left[ \left[ 1,N\right] \right] $, la
carte $C_{i}$ se trouve en position $i$.

Ainsi, \`{a} l'instant initial, la carte $C_{1}$ se trouve sur le dessus du
paquet alors que $C_{N}$ se trouve donc tout en dessous du paquet.

Pour $k$ \'{e}l\'{e}ment de $\left[ \left[ 1,N\right] \right] $, on appelle
insertion \`{a} la $k^{i\grave{e}me}$ place l'op\'{e}ration qui consiste 
\`{a} prendre la carte situ\'{e}e au-dessus du paquet et \`{a} l'ins\'{e}rer
entre la $k^{i\grave{e}me}$ et la $\left( k+1\right) ^{i\grave{e}me}$ place.
Une insertion \`{a} la premi\`{e}re place ne change pas l'ordre des cartes.
Une insertion \`{a} la $N^{i\grave{e}me}$ place consiste \`{a} faire glisser
la carte situ\'{e}e au-dessus du paquet pour la mettre sous le paquet.

Le battage par insertions du jeu de cartes consiste \`{a} effectuer une
suite d'insertions al\'{e}atoires, en choisissant, \`{a} chaque instant, au
hasard uniform\'{e}ment dans $\left \{ 1,\cdots N\right \} $ la place \`{a}
laquelle l'insertion a lieu, ind\'{e}pendamment des insertions pr\'{e}c\'{e}%
dentes.

Les instants successifs d'insertions seront not\'{e}es $1,2,\dots,n,\dots,$
l'instant initial est $n=0$.

\textbf{Notations}. Nous notons :

\begin{itemize}
\item $T_{1}$ le premier instant o\`{u} la carte situ\'{e}e sur le dessus du
paquet est gliss\'{e}e en derni\`{e}re position, c'est-\`{a}-dire le premier
instant o\`{u} la carte $C_{N}$ se trouve remont\'{e}e de la position $N$ 
\`{a} la position $N-1$,

\item $T_{2}$ le premier instant o\`{u} la carte $C_{N}$ se trouve remont%
\'{e}e en position $N-2$,

\item et plus g\'{e}n\'{e}ralement, pour $i$ dans $\left[ \left[ 1,N-1\right]
\right] ,$ $T_{i}$ le premier instant o\`{u} la carte $C_{N}$ atteint la
position $N-i$.

\item On posera \'{e}galement $\Delta_{1}=T_{1}$ et $\forall i\in \left[ %
\left[ 2,N-1\right] \right] ,\ \Delta_{i}=T_{i}-T_{i-1}$

\item Enfin, on notera $T=T_{N-1}+1$.
\end{itemize}

On admet que les conditions de l'exp\'{e}rience permettent de faire l'hypoth%
\`{e}se que les variables al\'{e}atoires $\left( \Delta_{i}\right) _{i\in %
\left[ \left[ 1,N-1\right] \right] }$ sont ind\'{e}pendantes.

\textbf{Description d'un exemple.} Dans le tableau ci-dessous, nous d\'{e}%
crivons les r\'{e}sultats d'une exp\'{e}rience faite sur un paquet de $N=4$
cartes. La premi\`{e}re ligne du tableau indique les instants $n$, la deuxi%
\`{e}me ligne indique les positions d'insertions, et dans la derni\`{e}re
ligne figure la configuration du paquet \`{a} l'instant $n$.

\begin{tabular}{|c|r|cccccccc|}
\hline
& instant $n$ & $0$ & \multicolumn{1}{|c}{$1$} & \multicolumn{1}{|c}{$2$} & 
\multicolumn{1}{|c}{$3$} & \multicolumn{1}{|c}{$4$} & \multicolumn{1}{|c}{$5$%
} & \multicolumn{1}{|c}{$6$} & \multicolumn{1}{|c|}{$7$} \\ \hline
& insertion en place $k$ &  & \multicolumn{1}{|c}{$3$} & \multicolumn{1}{|c}{%
$2$} & \multicolumn{1}{|c}{$4$} & \multicolumn{1}{|c}{$1$} & 
\multicolumn{1}{|c}{$3$} & \multicolumn{1}{|c}{$4$} & \multicolumn{1}{|c|}{$%
2 $} \\ \hline
Configuration & position 1 & $C_{1}$ & $C_{2}$ & $C_{3}$ & $C_{2}$ & $C_{2}$
& $C_{1}$ & $C_{4}$ & $C_{2}$ \\ 
du & position 2 & $C_{2}$ & $C_{3}$ & $C_{2}$ & $C_{1}$ & $C_{1}$ & $C_{4}$
& $C_{2}$ & $C_{4}$ \\ 
paquet & position 3 & $C_{3}$ & $C_{1}$ & $C_{1}$ & $C_{4}$ & $C_{4}$ & $%
C_{2}$ & $C_{3}$ & $C_{3}$ \\ 
& position 4 & $C_{4}$ & $C_{4}$ & $C_{4}$ & $C_{3}$ & $C_{3}$ & $C_{3}$ & $%
C_{1}$ & $C_{1}$ \\ \hline
\end{tabular}
\newline

Pour cette, exp\'{e}rience, on a les r\'{e}sultats $T_{1}\left( \omega
\right) =3,\ T_{2}\left( \omega \right) =5,\ T_{3}\left( \omega \right) =6$
et $T_{7}\left( \omega \right) =7$

\subsection*{Partie 1 - Description et premiers r\'{e}sultats}

\begin{enumerate}
\item Pour tout $i,$ $\Delta_{i}$ est le nombre de coups s\'{e}parant la $%
i-1^{\grave{e}me}$ de la $i^{\grave{e}me}$ remont\'{e}e.

Donc $T_{i}$ nombre total de coup pour la $i^{\grave{e}me}$ remont\'{e}e est 
$T_{i}=T_{1}+\cdots+\Delta_{i}=\Delta_{1}+\cdots+\Delta_{i}$

(on pouvait aussi le faire par r\'{e}currence, plus coh\'{e}rent avec
l'ordre des deux questions)

\item Loi de $\Delta_{1}$.

$\left( \Delta_{1}>n\right) $ signifie qu'aucune insertion ne s'est faite en 
$N^{\grave{e}me}$ position durant les $n$ premi\`{e}res insertions.

En notant $I_{m}$ la position de la $m^{i\grave{e}me}$ insertion on a donc $%
\left( \Delta_{1}>n\right) =\bigcap_{m=1}^{n}\left( I_{m}<N\right) $

et par ind\'{e}pendance des insertions $\func{P}\left( \Delta _{1}>n\right)
=\prod_{m=1}^{n}\func{P}\left( I_{m}<N\right) $ avec $\func{P}\left(
I_{m}<N\right) =\frac{N-1}{N}$ car les positions d'insertion sont \'{e}%
quiprobables.

\textsl{Conclusion : }\fbox{$\func{P}\left( \Delta_{1}>n\right) =\left( 
\frac{N-1}{N}\right) ^{n}$}

et comme (valeurs enti\`{e}res) on a alors $\left( \Delta_{1}>n-1\right)
=\left( \Delta_{1}>n\right) \cup \left( \Delta_{1}=n\right) $ donc 
\begin{align*}
\func{P}\left( \Delta_{1}=n\right) & =\func{P}\left( \Delta_{1}>n-1\right) -%
\func{P}\left( \Delta_{1}>n\right) \\
& =\left( \frac{N-1}{N}\right) ^{n-1}-\left( \frac{N-1}{N}\right) ^{n} \\
& =\left( \frac{N-1}{N}\right) ^{n-1}\left( 1-\frac{N-1}{N}\right)
\end{align*}
et on reconna\^{\i}t, avec $\Delta_{1}\left( \Omega \right) =\mathbb{N}%
^{\ast},$\textsl{\ }\fbox{$\Delta_{1}\hookrightarrow \mathcal{G}\left( 
\dfrac{1}{N}\right) $}

\textbf{N.B. }on pouvait le voire directement avec $\Delta_{1}$ rang de la
premi\`{e}re insertion en position $N$ dans une suite d'insertions ind\'{e}%
pendantes, la probabilit\'{e} \`{a} chacune \'{e}tant de $1/N$

\item Soit $i\in \left[ \left[ 2,N-1\right] \right] .$ Loi de $\Delta_{i}$

\begin{enumerate}
\item Pour tout $n\in \mathbb{N}$

$\left( \Delta_{i}>n\right) $ signifie que, il y a plus de $n$ insertion
pour la $i^{\grave{e}me}$ remont\'{e}e de la carte $C_{N}$

Cette remont\'{e}e se fait de la position $N-i-1$ (apr\`{e}s $i-1$ remont%
\'{e}es) \`{a} la $N-i.$

Il y a donc $N-i$ positions d'insertions permises.

$\left( \Delta_{i}>n\right) =\bigcap_{m=1}^{n}\left( I_{m}\leq N-i\right) $
d'et par ind\'{e}pendance des insertions \newline
$\func{P}\left( \Delta_{i}>n\right) =\prod_{m=1}^{n}\func{P}\left( I_{m}\leq
N-i\right) $ avec $\func{P}\left( I_{m}\leq N-i\right) =\dfrac {N-i}{N}$

\textsl{Conclusion : }\fbox{$\func{P}\left( \Delta_{i}>n\right) =\left( 
\frac{N-i}{N}\right) ^{n}$}

et comme pr\'{e}c\'{e}demment, \textsl{Conclusion : }\fbox{$\Delta
_{i}\hookrightarrow \mathcal{G}\left( \dfrac{i}{N}\right) $}

\item On a alors $E\left( \Delta_{i}\right) =\dfrac{1}{i/N}=\dfrac{N}{i}$ et 
$V\left( \Delta_{i}\right) =\dfrac{1-\frac{i}{N}}{\left( \frac{i}{N}\right)
^{2}}=\dfrac{N\left( N-i\right) }{i^{2}}$
\end{enumerate}

\item Loi de $T_{2}$. Soit $n\geq2.$-

\begin{enumerate}
\item $T_{2}=\Delta_{1}+\Delta_{2}$ donc%
\begin{equation*}
\left( T_{2}=n\right) =\bigcup_{k=1}^{n-1}\left( \Delta_{1}=k\cap \Delta
_{2}=n-k\right) 
\end{equation*}
les bornes \'{e}tant impos\'{e}es par $\Delta_{1}\geq1$ et $\Delta_{2}\geq1$

Donc ($\cup$ incompatibles et $\left( \Delta_{i}\right) $ ind\'{e}pendants)%
\begin{equation*}
\func{P}\left( T_{2}=n\right) =\sum_{k=1}^{n-1}\func{P}\left(
\Delta_{2}=n-k\right) \func{P}\left( \Delta_{1}=k\right) 
\end{equation*}

\item On a 
\begin{align*}
\sum_{k=1}^{n-1}\left( \frac{1-1/N}{1-2/N}\right) ^{k} & =\left( \frac{1-1/N%
}{1-2/N}\right) \frac{1-\left( \frac{1-1/N}{1-2/N}\right) ^{n-1}}{1-\left( 
\frac{1-1/N}{1-2/N}\right) }\text{ car }\frac{1-1/N}{1-2/N}\neq1 \\
& =\left( 1-1/N\right) \frac{1-\left( \frac{1-1/N}{1-2/N}\right) ^{n-1}}{%
1-2/N-1+1/N} \\
& =N\left( 1-\frac{1}{N}\right) \left[ 1-\left( \frac{1-1/N}{1-2/N}\right)
^{n-1}\right]
\end{align*}

\item On reprend%
\begin{align*}
\func{P}\left( T_{2}=n\right) & =\sum_{k=1}^{n-1}\func{P}\left(
\Delta_{2}=n-k\right) \func{P}\left( \Delta_{1}=k\right) \text{ et }k\text{
et }n-k\geq1\text{ donc } \\
& =\sum_{k=1}^{n-1}\left( 1-\frac{2}{N}\right) ^{n-k-1}\frac{2}{N}\left( 1-%
\frac{1}{N}\right) ^{k-1}\frac{1}{N} \\
& =\frac{2}{N^{2}}\left( 1-\frac{2}{N}\right) ^{n-1}\left( 1-\frac{1}{N}%
\right) ^{-1}\sum_{k=1}^{n-1}\left( \frac{1-1/N}{1-2/N}\right) ^{k} \\
& =\frac{2}{N^{2}}\left( 1-\frac{2}{N}\right) ^{n-1}\left( 1-\frac{1}{N}%
\right) ^{-1}N\left( 1-\frac{1}{N}\right) \left[ 1-\left( \frac {1-1/N}{1-2/N%
}\right) ^{n-1}\right] \\
& =\frac{2}{N}\left( 1-\frac{2}{N}\right) ^{n-1}\left[ 1-\left( \frac{1-1/N}{%
1-2/N}\right) ^{n-1}\right] \\
& =\frac{2}{N}\left[ \left( 1-\frac{2}{N}\right) ^{n-1}-\left( 1-\frac {1}{N}%
\right) ^{n-1}\right]
\end{align*}
\end{enumerate}

\item \`{A} l'instant $T_{2}$, la carte $C_{N}$ est situ\'{e}e en position $%
N-2$ et deux cartes se trouvent sous elle qui ont \'{e}t\'{e} ins\'{e}r\'{e}%
es aux instants $T_{1}$ et $T_{2}$

La carte ins\'{e}r\'{e}e \`{a} $T_{1}$ sera au dessus de celle ins\'{e}r\'{e}%
e \`{a} $T_{2},$ si (et seulement si) celle ins\'{e}r\'{e}e \`{a} $T_{2}$
l'est en position $N.$

Elle sera en dessous si celle ins\'{e}r\'{e}e \`{a} $T_{2}$ l'est en
position $N-1$

Les deux cas sont \'{e}quiprobables. Donc \`{a} l'instant $T_{2}$

\begin{itemize}
\item \og la carte ins\'{e}r\'{e}e \`{a} l'instant $T_{1}$ est en place $N-1$
et celle ins\'{e}r\'{e}e \`{a} l'instant $T_{2}$ en place $N$\fg et

\item \og la carte ins\'{e}r\'{e}e \`{a} l'instant $T_{1}$ est en place $N$
et celle ins\'{e}r\'{e}e \`{a} l'instant $T_{2}$ en place $N-1$\fg
\end{itemize}

ont la m\^{e}me probabilit\'{e} : $\dfrac{1}{2}$

\item A l'instant $T_{3}$, la carte $C_{N}$ est situ\'{e}e en position $N-3$
et trois cartes, ins\'{e}r\'{e}es aux instants $T_{1}$, $T_{2}$ et $T_{3}$
se trouvent sous elle. On note alors, pour $i\in \left \{ 1,2,3\right \} ,\
a_{i}$ la position de la carte ayant \'{e}t\'{e} ins\'{e}r\'{e}e \`{a}
l'instant $T_{i}.$

\begin{enumerate}
\item Apr\`{e}s la troisi\`{e}me insertion en dessous de $C_{N}$,

la premi\`{e}re carte ins\'{e}r\'{e}e peut se retrouver en $\left \{
N-2,N-1,N\right \} $

la seconde ans $\left \{ N-1,N\right \} $ et ma troisi\`{e}me est en
position $N$.

Il y a donc $3\cdot2\cdot1=6$ r\'{e}sultats possibles pour $\left(
a_{1},a_{2},a_{3}\right) $

Equiprobables ? les points d'insertion faisant remonter $C_{N}$ sont \'{e}%
quiprobables. Il y en a $1\cdot2\cdot3$

\item \underline{Quelques exemples.} \`{a} l'instant $T_{3}$:

\begin{enumerate}
\item on obtient $\left( a_{1},a_{2},a_{3}\right) =\left( N-2,N-1,N\right) $
si (et seulement si) les insertions ont \'{e}t\'{e} faites les trois fois en
position $N.$

Il a donc une probabilit\'{e} de $\frac{1}{6}$

\item on obtient $\left( a_{1},a_{2},a_{3}\right) =\left( N-2,N,N-1\right) $
si et seulement si

la carte ins\'{e}r\'{e}e en $T_{1}$ a \'{e}t\'{e} deux fois repouss\'{e}e
(insertion $T_{2}$ et $T_{3}$ en dessous)

et celle ins\'{e}r\'{e}e en $T_{2}$ n'a pas \'{e}t\'{e} repouss\'{e}e par
l'insertion en $T_{3}$ donc

la premi\`{e}re carte insertion est en $N,$ la seconde en $N$ et la derni%
\`{e}re en $N-1$

Il a donc une probabilit\'{e} de $\frac{1}{6}$
\end{enumerate}
\end{enumerate}

\item \og \`{A} partir de l'instant $T$, toutes les configurations du jeu de
cartes sont \'{e}quiprobables\fg

C'est clair ! non ?

\`{A} chaque instant $T_{i}$ $(i<N)$ la carte ins\'{e}r\'{e}e en dessous de $%
C_{N}$ l'est \'{e}quiprobablement sur chacune des positions $\left[ \left[
N-i+1,N\right] \right] $ et on a alors (r\'{e}currence) pour les cartes ins%
\'{e}r\'{e}es en dessous, toutes les permutations \'{e}quiprobables.

\`{A} l'instant $T_{N-1}+1,$ on ins\`{e}re enfin la carte $C_{N}$ qui se
retrouve \'{e}quiprobablement en toutes positions.

Au final, toutes les permutations seront \'{e}quiprobables \`{a} l'instant $%
T.$
\end{enumerate}

\textsl{On retiendra que si on arr\^{e}te le battage des cartes par
insertion exactement \`{a} l'instant }$T$\textsl{, on a un paquet
convenablement m\'{e}lang\'{e}. Cependant le temps }$T$\textsl{\ \'{e}tant al%
\'{e}atoire, il n'est pas possible d'arr\^{e}ter de battre les cartes \`{a}
cet instant pr\'{e}cis, \`{a} moins de marquer la carte }$C_{N}$\textsl{\
bien s\^{u}r !}

\subsection*{Partie 2 - Estimation du nombre d'insertions pour bien m\'{e}%
langer les cartes}

\textbf{Notations.} on introduit les suites $\left( H_{n}\right) _{n\geq1}$
et $\left( u_{n}\right) $ d\'{e}finies par :%
\begin{equation*}
\forall n\geq1\quad H_{n}=\sum_{k=1}^{n}\frac{1}{k}\text{\quad et\quad}%
u_{n}=H_{n}-\ln \left( n\right) 
\end{equation*}

\begin{enumerate}
\item \setcounter{enumi}{7}

\item \underline{Esp\'{e}rance et variance de $T$}

On a $T=T_{N-1}+1=\sum_{k=1}^{N-1}\Delta_{k}+1$ donc 
\begin{align*}
E\left( T\right) & =1+\sum_{k=1}^{N-1}E\left( \Delta_{k}\right) \\
& =1+\sum_{k=1}^{N-1}\dfrac{N}{k}=\frac{N}{N}+\sum_{k=1}^{N-1}\dfrac{N}{k} \\
& =NH_{N}\text{ et } \\
V\left( T\right) & =\sum_{k=1}^{N-1}V\left( \Delta_{k}\right) \text{ par ind%
\'{e}pendance} \\
& =\sum_{k=1}^{N-1}\dfrac{N\left( N-k\right) }{k^{2}}=\sum_{k=1}^{N}\dfrac{%
N\left( N-k\right) }{k^{2}}-0 \\
& =\sum_{k=1}^{N}\dfrac{N^{2}}{k^{2}}-\dfrac{Nk}{k^{2}} \\
& =N^{2}\sum_{k=1}^{N}\dfrac{1}{k^{2}}-N\sum_{k=1}^{N}\dfrac{1}{k}
\end{align*}

\textsl{Conclusion : }\fbox{$V\left( T\right) =N^{2}\sum_{k=1}^{N}\dfrac {1}{%
k^{2}}-NH_{N}$}

\item \underline{\'{E}tude de la suite $\left( u_{n}\right) $}

\begin{enumerate}
\item Pour tout $k\geq1$ et $t\in \left[ k,k+1\right] $ on a 
\begin{align*}
\frac{1}{k+1} & \leq \frac{1}{t}\leq \frac{1}{k}\text{ donc bornes }k\leq k+1
\\
\int_{k}^{k+1}\frac{1}{k+1}dt & \leq \int_{k}^{k+1}\frac{1}{t}dt\leq \int
_{k}^{k+1}\frac{1}{k}dt\text{ et } \\
\frac{1}{k+1} & \leq \int_{k}^{k+1}\frac{1}{t}dt\leq \frac{1}{k}
\end{align*}

\item On en d\'{e}duit pour tout entier $n\geq1$

\begin{align*}
u_{n+1}-u_{n} & =\frac{1}{n+1}-\ln \left( n+1\right) +\ln \left( n\right) \\
& =\frac{1}{n+1}-\int_{n}^{n+1}\frac{1}{t}dt \\
& \leq0
\end{align*}
donc la suite $\left( u_{n}\right) _{n\geq1}$ est d\'{e}croissante

Donc, comme $u_{1}=H_{1}-\ln \left( 1\right) =1$ alors pour tout $n\geq1:$ $%
u_{n}\leq u_{1}=1$ et \fbox{$H_{n}\leq \ln \left( n\right) +1$}

Enfin en sommant les in\'{e}galit\'{e}s de droite du a) 
\begin{align*}
\sum_{k=1}^{n}\int_{k}^{k+1}\frac{1}{t}dt & \leq \sum_{k=1}^{n}\frac{1}{k}%
\text{ et Chasles } \\
\int_{1}^{n+1}\frac{1}{t}dt & \leq H_{n}
\end{align*}

\textsl{Conclusion : }$\fbox{$\forall n\in \mathbb{N}^{\ast},\quad \ln
\left( n+1\right) \leq H_{n}\leq \ln \left( n\right) +1$}$

\item On a donc $\forall n\in \mathbb{N}^{\ast},$ $\ln \left( n+1\right)
-\ln \left( n\right) \leq H_{n}-\ln \left( n\right) \leq1$

et donc $0\leq \ln \left( \frac{n+1}{n}\right) \leq u_{n}\leq1$

La suite $u$ est donc d\'{e}croissante et minor\'{e}e par $0$ donc converge
vers une limite $\gamma$ et $\gamma \in \left[ 0,1\right] $
\end{enumerate}

\item 
\begin{enumerate}
\item Comme $\ln \left( n+1\right) \leq H_{n}\leq \ln \left( n\right) +1$
avec $\ln \left( n+1\right) =\ln \left( n\left( 1+1/n\right) \right) =\ln
\left( n\right) +\ln \left( 1+1/n\right) $

donc 
\begin{equation*}
1+\frac{\ln \left( 1+1/n\right) }{\ln \left( n\right) }\leq \frac{H_{n}}{\ln
\left( n\right) }\leq1+\frac{1}{\ln \left( n\right) }
\end{equation*}
et par encadrement $H_{n}/\ln \left( n\right) \rightarrow1$ et $H_{n}\sim
\ln \left( n\right) $

\textsl{Conclusion : }\fbox{$E\left( T\right) =NH_{N}\sim N\ln \left(
N\right) $ quand $N\rightarrow+\infty$}

Et comme $H_{n}=\ln \left( n\right) +u_{n}$ et avec $u_{n}-\gamma
=\varepsilon \left( n\right) \rightarrow0$ on a donc

$E\left( T\right) =NH_{N}=N\left( \ln \left( n\right) +\gamma +\varepsilon
\left( N\right) \right) =N\ln \left( N\right) +N\gamma +N\varepsilon \left(
N\right) $

\textsl{Conclusion : }\fbox{$E\left( T\right) =N\ln \left( N\right)
+N\gamma+o\left( N\right) $}

\item On a $vu$ que $V\left( T\right) =N^{2}\sum_{k=1}^{N}\dfrac{1}{k^{2}}%
-NH_{N}=N^{2}\sum_{k=1}^{N}\dfrac{1}{k^{2}}-E\left( T\right) $

Donc 
\begin{equation*}
\frac{V\left( T\right) }{N^{2}}=\sum_{k=1}^{N}\dfrac{1}{k^{2}}-\frac{E\left(
T\right) }{N^{2}}
\end{equation*}
avec $\displaystyle \frac{E\left( T\right) }{N^{2}}=\frac{\ln \left(
N\right) }{N}+\frac{\gamma}{N}+\frac{o\left( N\right) }{N^{2}}\rightarrow0$
et la s\'{e}rie $\dsum _{k\geq1}\dfrac{1}{k^{2}}$ convergente

\textsl{Conclusion : }\fbox{la suite $\left( \frac{V\left( T\right) }{N^{2}}%
\right) _{N\in \mathbb{N}^{\ast}}$ est convergente}

En notant $\alpha=\sum_{k=1}^{+\infty}\dfrac{1}{k^{2}}$ on a donc $\dfrac{%
V\left( T\right) }{N^{2}}\rightarrow \alpha$

\textsl{Conclusion : }\fbox{$V\left( T\right) \sim \alpha N^{2}$ avec $%
\alpha=\sum_{k=1}^{+\infty}\dfrac{1}{k^{2}}$}

Enfin 
\begin{equation*}
V\left( T\right) -\alpha N^{2}=-N^{2}\sum_{k=N+1}^{+\infty}\dfrac{1}{k^{2}}%
-E\left( T\right) \leq0 
\end{equation*}
\textsl{Conclusion : }\fbox{$V\left( T\right) \leq \alpha N^{2}$}
\end{enumerate}

\item \underline{\'{E}cart \`{a} la moyenne}

\textsl{On rappelle l'in\'{e}galit\'{e} de Bienaym\'{e}-Tchebichev valable
pour une variable al\'{e}atoire }$X$\textsl{\ admettant une esp\'{e}rance et
une variance :}%
\begin{equation*}
\forall \varepsilon>0\quad \func{P}\left( \left \vert X-E\left( X\right)
\right \vert \geq \varepsilon \right) \leq \frac{V\left( X\right) }{%
\varepsilon^{2}}
\end{equation*}
\textsl{\ }Soit $N$ fix\'{e} et une $c$ constante strictement plus grande
que 1.

\begin{enumerate}
\item On a $T\left( \omega \right) -N\ln \left( N\right) =T\left( \omega
\right) -E\left( T\right) +E\left( T\right) -N\ln \left( N\right) $ et par in%
\'{e}galit\'{e} triangulaire 
\begin{equation*}
\left \vert T\left( \omega \right) -N\ln \left( N\right) \right \vert \leq
\left \vert T\left( \omega \right) -E\left( T\right) \right \vert +\left
\vert E\left( T\right) -N\ln \left( N\right) \right \vert 
\end{equation*}

et $E\left( T\right) -N\ln \left( N\right) =NH_{N}-N\ln \left( N\right)
=N\left( H_{n}-\ln \left( N\right) \right) $ et on a vu que \newline
$0\leq u_{n}=H_{n}-\ln \left( N\right) \leq1$ donc

$\left \vert E\left( T\right) -N\ln \left( N\right) \right \vert =E\left(
T\right) -N\ln \left( N\right) \leq N$ et donc

\textsl{Conclusion : }\fbox{$\left \vert T\left( \omega \right) -N\ln \left(
N\right) \right \vert \leq \left \vert T\left( \omega \right) -E\left(
T\right) \right \vert +N$}

Donc, \textbf{si} $\left \vert T-N\ln \left( N\right) \right \vert \geq cN$ 
\textbf{alors} $\left \vert T-E\left( T\right) \right \vert +N\geq \left
\vert T-N\ln \left( N\right) \right \vert \geq cN$ \newline
\textbf{et }$\left \vert T-N\ln \left( N\right) \right \vert \geq cN-N$

\textsl{Conclusion : }\fbox{$\left( \left \vert T-N\ln \left( N\right)
\right \vert \geq cN\right) \subset \left( \left \vert T-E\left( T\right)
\right \vert \geq N\left( c-1\right) \right) $}

\item D'apr\`{e}s l'in\'{e}galit\'{e} de Bienaym\'{e}\&Tchebichev,

On a $\displaystyle \func{P}\left( \left \vert T-E\left( T\right) \right
\vert \geq \left( c-1\right) N\right) \leq \frac{V\left( T\right) }{\left(
c-1\right) ^{2}N^{2}}$ et $V\left( T\right) \leq \alpha N^{2}$ (10.b) ) donc

$\displaystyle \func{P}\left( \left \vert T-E\left( T\right) \right \vert
\geq \left( c-1\right) N\right) \leq \frac{\alpha}{\left( c-1\right) ^{2}}$

et comme $\left( \left \vert T-N\ln \left( N\right) \right \vert \geq
cN\right) \subset \left( \left \vert T-E\left( T\right) \right \vert \geq
N\left( c-1\right) \right) $ alors \newline
$\displaystyle \func{P}\left( \left \vert T-N\ln \left( N\right) \right
\vert \geq cN\right) \leq \func{P}\left( \left \vert T-E\left( T\right)
\right \vert \geq N\left( c-1\right) \right) \leq \frac{\alpha}{\left(
c-1\right) ^{2}}$

\textsl{Conclusion : }\fbox{$\displaystyle \func{P}\left( \left \vert T-N\ln
\left( N\right) \right \vert \geq cN\right) \leq \frac{\alpha}{\left(
c-1\right) ^{2}}$}

Le nombre $N$ \'{e}tant fix\'{e}, $\dfrac{\alpha}{\left( c-1\right) ^{2}}%
\rightarrow0$ quand $c\rightarrow+\infty$ donc, par encadrement (une
probabilit\'{e} est positive)

\textsl{Conclusion : }\fbox{$\func{P}\left( \left \vert T-N\ln \left(
N\right) \right \vert \geq cN\right) \rightarrow0$ quand $c\rightarrow
+\infty$}
\end{enumerate}

\item Soit $\varepsilon>0.$

La question pr\'{e}c\'{e}dente pousserait le professeur de math\'{e}matique 
\`{a} jouer avec les $\varepsilon.$

Plus simplement :

avec $c=\varepsilon \ln \left( N\right) ,$ on a, pour $N>\exp^{1/\varepsilon}
$ , $c>1$ donc$\displaystyle \func{P}\left( \left \vert T-N\ln \left(
N\right) \right \vert \geq \varepsilon \ln \left( N\right) N\right) \leq 
\frac{\alpha}{\left( \varepsilon \ln \left( N\right) -1\right) ^{2}}$

\textsl{Conclusion : }\fbox{par encadrement, $\lim_{N\rightarrow+\infty }%
\func{P}\left( \left \vert T-N\ln \left( N\right) \right \vert \geq
\varepsilon \ln \left( N\right) N\right) =0$}

On peut traduire ces r\'{e}sultats en disant que l'\'{e}v\'{e}nement: \og$T$
s'\'{e}carte de $N\ln \left( N\right) $ de mani\`{e}re significative\fg est
un \'{e}v\'{e}nement asymptotiquement rare.

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

\item Simulation informatique. Dans cette question on consid\`{e}re un jeu
de $N=32$ cartes.

\textbf{Mod\'{e}lisation : } On d\'{e}finit en \texttt{PASCAL} le \texttt{%
TYPE Paquet=ARRAY[1. .32] OF INTEGER;} Le paquet de 32 cartes est repr\'{e}%
sent\'{e} par une variable \texttt{Jeu} de \texttt{TYPE Paquet} rempli
initialement d'entiers entre 1 et 32; donc, initialement, \texttt{Jeu[i]}
contient $i$, c'est \`{a} dire que la carte $C_{i}$ est en position $i.$ Au
cours des insertions, \texttt{Jeu[i]} d\'{e}signe le num\'{e}ro de la carte
en position num\'{e}ro $i$. Par exemple, \texttt{Jeu [i] =10} signifie que
la carte $C_{10}$ est en position $i$.

On indique \`{a} la fin de cette question un extrait de programme \`{a} compl%
\'{e}ter en suivant les questions suivantes:

\begin{enumerate}
\item \'{E}crire la proc\'{e}dure \texttt{Init} permettant de d\'{e}finir
une variable \texttt{Jeu} correspondant \`{a} la configuration initiale du
paquet de cartes.

\texttt{PROCEDURE Init(VAR jeu:paquet);}

\texttt{VAR i:integer;}

\texttt{BEGIN}

\texttt{\hspace*{1cm}FOR i:=1 TO 32 DO jeu[i]:=i;}

\texttt{END;}

\item Compl\'{e}ter la proc\'{e}dure \texttt{Insertion} qui simule une op%
\'{e}ration d'insertion. On rappelle que la fonction \texttt{RANDOM(32)}
permet de tirer un nombre entier au hasard dans l'intervalle $\left[ \left[
0,31\right] \right] $.

\texttt{PROCEDURE insertion (VAR Jeu:paquet);}

\texttt{VAR i,k,cartedessus:INTEGER;}

\texttt{BEGIN}

\texttt{\hspace*{1cm}k:=RANDOM(31)+1;}

\texttt{\hspace*{1cm}cartedessus:=Jeu[1];}

\texttt{\hspace*{1cm}IF k\TEXTsymbol{>}1 THEN FOR i:=1 TO k-1 DO
Jeu[i]:=Jeu[i+1]; }

\texttt{\hspace*{1cm}//d\'{e}calage d'une position}

\texttt{\hspace*{1cm}jeu[k]:=cartedessus;}

\texttt{END;}

\item \texttt{FUNCTION T(Jeu:Paquet):INTEGER;}

\texttt{var n:INTEGER;}

\texttt{begin}

\texttt{\hspace*{1cm}Init(Jeu); // met le paquet en place}

\texttt{\hspace*{1cm}n:=0; // initialise un compteur}

\texttt{\hspace*{1cm}WHILE Jeu[1]\TEXTsymbol{<}\TEXTsymbol{>}32 DO //} le
jeu est battu

\texttt{\hspace*{1cm}BEGIN}

\texttt{\hspace*{2cm}insertion(Jeu);}

\texttt{\hspace*{2cm}n:=n+1; // incr\'{e}mente }

\texttt{\hspace*{1cm}END;}

\texttt{\hspace*{1cm}T:=n;}

\texttt{END;}

Cette proc\'{e}dure effectue les insertions jusqu'\`{a} ce que la carte 32
(celle du dessous) se retrouve au dessus. \texttt{n }compte le nombre
d'insertions n\'{e}cessaires pour y parvenir.

Donc $\mathtt{T}$ simule $T_{N-1}$ et non pas $T$ ...pi\`{e}ge !

C'est donc un de moins que le nombre d'insertions pour

\item Pour \'{e}crire le programme principal permettant de calculer et
d'afficher la moyenne des valeurs prises par la fonction T sur 100 exp\'{e}%
riences et compl\'{e}ter la ligne de d\'{e}claration de variables, il ne
reste, dans le programme principal, qu'\`{a} appeler 100 fois \texttt{T} et 
\`{a} totaliser les r\'{e}sultats ($\mathtt{S}$ accumulateur) .

\texttt{TYPE Paquet=ARRAY[1..32] OF INTEGER;}

\texttt{VAR Jeu:Paquet;}

\texttt{\hspace*{1cm}S,n:integer;}

\texttt{BEGIN}

\texttt{\hspace*{1cm}RANDOMIZE;}

\texttt{\hspace*{1cm}S:=0;}

\texttt{\hspace*{1cm}FOR n:=1 to 100 do S:=S+T(Jeu);}

\texttt{\hspace*{1cm}Writeln(S/100);}

\texttt{END.}
\end{enumerate}
\end{enumerate}

\subsection*{Partie 3 - Distance variationnelle \`{a} la loi uniforme}

Notations:

\begin{itemize}
\item On note $\pi$ l'\'{e}quiprobabilit\'{e} sur $S_{N}$; c'est-\`{a}-dire
l'application de $\mathcal{P}\left( S_{N}\right) $ dans $\left[ 0,1\right] $
telle que :%
\begin{equation*}
\forall A\subset S_{N}\quad \pi \left( A\right) =\frac{\func{card}\left(
A\right) }{N!};\text{ en particulier,}\forall \sigma \in S_{N}\quad \pi
\left( \left \{ \sigma \right \} \right) =\frac{1}{N!}
\end{equation*}

\item On note \'{e}galement $\mu_{n}$ la probabilit\'{e} sur $S_{N}$ d\'{e}%
finie comme suit :

pour chaque configuration $\sigma$ de $S_{N}$,\ $\mu_{n}\left( \left \{
\sigma \right \} \right) $ d\'{e}signe la probabilit\'{e} qu'\`{a} l'instant 
$n$ le tas de cartes se trouve dans la configuration $\sigma$.

On a alors pour toute partie $A$ de $S_{N}$, $\mu_{n}\left( A\right) =\sum
\limits_{\sigma \in A}\mu_{n}\left( \left \{ \sigma \right \} \right) $

On peut mesurer la qualit\'{e} du m\'{e}lange \`{a} un instant donn\'{e} $n$
en estimant l'\'{e}cart entre $\mu_{n}$ et $\pi.$ Une \textsl{distance} $d$
entre ces probabilit\'{e}s est d\'{e}finie de la mani\`{e}re suivante :%
\begin{equation*}
d\left( \mu_{n},\pi \right) =\max \left \{ \left \vert \mu_{n}\left(
A\right) -\pi \left( A\right) \right \vert \ ,\ A\subset S_{N}\right \} 
\end{equation*}
\end{itemize}

\begin{enumerate}
\item \setcounter{enumi}{13}
\end{enumerate}

\begin{enumerate}
\item Soient $A$ une partie de $S_{N}$, $n\in \mathbb{N}^{\ast}$ et $E_{n}$\
l'\'{e}v\'{e}nement: \og \`{a} l'instant $n$ le paquet de cartes se trouve
dans une configuration qui appartient \`{a} la partie A.\fg

\begin{enumerate}
\item A l'instant $T$, le paquet a \'{e}t\'{e} m\'{e}lang\'{e} et toutes les
configurations sont \'{e}quiprobables.

Et pour les m\^{e}mes raisons, \`{a} tout instant ult\'{e}rieur, les
configurations seront toutes \'{e}quiprobables.

Donc sachant l'instant $n\geq T,$ la probabilit\'{e} est l'\'{e}quiprobable
: $\pi$.

\textsl{Conclusion : }\fbox{$\func{P}_{T\leq n}\left( E_{n}\right) =\pi
\left( A\right) $}

\textsl{Conclusion : }\fbox{$\func{P}\left( E_{n}\cap \left( T\leq n\right)
\right) =\func{P}\left( T\leq n\right) \func{P}_{T\leq n}\left( E_{n}\right)
=\pi \left( A\right) \func{P}\left( T\leq n\right) $}

\item Si $\left( E_{n}\cap T>n\right) $ alors $\left( T>n\right) $ donc $%
\left( E_{n}\cap T>n\right) \subset \left( T>n\right) $

\textsl{Conclusion : }\fbox{$\func{P}\left( E_{n}\cap T>n\right) \leq \func{P%
}\left( T>n\right) $}

\item Pour tout $\sigma,\mu_{n}\left( \sigma \right) =\func{P}\left( \og %
\sigma \text{ \`{a} l'instant }n\fg \right) $ donc $\mu_{n}\left( A\right) =%
\func{P}\left( E_{n}\right) .$

et comme $\left( T>n,T\leq n\right) $ est nu syst\`{e}me complet d'\'{e}v%
\'{e}nements, 
\begin{align*}
\func{P}\left( E_{n}\right) & =\func{P}\left( E_{n}\cap \left( T\leq
n\right) \right) +\func{P}\left( E_{n}\cap T>n\right) \\
& =\pi \left( A\right) \func{P}\left( T\leq n\right) +\func{P}\left(
E_{n}\cap T>n\right)
\end{align*}
avec $\func{P}\left( T\leq n\right) $ donc $\pi \left( A\right) \func{P}%
\left( T\leq n\right) \leq \pi \left( A\right) $ et $\func{P}\left(
E_{n}\cap T>n\right) \leq \func{P}\left( T>n\right) $

\textsl{Conclusion : }\fbox{$\mu_{n}\left( A\right) \leq \pi \left( A\right)
+\func{P}\left( T>n\right) $}
\end{enumerate}

\item Soit $A$ une partie de $S_{N}$ et $n\in \mathbb{N}^{\ast}$. On note $%
\overline{A}$ l'\'{e}v\'{e}nement contraire de $A$.

\begin{enumerate}
\item $\mu_{n}$ est une probabilit\'{e} donc $\mu_{n}\left( \overline {A}%
\right) =1-\mu_{n}\left( A\right) $ et de m\^{e}me $\pi \left( \overline{A}%
\right) =1-\pi \left( A\right) $

\textsl{Conclusion : }\fbox{$\mu_{n}\left( \overline{A}\right) -\pi \left( 
\overline{A}\right) =\pi \left( A\right) -\mu_{n}\left( A\right) $ }

\item De $\mu_{n}\left( A\right) \leq \pi \left( A\right) +\func{P}\left(
T>n\right) $ on tire $\pi \left( A\right) -\mu_{n}\left( A\right) \geq-\func{%
P}\left( T>n\right) $

l'in\'{e}galit\'{e} pr\'{e}c\'{e}dente \'{e}tant vraie pour toute partie $A$
de $S_{N},$ elle l'est aussi pour $\overline{A}$

Donc $\pi \left( \overline{A}\right) -\mu_{n}\left( \overline{A}\right) \geq-%
\func{P}\left( T>n\right) $ soit $\mu_{n}\left( \overline {A}\right) -\pi
\left( \overline{A}\right) \leq \func{P}\left( T>n\right) $

et comme d'autre part $\pi \left( A\right) -\mu_{n}\left( A\right) =\mu
_{n}\left( \overline{A}\right) -\pi \left( \overline{A}\right) $ on a donc

$-\func{P}\left( T>n\right) \leq \pi \left( A\right) -\mu_{n}\left( A\right)
\leq \func{P}\left( T>n\right) $ soit

\textsl{Conclusion : }\fbox{$\left \vert \pi \left( A\right) -\mu_{n}\left(
A\right) \right \vert \leq \func{P}\left( T>n\right) $}

\item Les quantit\'{e}s de $\left \{ \left \vert \mu_{n}\left( A\right) -\pi
\left( A\right) \right \vert \ ,\ A\subset S_{N}\right \} $ sont toutes
comprises entre $0$ et $\func{P}\left( T>n\right) .$

Donc le maximum $d\left( \mu_{n},\pi \right) $ \'{e}galement

\textsl{Conclusion : }\fbox{$0\leq d\left( \mu_{n},\pi \right) \leq \func{P}%
\left( T>n\right) $}

$T$ \'{e}tant une variable al\'{e}atoire, sa fonction de r\'{e}partition
tend vers $1$ en $+\infty$.

Et donc $\func{P}\left( T>n\right) =1-\func{P}\left( T\leq n\right)
\rightarrow1-1=0$ quand $n\rightarrow+\infty$

\textsl{Conclusion : }\fbox{par encadrement $\lim_{n\rightarrow+\infty
}d\left( \mu_{n},\pi \right) =0$}
\end{enumerate}
\end{enumerate}

\subsection*{Partie 4 Une majoration de $\func{P}\left( T>n\right) $}

Dans cette partie, nous int\'{e}ressons provisoirement \`{a} un
collectionneur de timbres. Celui-ci re\c{c}oit chaque jour une lettre
affranchie avec un timbre choisi au hasard uniform\'{e}ment parmi les $N$
timbres en vigueur. On \'{e}tudie ici le nombre de jours que doit attendre
le collectionneur pour poss\'{e}der 1a collection compl\`{e}te des $N$
timbres. Le jour $0$ il n'a aucun timbre.

On note alors:

\begin{itemize}
\item pour tout entier $k\in \left[ \left[ 1,N\right] \right] ,$ $S_{k}$ le
nombre al\'{e}atoire de jours que doit attendre le collectionneur pour que
le nombre de timbres diff\'{e}rents qu'il poss\`{e}de passe de $k-1$ \`{a} $k
$,

\item $S=S_{1}+S_{2}+\cdots+S_{N}$, soit la variable al\'{e}atoire
correspondant au nombre de jours \`{a} attendre pour poss\'{e}der la
collection compl\`{e}te des $N$ timbres,

\item en supposant les $N$ timbres en vigueur num\'{e}rot\'{e}s de $1$ \`{a} 
$N$, pour tout $j$ de $\left[ \left[ 1,N\right] \right] ,\ B_{j}^{m}$ l'\'{e}%
v\'{e}nement \og le jour $m$, le collectionneur n'a toujours pas re\c{c}u de
lettre affranchie avec le timbre num\'{e}ro $j$ \fg
\end{itemize}

On admet que les variables al\'{e}atoires $\left( S_{k}\right) _{k\in \left[ %
\left[ 1,N\right] \right] }$ sont ind\'{e}pendantes.

\begin{enumerate}
\item \setcounter{enumi}{16}

\item $S_{1}$ est le temps d'attente du premier timbre donc $S_{1}=1,$
variable certaine.

\item Pour tout $k\in \left[ \left[ 2,N\right] \right] ,$ $S_{k}$ est le
temps d'attente d'un timbre diff\'{e}rent des $k-1$ qu'il poss\`{e}de d\'{e}j%
\`{a}, avec une probabilit\'{e} $\frac{N-\left( k-1\right) }{N}$ chaque
jour, les arrivages \'{e}tant ind\'{e}pendants.

Donc $S_{k}\hookrightarrow \mathcal{G}\left( 1-\frac{k-1}{N}\right) $ loi de 
$\Delta_{N-k+1}$

\item Donc $S=S_{1}+S_{2}+\cdots+S_{N}$ est une somme de variables ind\'{e}%
pendantes de m\^{e}me lois (en ordre invers\'{e}s) que $T=\Delta
_{1}+\cdots+\Delta_{N-1}+1.$

\textsl{Conclusion : }\fbox{$S$ suit la m\^{e}me loi que $T$}

Ce r\'{e}sultat sera utilis\'{e} pour estimer la quantit\'{e} $\func{P}%
\left( T>n\right) .$

\item Soit $m\in \mathbb{N}^{\ast}$

\begin{enumerate}
\item $\left( S>m\right) $ signifie que le $m^{i\grave{e}me}$ jour, le
collectionneur n'a toujours pas les $N$ timbres. Donc que l'un au moins des
timbre n'a pas \'{e}t\'{e} re\c{c}u au jour $m:\left( S>m\right)
=\bigcup_{j=1}^{N}B_{j}^{m}$

\item Pour tout entier $j\in \left[ \left[ 1,N\right] \right] ,$ $B_{j}^{m}$
signifie que le timbre $j$ n'a pas \'{e}t\'{e} re\c{c}u pendant les $m$
jours (intersection d'\'{e}v\'{e}nements ind\'{e}pendants)

Donc $\func{P}\left( B_{j}^{m}\right) =\left( 1-\frac{1}{N}\right) ^{m}$ 

\item On rappelle que pour tout entier $n\geq2$ et pour toute famille d'\'{e}%
v\'{e}nements $A_{1},\dots,A_{n},$ on a l'in\'{e}galit\'{e} : $\func{P}%
\left( \bigcup_{i=1}^{n}A_{i}\right) \leq \sum_{i=1}^{n}\func{P}\left(
A_{i}\right) .$

$\left( S>m\right) =\bigcup_{j=1}^{N}B_{j}^{m}$ donc $\func{P}\left(
S>m\right) \leq \sum_{i=1}^{N}\func{P}\left( B_{j}^{m}\right) =N\left( 1-%
\frac{1}{N}\right) ^{m}$
\end{enumerate}

\item 
\begin{enumerate}
\item La fonction $x\rightarrow \ln \left( 1+x\right) $ \'{e}tant concave,
elle sa courbe est en dessous de sa tangente en $0,$ d'\'{e}quation $y=x$

\textsl{Conclusion : }\fbox{$\ln \left( 1+x\right) \leq x$ pour tout $x\in %
\left] -1,+\infty \right[ $}

Or 
\begin{align*}
\left( 1-\frac{1}{N}\right) ^{m}& =\exp \left( m\ln \left( 1-\frac{1}{N}%
\right) \right) \text{ et } \\
\ln \left( 1-\frac{1}{N}\right) & \leq -\frac{1}{N}\text{ car }\frac{-1}{N}%
\in \left] -1,+\infty \right[ \text{ donc } \\
\left( 1-\frac{1}{N}\right) ^{m}& \leq \exp \left( -\frac{m}{N}\right) \text{
et } \\
\func{P}\left( S>s\right) & =N\left( 1-\frac{1}{N}\right) ^{m}\leq N\exp
\left( -\frac{m}{N}\right) 
\end{align*}%
Et comme $S$ et $T$ ont la m\^{e}me loi , $\func{P}\left( T>s\right) =\func{P%
}\left( S>s\right) $

\textsl{Conclusion : }\fbox{$\func{P}\left( T>m\right) \leq Ne^{-\tfrac{m}{N}%
}$}
\end{enumerate}

\item On reprend les notations introduites dans la partie pr\'{e}c\'{e}dente.

\begin{enumerate}
\item Soit $c>0$ fix\'{e}.

On a vu (15.b) que $0\leq d\left( \mu_{n},\pi \right) \leq \func{P}\left(
T>n\right) $ pour tout entier $n\in \mathbb{N}^{\ast}$

et \`{a} la question pr\'{e}c\'{e}dente $\func{P}\left( T>n\right) \leq Ne^{-%
\tfrac{n}{N}}$ pour tout $n\in \mathbb{N}^{\ast}$

donc $d\left( \mu_{n},\pi \right) \leq Ne^{-\tfrac{n}{N}}.$

Et pour tout entier $n\geq N\ln \left( N\right) +cN$ on a : $-\tfrac{n}{N}%
\leq-\ln \left( N\right) +c$

d'o\`{u} $e^{-\tfrac{n}{N}}\leq e^{-\ln \left( N\right) +c}=\frac{1}{N}e^{-c}
$

\textsl{Conclusion : }\fbox{%
\begin{tabular}[t]{l}
$d\left( \mu_{n},\pi \right) \leq e^{-c}$ \\ 
pour tout entier $n\geq N\ln \left( N\right) +cN$%
\end{tabular}
}

\item Application num\'{e}rique. On estime qu'une distance en variation \`{a}
la loi uniforme de $0,2$ est acceptable.

Avec un jeu de 32 cartes, combien de battages par insertions doit-on faire
pour consid\'{e}rer le paquet m\'{e}lang\'{e} de fa\c{c}on acceptable?

On veut $d\left( \mu_{n},\pi \right) \leq0,2$. Il suffit pour cela que $%
e^{-c}\leq0,2$

soit $c\geq-\ln \left( 0,2\right) =-\ln \left( \frac{1}{5}\right) =\ln
\left( 5\right) $

Il suffit donc de prendre $n\geq32\ln \left( 32\right) +32c\geq32\left( \ln
\left( 32\right) +\ln \left( 5\right) \right) =32\ln \left( 160\right)
\simeq162$ pour que le paquet soit m\'{e}lang\'{e} de fa\c{c}on acceptable.
\end{enumerate}
\end{enumerate}

\end{document}