next up previous contents
Next: Le processus ponctuel de Up: Introduction aux processus stochastiques Previous: Introduction aux processus stochastiques   Contents


La marche aléatoire unidimensionnelle symétrique

Considérons une expérience de Pile ou Face. Pour $ N$ jets successifs, on peut prendre comme univers le produit $ \Omega_N=\set{\text{P},\text{F}}^N$. Considérons alors la variable aléatoire $ S_k$ égale à la différence entre le nombre de Pile et de Face obtenus lors des $ k$ premiers jets. On peut écrire

$\displaystyle S_k = \sum_{j=1}^k X_j$   où $\displaystyle X_j = \begin{cases}\phantom-1 & \text{si le $j$-\\lq eme jet donne Pile\;,}\\ -1 & \text{si le $j$-\\lq eme jet donne Face\;.}\\ \end{cases}$ (3.1)

La marche aléatoire unidimensionnelle symétrique est la suite des $ S_k$ obtenue dans le cas

$\displaystyle \prob{X_j=1} = \prob{X_j=-1} = \frac12\;,$ (3.2)

les $ X_j$ étant supposés indépendants. Les réalisations du processus sont des suites $ \set{S_k(\omega)}$ d'entiers telles que $ S_0(\omega)=0$ et $ S_{k+1}(\omega)-S_k(\omega)=\pm1$ (fig_marche1). La probabilité de chaque suite de longueur $ k$ est $ 2^{-k}$.

\begin{figure}{\small {\bf Figure 3.1. } Une r\'ealisation d'une marche al\'eatoire $S_k(\omega)$.}\end{figure}

Commençons par établir quelques propriétés élémentaires de la variable aléatoire $ S_k$.


\begin{prop}\hfill \begin{enum} \item L'image de $S_k$\ est $S_k(\Omega_N)=\set{... ...end{equation}\item On a $\expec{S_k}=0$\ et $\Var(S_k)=k$. \end{enum}\end{prop}

D´EMONSTRATION.
\begin{enum} \item Suit du fait que $S_0=0$\ et $S_{k+1}-S_k\in\set{-1,1}$. \it... ...c{X_i}=0$\ et $\Var(X_i)=1$, on a $\expec{S_k}=0$\ et $\Var(S_k)=k$. \end{enum}
$ \qedsymbol$

La Proposition 3.1.1 implique que $ S_k$ est nul en moyenne, mais que ses fluctuations sont d'ordre $ \sqrt{k}$. En particulier, la probabilité que le processus se trouve en 0 au $ k$-ème pas est donnée par

$\displaystyle \prob{S_k=0} = \begin{cases}0 & \text{si $k$\ est impair\;,} \\ ... ...ac{(2\ell)!}{2^{2\ell}(\ell!)^2} & \text{si $k=2\ell$\ est pair\;.} \end{cases}$ (3.3)

Remarquons que la formule de Stirling implique que pour $ \ell$ grand,

$\displaystyle \prob{S_{2\ell}=0} \sim \frac1{2^{2\ell}} \frac{\sqrt{4\pi\ell}\e... ...l}(2\ell)^{2\ell}}{2\pi\ell\e^{-2\ell}\ell^{2\ell}} = \frac1{\sqrt{\pi\ell}}\;.$ (3.4)

Cependant, la loi de chaque $ S_k$ ne détermine pas le processus, les $ S_k$ n'étant pas indépendants. Voici d'abord quelques propriétés simples du processus considéré dans son ensemble:


