
  {\it Ces travaux
dirigés suivent \cite{GS}, section 3.9 pages 71 et suivantes. Nous suivrons la présentation élémentaire (sans le
formalisme martingales et chaînes de Markov). On montre tous les résultats par des raisonnements élémentaires, le
principe de réflexion et un usage habile de la fonction génératrice. Cette présentation élémentaire est à connaître.
L'option probabilité verra des résultats complémentaires, et retrouvera les mêmes, grâce aux martingales et aux chaînes
de Markov. Le nombre des questions qu'on peut se poser sur le jeu de pile ou face est immense. En fait, la liste des
questions et réponses présentée aussi dépend aussi de l'accessibilité technique du résultat. Un ouvrage entier
classique, en deux tomes, le Feller, est entièrement consacré au jeu de pile ou face.  Voici une liste succincte des
questions que l'on se pose avec une indication des réponses démontrées dans ce chapitre. }

\medskip
 Soit $X_n$ une suite de variables de Bernoulli  i.i.d.
centrées de paramètre $p$, c'est-à-dire $\Pro(X_n=1)=p$ et $\Pro(X_n=-1)=1-p=q$. Soit $S_0$ une v.a. indépendante des
$X_i$ telle que $\Pro(S_0=k)>0$ pour tout $k\in \relative$. On pose $S_n=S_0+\sum_{i=1}^nX_i.$ On peut interpréter
$S_n$ comme la fortune d'un joueur de roulette ou de pile ou face. La probabilité de gagner pour le joueur est $p$ et
sa mise est supposée unitaire. $X_n$ désigne le $n$-ième tirage. Par exemple si le joueur joue à rouge ou noir, sa
probabilité est $\frac{18}{37}$, car il y a 36 chiffres colorés dont 18 noirs et 18 rouges, plus le zéro. La banque
ramasse tout quand le zéro sort. (Lire {\it Le Joueur} de Dostoïevsky pour tous les détails, probablement la plus belle
analyse littéraire et psychologique du jeu de roulette mais avec une suite d'observations concrètes). La suite $S_n$
s'appelle une {\it marche aléatoire simple}. Elle correspond aussi au mouvement aléatoire d'une particule sur
$\natural$, progressant de $+1$ avec probabilité $p$ et reculant de $-1$ avec probabilité $q$.  La marche est appelée
symétrique si $p=q=\frac 12$.

\medskip
\begin{itemize}
\item $S_n$ est-elle une chaîne de Markov (le futur ne dépend que du présent?). Oui, calculs élémentaires de
probabilité conditionnelle.
\item Ruine du joueur: le joueur commence avec une fortune de $k$, la banque a une fortune de $N$ : le jeu
s'arrète-t-il en temps fini? (oui, technique de temps d'arrêt élémentaire). Permet de montrer ``a la main'' le théorème
d'arrêt de Doob.
\item Ruine du joueur: quelle est l'espérance du temps de jeu? $D_k=k(N-k)$. L'interprétation de ce résultat est
passionnante.  Technique d'espérance conditionnelle (discrète).
\item Ruine du joueur: Probabilité de ruine du joueur: $p_k=1-\frac kN$. Là encore l'interprétation doit faire l'objet
d'une discussion (la meilleure illustration est le film de Luigi Comencini, {\it L'argent de la vieille}).
\item Le retour à l'origine partant de l'origine. Calcul de la probabilité de retour: $1-|p-q|$. Technique : usage
intensif des fonctions génératrices de distributions discrètes.
\item Egalement par la même  technique : calcul de la probabilité de retour en exactement $k$ pas.
\item Egalement par la même technique : calcul des probabilités d'atteindre 1, 2, $r$ partant de 0. On utilise aussi le
{\it  principe de réflexion}.
\item Probabilité  d'aller de $a>0$ en $b>0$ sans passer par 0 (c'est-à-dire sans se ruiner). Ce calcul utilise
l'astuce remarquable du {\bf principe de réflexion}.
\item Une suite de résultats sur la probabilité des longueur d'excursions sans ruine permet d'établir le {\bf théorème
de ballotage ou de scrutin}, qui donne la probabilité (étonnament élevée) que lors d'un dépouillement de votes le
résultat du dépouillement partiel contredise le résultat final. La loi de l'arcsinus montre évalue la probabilité que
dans un jeu  un des joueurs soit gagnant ($S_n>0$)  sur une très longue période. L'interprétation de ces résultats
permet de comprendre mieux le phénomène du jeu de hasard, l'existence des casinos, les suspenses paradoxaux provoqués
par le jeu. {\bf Lors d'une leçon sur pile ou face, il est essentiel d'interpréter chaque résultat donné.}

\end{itemize}}
 

\section{Propriétés élémentaires}

\dexer


\quest 1) Représentation graphique standard : tirer à pile ou face
10 fois. Noter les résultats.  Représenter les résultats avec en
abcisse $n$ et en ordonnée la valeur de $S_n$, avec $S_0=0$.
Joindre les points par des segments de droite.


\quest 2) Homogénéité spatiale. Montrer que
\begin{equation} \label{homogeneitespatiale}
\Pro(S_n=j|S_0=a)=\Pro(S_n=j+b|S_0=a+b).
\end{equation}
Indication : Montrer que les deux cotés sont égaux à
$\Pro(\sum_1^nX_i=j-a).$


\quest 3) Homogénéité temporelle   Montrer que
\begin{equation} \label{homogeneitetemporelle}
\Pro(S_n=j|S_0=a)=\Pro(S_{m+n}=j|S_m=a).
\end{equation}
Indication : Le membre de gauche est $\Pro(\sum_1^nX_i=j-a) $ et
le membre de droite est $\Pro(\sum_{m+1}^{m+n}X_i=j-a).$

\quest 4) Les marches aléatoires simples ont la propriété de
Markov
\begin{equation}
\label{proprietedeMarkovmarchesaleatoires}  \Pro(S_{m+n}=j|S_0,\;
S_1,\;\dots,\;S_m)=\Pro(S_{m+n}=j|S_m),\;\; n\geq 0.
\end{equation}
D'abord, comprenons bien ce que veut dire cette relation,  à
savoir que pour toutes les valeurs possibles de $a_0$, $a_1$, ...,
$a_m$, on a
\begin{equation} \label{traductionMarkov}
\Pro(S_{m+n}=j|S_0=a_0,\;S_1=a_1,\;\dots,\;S_m=a_m)=
\Pro(S_{m+n}=j|S_m=a_m).
\end{equation}


 La
``démonstration" de \cite{GS} est la suivante ``If one
knows the value of $S_m$, then the distribution of $S_{m+n}$
depends only on the jumps $X_{m+1},\;\dots,\; X_{m+n}$ and cannot
depend on further information concerning the values of $S_0,\;
S_1,\; \dots,\; S_{m-1}$.  Vous paraît-elle suffisante ?

\quest 5) Montrer (\ref{proprietedeMarkovmarchesaleatoires}) en
menant les calculs grâce à (\ref{traductionMarkov}) et en
utilisant la définition de la probabilité conditionnelle.
\fexer

\dsolution {}(C'est juste une indication, je vous conseille de
détailler un peu plus...)
$$\Pro(S_{m+n}=j|(S_0\dots S_m)=(a_0\dots a_m))=
\Pro(\sum_{m+1}^nX_i=j-a_m|(S_0\dots S_m)=(a_0\dots a_m))=
$$
$$\frac{\Pro(\sum_{m+1}^nX_i=j-a_m)\Pro((S_0\dots S_m)=(a_0\dots
a_m))}{\Pro((S_0\dots S_m)=(a_0\dots a_m)) }=\Pro(\sum_{m+1}^n
X_i=j-a_m)=
$$
$$=\Pro(S_{m+n}=j|S_m=a_m).$$


\fsolution