\begin{prop}\hfill \begin{enum} \item \defwd{Propri\'et\'e de Markov:}\/ Pour to... ...d{S_k=n}{S_\ell=m} = \prob{S_{k-\ell}=n-m}\;. \end{equation}\end{enum}\end{prop}

D´EMONSTRATION. Nous pouvons décomposer

$\displaystyle S_k = S_\ell + Y\;, \qquad Y = \sum_{j=\ell+1}^k X_j\;.$ (3.5)

L'indépendance des $ X_i$ implique que $ Y = S_k-S_\ell$ est indépendante de $ X_1,\dots,X_\ell$, donc aussi de $ S_1,\dots,S_\ell$. Il suit que

$\displaystyle \pcond{S_k=n}{S_\ell=m_\ell,\dots,S_1=m_1}$ $\displaystyle = \frac{\prob{Y=n-m_\ell,S_\ell=m_\ell,\dots,S_1=m_1}} {\prob{S_\ell=m_\ell,\dots,S_1=m_1}}$    
  $\displaystyle = \prob{Y=n-m_\ell}\;.$ (3.6)

Par le même raisonnement, nous avons également

$\displaystyle \pcond{S_k=n}{S_\ell=m_\ell} = \prob{Y=n-m_\ell}\;.$ (3.7)

Finalement,

$\displaystyle \prob{Y=n-m} = \biggprob{\sum_{j=\ell+1}^k X_j = n-m} = \biggprob{\sum_{j=1}^{k-j} X_j = n-m} = \prob{S_{k-\ell}=n-m}\;,$ (3.8)

du fait que les $ X_i$ sont identiquement distribués. $ \qedsymbol$

La propriété de Markov signifie que l'évolution du processus ne dépend que de son état présent, indépendamment de son passé. Elle permet d'écrire des relations du genre

\begin{multline} \qquad \prob{S_k=n,S_{k-1}=m,(S_1,\dots,S_{k-2})\in A} \\ = \p... ...n}{S_{k-1}=m} \prob{S_{k-1}=m,(S_1,\dots,S_{k-2})\in A}\;. \qquad \end{multline}