\dexer {\bf Pile ou face-La ruine du joueur}, \cite{GS} 1.7 p. 17 et 3.9 p. 74. Un joueur a une fortune de $k$ et il
désire atteindre en jouant à pile ou face une fortune de $N$,
$0<k<N$. Il parie toujours sur pile, qui a probabilité $p$. La
question est de savoir avec quelle probabilité il se ruinera avant
d'atteindre son but. On désigne par $A_k$ l'événement ``ruine du
joueur, partant d'une fortune $S_0=k$" et par $B$ l'événement que
le résultat du premier tirage est pile.   On munit l'espace
$\Omega$ des suites infinies de tirages de la probabilité $\Pro$
construite par le théorème de Kolmogorov.  On note $\omega
=(\omega_1,\;\omega_2,\;\dots\omega_n,\dots)$ un élément de
$\Omega$. On note également $\omega =(\omega_1, \omega^1)$ avec
$\omega^1=(\omega_2,\;\dots,\; \omega_n,\dots).$

\quest 1)   Donner une définition formelle de l'événement ``ruine
du joueur". On utilisera le temps d'arrêt
$$t_k(\omega)=\inf\{n,\; k+\omega_1+\dots+\omega_n=0 \hbox{ ou } N\}.$$
Montrer que  $t_k$ est mesurable.
 Montrer que pour $1<k<N-1$,
$$\Pro(A_k)=p \Pro(A_{k+1})+ q\Pro(A_{k-1}).$$
On commencera par interpréter cette formule.
 Vérifier que cette formule est encore valable pour $k=1$ ou $N-1$ en
remarquant que $\Pro(A_0)=1$ et $\Pro(A_{N})=0$
\newline {\it Indication : montrer que pour $\omega\in \{\omega_1=1\},$ on a $t_k(\omega)= t_{k+1}(\omega^1)+1.$
Attention : ni \cite{GS} ni \cite{F} ne jugent bon de donner cette preuve. Le formalisme de \cite{GS} est discutable :
ils notent $\Pro_k(A)$ ce que nous notons $\Pro(A_k)$, l'év\'enement $A$ étant alors un év\'enement absolu appelé
``ruine du joueur". L'ennui, c'est que cet év\'enement dépend du point de départ $k$ et donc, $A$ a de toutes manières
une signification différente quand $k$ change. Il vaut mieux le noter $A_k$ et garder le même espace de probabilité
$\Omega$ pour toutes les marches aléatoires. Pour le reste, nous suivons \cite{GS}.}


\quest 2) On  pose $p_k=\Pro(A_k)$.  Si $p=\frac 12$,  déduire que
$p_k=\frac 12(p_{k+1}+p_{k-1})$, $0<k<N$.

\quest 3) En utilisant les valeurs de $p_0$ et $p_N$, montrer que
$$\Pro(A_k)=1-\frac kN.$$

\quest 4) Interpréter cette relation. On pourra s'inspirer comme suggéré par Grimmett-Stirzaker de ``Millionaires
should always gamble, poor men never" (J.M. Keynes). Et voir {\it L'argent de la vieille} de Luigi Comencini.

\quest 5) Plus généralement, on a l'équation
$p_k=p.p_{k+1}+qp_{k-1}$, $1\leq k\leq N-1$, avec conditions au
bord $p_0=1$, $p_N=0$.  Montrer que
$$p_k=\frac{(\frac qp)^k-(\frac qp)^N}{1-(\frac qp)^N}.$$


\quest 6) En déduire $q_k$, la probabilité que le joueur fasse
fortune.

\quest 7) Vérifier que $p_k+q_k=1$. Interpréter.

\quest 8) Montrer que le temps d'arrêt est presque sûrement fini.

\quest 9) On pose $D_k=\esp t_k$. Grimmett-Stirzaker n'écrit pas
cette définition mais décrit $D_k$ comme ``the mean number of
steps before the particle hits one of the absorbing barriers,
starting from $k$ ".  Justifier la relation proposée par ces
auteurs
$$D_k=p(1+D_{k+1}) + q(1+D_{k-1}), \;\; 1\leq k\leq N-1, \;\;
D_0=D_N=0.
$$
 Pour cela, on appliquera au temps d'arrêt   les formules de l'espérance
conditionnelle pour des variables aléatoires discrètes et des
événements $B$ que l'on rappelle :
\begin{equation} \label{esperanceconditionnelleaevenement}
\esp Y=\sum_x \esp(Y|X=x)\Pro(X=x),
\end{equation}
\begin{equation}\label{definitionesperanceconditionnellediscrete}
\esp(Y|B)=\sum_l l\Pro(Y=l|B).
\end{equation}


\quest 10) En déduire que
$$D_k=\frac 1{q-p}\left[k-N\left(\frac{1-(\frac qp)^k}{1-(\frac
qp)^N}\right)\right] \;\; \hbox{ si } p\neq \frac 12,$$
$$D_k=k(N-k)\;\; \hbox{ si } p=\frac 12.$$

\quest 11)  Interpréter ces résultats.

\fexer

\dsolution{}

\quest 1) On a
$$A_k =\{t_k(\omega)=\inf\{n,\;k+\omega_1+\dots+\omega_n=0\hbox{
ou } N\}<\infty \hbox{ et } k+\omega_1+\dots
+\omega_{t_k(\omega)}=0\}.$$ On écrit $A_k=(A_k\cap
\{\omega_1=1\})\cup(A_k\cap\{\omega_1=-1\}).$ Mais pour $\omega\in
\{\omega_1=1\},$  on a
$$t_k(\omega)=\inf\{n,\;k+1+\omega_2+\dots+\omega_n=0\hbox{ ou }
N\}<\infty=t_{k+1}(\omega^1)+1.$$
 On en déduit que
$$A_k\cap\{\omega_1=1\}=\{t_{k+1}(\omega^1) <\infty \hbox{ et } k+1+\omega_2+\dots
+\omega_{t_{k+1}(\omega^1)}=0\}\cap \{\omega_1=1\}.$$ Comme les
$X_i$ sont i.i.d., on obtient
$$\Pro(A_k\cap \{\omega_1=1\})=p\Pro(A_{k+1}).$$
On conclut aisément.


 \quest 2), 3) 4) Immédiat, simple calcul. Le
résultat nous dit que plus on est pauvre, moins on a de chances de
devenir riche. L'interprétation est toutefois facilitée si on
considère le jeu de manière symétrique : le  premier joueur
possède $k$ et le second possède $N-k$. On peut alors reformuler
la règle du jeu ainsi : le jeu s'arrète quand l'un des deux
joueurs est ruiné.  La probabilité de ruine du premier joueur est
$\frac{N-k}N$ et celle du second $\frac kN$. L'une tend vers 1 et
l'autre vers 0 quand $\frac Nk$ tend vers l'infini. Les riches
gagnent donc presque toujours. Mais, quand ils perdent, il perdent
gros, comme on peut le vérifier en remarquant que l'espérance des
gains des deux joueurs au moment de l'arrêt du jeu sont les mêmes
et égales à zéro. En effet, l'espérance du gain du premier joueur
est $-k\Pro(A_k) + (N-k)(1-\Pro(A_k))= 0$ et on vérifie
immédiatement que celle du second est aussi zéro.  Ce résultat est
connu sous le nom de théorème d'arrêt de Doob (\cite{W} page 100),
mais pour appliquer directement ce théorème il faudrait d'abord
démontrer que le temps d'arrêt $t_k(\omega)$ est presque sûrement
fini.  Une autre manière de calculer $\Pro(A_k)$ est donc, pour
ceux qui connaissent les martingales, de :

\begin{itemize}
\item montrer que le temps
d'arrêt du jeu est presque sûrement fini.

\item utiliser le théorème d'arrêt qui dit que sous cette
condition, $\esp S_{t_k}=\esp S_0=k$, ce qui veut exactement dire
que l'espérance de gain est nulle.
\end{itemize}
 Il est quand même préférable de savoir que l'on peut tout faire
 avec des moyens élémentaires !

\quest 5) Calculs classiques avec la formule de récurrence.