\begin{figure}{\small {\bf Figure 3.2. } Une r\'ealisation d'une marche al\'eatoire pour laquelle $\tau=12$.}\end{figure}

Voyons maintenant comment déduire de ces propriétés des informations non triviales sur les réalisations du processus. Une première quantité intéressante est le temps $ \tau$ du premier retour du processus en 0 (fig_marche2):

$\displaystyle \tau = \inf\setsuch{k\geqs 1}{S_k=0}\;.$ (3.9)

Par exemple, dans l'expérience de jet de pièce de monnaie, $ \tau$ est le nombre de fois que l'on jette la pièce jusqu'à obtenir pour la première fois autant de Pile que de Face. Quelle est la loi de $ \tau$? Il est clair que $ \tau$ ne peut prendre que des valeurs paires. De plus, si $ \tau=k$ alors $ S_k=0$, donc $ \prob{\tau=k}\leqs\prob{S_k=0}$. En fait, il nous faut déterminer

$\displaystyle \prob{\tau=k} = \prob{S_1\neq0,S_2\neq0,\dots,S_{k-1}\neq0,S_k=0}\;.$ (3.10)


\begin{theorem} La loi de $\tau$\ est donn\'ee par \begin{equation} \prob{\tau=... ...rob{S_{k-2}=0} & \text{pour $k$\ pair\;.} \end{cases}\end{equation}\end{theorem}

\begin{figure}{\small {\bf Figure 3.3. } Pour chaque r\'ealisation d'une marche... ...=-1$, obtenue par r\'eflexion par rapport \\lq a l'axe des abscisses.}\end{figure}

D´EMONSTRATION. Supposons que $ \tau=k$. Comme le processus ne peut pas changer de signe sans passer par 0, on a

$\displaystyle \prob{\tau=k} ={}$ $\displaystyle \prob{S_1>0,S_2>0,\dots,S_{k-1}>0,S_k=0}$    
  $\displaystyle {}+ \prob{S_1<0,S_2<0,\dots,S_{k-1}<0,S_k=0}$    
$\displaystyle ={}$ $\displaystyle 2 \prob{S_1>0,S_2>0,\dots,S_{k-1}>0,S_k=0}$    
$\displaystyle ={}$ $\displaystyle 2 \prob{S_1=1,S_2>0,\dots,S_{k-2}>0,S_{k-1}=1,S_k=0}$    
$\displaystyle ={}$ $\displaystyle 2 \pcond{S_k=0}{S_{k-1}=1} \prob{S_1=1,S_2>0,\dots,S_{k-2}>0,S_{k-1}=1} \;,$ (3.11)

où nous avons utilisé la propriété de Markov dans la dernière ligne. La propriété des incréments stationnaires implique

$\displaystyle \pcond{S_k=0}{S_{k-1}=1} = \prob{S_1=-1} = \frac12\;.$ (3.12)

Il suit que

$\displaystyle \prob{\tau=k}$ $\displaystyle = \prob{S_1=1,S_2>0,\dots,S_{k-2}>0,S_{k-1}=1}$ (3.13)
  $\displaystyle = \prob{S_1=S_{k-1}=1} - \prob{S_1=S_{k-1}=1,\, \exists\ell\in\set{2,\dots,k-2}:\,S_\ell=0}\;.$    

Nous utilisons maintenant un argument important, appelé le principe de réflexion: A tout chemin allant de $ (1,1)$ à $ (k-1,1)$ passant par 0, on peut faire correspondre un unique chemin de $ (-1,1)$ à $ (k-1,1)$, obtenu en réfléchissant par rapport à l'axe des abscisses la partie du chemin antérieure au premier passage en 0. On a donc

$\displaystyle \prob{S_1=S_{k-1}=1,\,\exists\ell\in\set{2,\dots,k-2}:\,S_\ell=0} = \prob{S_1=-1,S_{k-1}=1}\;.$ (3.14)

Finalement, en appliquant de nouveau la propriété des incréments stationnaires, on voit que

$\displaystyle \prob{S_1=1,S_{k-1}=1}$ $\displaystyle = \pcond{S_{k-1}=1}{S_1=1}\prob{S_1=1} = \prob{S_{k-2}=0}\cdot\frac12\;,$    
$\displaystyle \prob{S_1=-1,S_{k-1}=1}$ $\displaystyle = \pcond{S_{k-1}=1}{S_1=-1}\prob{S_1=-1} = \prob{S_{k-2}=2}\cdot\frac12\;.$ (3.15)

En remplaçant dans (3.1.19), il vient

$\displaystyle \prob{\tau=k} = \frac12 \bigbrak{\prob{S_{k-2}=0} - \prob{S_{k-2}=2}}\;.$ (3.16)

Le reste de la preuve est un calcul direct. Comme

$\displaystyle \frac{\prob{S_{k-2}=2}}{\prob{S_{k-2}=0}} = \frac{\binom{k-2}{k/2... ...frac k2}!\bigpar{\frac k2-2}!} = \frac{\frac k2 - 1}{\frac k2} = 1 - \frac2k\;,$ (3.17)

on obtient

$\displaystyle \prob{\tau=k} = \frac12 \prob{S_{k-2}=0}\biggbrak{1 - 1 + \frac2k} = \frac1k \prob{S_{k-2}=0}\;,$ (3.18)

ce qui conclut la démonstration. $ \qedsymbol$

Le tableau suivant donne les premières valeurs de la loi de $ \tau$:

$ k$ $ 2$ $ 4$ $ 6$ $ 8$ $ 10$ $ 12$ $ 14$
$ \prob{\tau=k}$ $ \frac12$ $ \frac18$ $ \frac1{16}$ $ \frac5{128}$ $ \frac7{256}$ $ \frac{21}{1024}$ $ \frac{33}{2048}$
  $ =0.5$ $ =0.125$ $ \cong0.063$ $ \cong0.039$ $ \cong0.027$ $ \cong0.021$ $ \cong0.016$
Il est donc assez probable de revenir rapidement en 0, puis la loi prend des valeurs plutôt faibles, tout en décroissant lentement. Il suit de (3.1.6) que pour des grands $ k$, $ \prob{\tau=k}$ décroît comme $ 1/k^{3/2}$. Ce fait a une conséquence surprenante:


\begin{cor} $\expec{\tau}=+\infty$. \end{cor}

D´EMONSTRATION. On a

$\displaystyle \expec{\tau} = \sum_{k\geqs 1}k\prob{\tau=k} = \sum_{\ell\geqs1} ... ...\prob{S_{2\ell-2}=0} \sim \sum_{\ell\geqs1} \frac1{\sqrt{\pi\ell}} = +\infty\;.$ (3.19)

$ \qedsymbol$

En d'autres termes, la marche aléatoire finit toujours par revenir en 0, mais la loi de $ \tau$ décroît trop lentement pour que son espérance soit finie. Cela est lié au fait que si la marche aléatoire s'éloigne beaucoup de 0, il lui faut longtemps pour y revenir.

Considérons une autre application du principe de réflexion. Supposons qu'une machine à sous fonctionne avec une mise d'un euro, et que la machine rende soit deux euros, soit rien, avec la même probabilité. Combien de fois peut-on jouer, si l'on possède initialement $ 10$ euros? La somme que l'on possède après avoir joué $ k$ fois est égale à $ 10-S_k$, on peut donc jouer jusqu'à ce que $ S_k=10$. Il nous faut donc déterminer la loi de

$\displaystyle \tau_L = \inf\setsuch{k\geqs0}{S_k=L}$ (3.20)

pour $ L=10$ dans notre exemple.


\begin{theorem} La loi de $\tau_L$\ est donn\'ee par \begin{equation} \prob{\ta... ...}+2, \dots}$\;,} \\ 0 & \text{sinon\;.} \end{cases}\end{equation}\end{theorem}

D´EMONSTRATION. Considérons le cas $ L>0$. On a

$\displaystyle \prob{\tau_L=k}$ $\displaystyle = \prob{S_1<L,S_2<L,\dots,S_{k-1}=L-1,S_k=L}$    
  $\displaystyle = \pcond{S_k=L}{S_{k-1}=L-1}\prob{S_1<L,S_2<L,\dots,S_{k-1}=L-1}$    
  $\displaystyle = \frac12 \prob{S_1<L,S_2<L,\dots,S_{k-1}=L-1}$ (3.21)
  $\displaystyle = \frac12 \bigbrak{\prob{S_{k-1}=L-1} - \prob{S_{k-1}=L-1,\,\exists j\in\set{1,\dots,k-2}:\,S_j=L}}\;.$    

Invoquons alors à nouveau le principe de réflexion (fig_marche4). A chaque réalisation telle que $ S_{k-1}=L-1$, qui a déjà atteint le niveau $ L$ auparavant, on peut associer une réalisation telle que $ S_{k-1}=L+1$. Nous avons donc

$\displaystyle \prob{\tau_L=k}$ $\displaystyle = \frac12 \bigbrak{\prob{S_{k-1}=L-1} - \prob{S_{k-1}=L+1}}$    
  $\displaystyle = \frac12 \frac1{2^{k-1}} \biggbrak{\binom{k-1}{\frac{k+L}2 -1} - \binom{k-1}{\frac{k+L}2}}$    
  $\displaystyle = \frac{(k-1)!}{2^k} \biggbrak{\frac1{\bigpar{\frac{k+L}2-1}!\bigpar{\frac{k-L}2}!} - \frac1{\bigpar{\frac{k+L}2}!\bigpar{\frac{k-L}2 - 1}!}}$    
  $\displaystyle = \frac1{2^k} \frac{k!}{\bigpar{\frac{k+L}2}!\bigpar{\frac{k-L}2}!} \frac1k \biggbrak{\frac{k+L}2 - \frac{k-L}2}$    
  $\displaystyle = \prob{S_k=L} \frac Lk\;.$ (3.22)

Le cas $ L<0$ suit par symétrie. $ \qedsymbol$

\begin{figure}{\small {\bf Figure 3.4. } Pour chaque r\'ealisation d'une marche... ...btenue par r\'eflexion par rapport \\lq a la droite d'ordonn\'ee $L$.}\end{figure}

Pour des raisons similaires à celles du cas du retour en 0, la loi de $ \tau_L$ décroît en $ 1/k^{3/2}$, et son espérance est donc infinie. On est donc sûr de perdre tôt ou tard, tout en pouvant espérer jouer infiniment longtemps. Le tableau suivant donne les premières valeurs de la loi dans le cas $ L=2$, donc si on ne possède que deux euros au début. On constate que si l'on ne perd pas lors des $ 6$ premiers coups, la probabilité de perdre en $ k$ coups change très peu d'un $ k$ au suivant.

$ k$ $ 2$ $ 4$ $ 6$ $ 8$ $ 10$ $ 12$ $ 14$
$ \prob{\tau_2=k}$ $ \frac14$ $ \frac18$ $ \frac5{64}$ $ \frac7{128}$ $ \frac{21}{512}$ $ \frac{33}{1024}$ $ \frac{429}{16384}$
  $ =0.25$ $ =0.125$ $ \cong0.078$ $ \cong0.054$ $ \cong0.041$ $ \cong0.032$ $ \cong0.026$

next up previous contents
Next: Le processus ponctuel de Up: Introduction aux processus stochastiques Previous: Introduction aux processus stochastiques   Contents
berglund 2005-11-28