\quest 6) La valeur de $q_k$ s'interprète comme une probabilité de
ruine  en échangeant les rôles de  $p$ et $q$ et de $k$ et $N-k$.
On obtient donc $q_k = \frac{(\frac pq)^{N-k}-(\frac
pq)^N}{1-(\frac pq)^N}.$

\quest 7) 8) La relation est vite vérifiée. On en déduit que
presque sûrement, le joueur se ruine ou fait fortune en temps
fini, ce qui veut implique que $t_k$ est presque sûrement fini.

\quest 9) On a en utilisant
 (\ref{definitionesperanceconditionnellediscrete}),
$$\esp(t_k|X_1=-1)=\sum_l
l\frac{\Pro(t_k=l;X_1=-1)}{\Pro(X_1=-1)}=$$
$$\sum_l l\frac{\Pro(\inf\{n,\; k-1+X_2+\dots +X_n=0\hbox{ ou } N\}=l)q}{q}=$$
$$\sum_l l\Pro(\inf\{n,\; k-1+X_1+\dots + X_{n-1}=0\hbox{ ou } N\}=l)=$$
$$\sum_l l\Pro(\inf\{n-1,\; k-1+X_1+\dots +X_{n-1}=0\hbox{ ou } N\}=l-1)=$$
$$1+\sum_l (l-1)\Pro(t_{k-1}=l-1)=1+\esp t_{k-1} = 1+D_{k-1}$$
On a utilisé le fait que $X_2+\dots +X_n$ et $X_1+\dots +X_{n-1}$ ont la même loi, l'indépendance de $X_1$ et des $X_i$
pour $i\geq 2$ et le fait que $t_k$ est presque sûrement fini. On a de même
$$\esp(t_k|X_i=+1)= 1+ D_{k+1}.$$
En utilisant la formule (\ref{esperanceconditionnelleaevenement}),
appliquée à $Y=t_k$ et $X=X_1$, on obtient comme demandé
$$D_k=p(1+D_{k+1})+q(1+D_{k-1}).$$

\quest 10)-11) Simple calcul.   L'interprétation n'est pas très
excitante si $p$ est très différent de $q$, car alors l'un des
joueurs a beaucoup plus de chances que l'autre. On va donc
interpréter le cas $p=\frac 12$ et remarquer qu'aux jeux de
casino, $p$ est assez proche de $\frac 12$ et la première formule
donnée pour $D_k$ peut alors s'interpréter dans la même ligne que
la seconde.   Le point important qui a été démontré est que
\newline\newline
{\bf le temps de jeu $D_k=k(N-k)$ est proportionnel au produit des
fortunes des deux joueurs.}
\newline
\newline
Ceci explique pourquoi les casinos existent. On doit d'une part
avoir $N-k$ très grand pour que le casino ne perde jamais. Cela
garantit de plus un temps moyen de jeu élevé pour tous les joueurs
et donc permet de les ``accrocher". La fortune du casino étant
grande et fixée, on remarque que la même formule donne un temps de
jeu à peu près proportionnel   à la fortune du joueur.  Pour
s'amuser longtemps dans un casino, il vaut mieux faire de petites
mises, et, à fortune égale, le temps de jeu est grosso modo double
si les mises sont deux fois plus petites.  On voit surgir d'
intéressantes questions de stratégie pour le casino : il faut
imposer des mises pas trop petites, car sinon le client risque de
ressortir par simple ennui,  avant d'avoir tout perdu.
Inversement, une mise minimale trop grosse va chasser trop vite
les petits clients qui auront manqué les plaisirs des ``haut et
bas" qui font le charme du jeu. Il y a donc un problème
d'optimisation de la mise minimale imposée en fonction de la
fortune moyenne des clients et de l'estimation du temps de jeu
optimal (une fin de soirée). L'idéal est que les clients aient le
temps de s'amuser avant de sortir les poches vides. \fsolution

\quest{\it Remarque : ce TD était complété pour les rapides par
les exercices pages 65-68 et 85-86 de \cite{O}}
