\newpage
 \dexer {\bf Le retour  à l'origine}\newline On considère une marche aléatoire sur $\ZZ$,
$$S_n = X_1 + \ldots X_n \; , \; S_{0}=0 $$
où les $X_{i}$ sont des Bernoulli indépendantes prenant la valeur
$1$ avec probabilité $p$ et la valeur $-1$ avec la probabilité
$1-p=q$.

On pose $p_0(n)=\Pro(S_n=0)$ et pour $n\geq 1$,
$f_0(n)=\Pro(S_1\neq 0,\;...,\; S_{n-1}\neq 0,\; S_n=0)$ la
probabilité que le \underbar{premier retour} en 0 se fasse après
$n$ pas.  On note les fonctions génératrices associées
$$P_0(s)=\sum_0^\infty p_0(n)s^n,\quad F_0(s)=\sum_{n=1}^\infty
f_0(n)s^n.$$ On va montrer le théorème suivant
\begin{thf}On a \newline
(a) $P_0(s)=1+P_0(s)F_0(s),$
\newline (b)$P_0(s)=(1-4pqs^2)^{-\frac 12},$
\newline (c) $F_0(s)=1-(1-4pqs^2)^\frac 12.$
\end{thf}

\quest 1) Soit $A=\{S_n=0\}$ et $B_k$ l'évènement que le premier
retour à l'origine se  fait \`a $k$ pas. Remarquer que
$$\Pro(A)=\sum_{k=1}^n \Pro(A|B_k)\Pro(B_k).$$

\quest 2) Montrer que $\Pro(A|B_k)=p_0(n-k).$

\quest 3) Déduire que \begin{equation}
\label{relationutilemarchealeatoire} p_0(n)=\sum_{k=1}^n
p_0(n-k)f_0(k)\end{equation}
 si $n\geq 1$ et obtenir (a).

\quest 4) Montrer par un simple argument combinatoire que
$p_0(n)=C^{\frac n2}_n(pq)^{\frac n2}$ si $n$ est pair, $=0$ sinon
et déduire (b) et (c).

\quest 5) Déduire des résultats précédents que :
\begin{itemize}
\item la probabilité de retour à l'origine est $1-|p-q|$.
(Commencer par définir  cette probabilité)

\item cette probabilité n'est égale à 1 que si $p=\frac 12$ et
alors le temps moyen de retour est infini. (Commencer par définir
le temps moyen de retour).

\end{itemize}
\fexer

\dsolution{}

\quest 1) C'est la règle des probabilités disjointes car les $B_k$
sont disjoints.

\quest 2)  On a
\begin{eqnarray*}
\Pro(A\cap B_k)&=&\Pro(S_n=0,\; S_k=0,\; S_{k-1}\neq 0,\; ...,\; S_1\neq 0)\\
&=&\Pro(X_{k+1}+\dots \;+X_n=0,\; S_k=0,\; S_{k-1}\neq 0,\;...,\; S_1\neq 0)\\
&=&\Pro(X_{k+1}+\dots\; +X_n=0)\Pro(B_k)=\Pro(S_{n-k}=0)\Pro(B_k)
\end{eqnarray*}
car les $X_i$ sont i.i.d. et les lois de $X_1+\dots +X_{n-k}$ et de
$X_{k+1}+\dots +X_n$ sont donc égales.  (On peut aussi utiliser
l'homogénéité temporelle)

\quest 3) La première relation découle de 1) et 2). La seconde
découle du fait que le calcul de la fonction génératrice
transforme une convolution de suites en produit. Plus précisément,
en utilisant la relation du 3) :
$$P_0(s)F_0(s)=\sum_1^\infty s^n[\sum_{k=1}^n
f_0(k)p_0(n-k)]=\sum_1^\infty s^np_0(n)=P_0(s)-1.$$

\quest 4) $S_n=0$ si et seulement si  la particule fait un nombre
égal à $\frac n2$ de pas vers la droite et un nombre égal vers la
gauche. Ceci peut se faire de $C_{n}^{\frac n2}$ manières et
chacune de ces marches a probabilité $(pq)^{\frac n2}.$ Si $n$ est
impair il est impossible que $S_n=0$ et donc $p_0(n)=0$.
 Pour  (b) : à vos développements en série ! La relation (c)
 découle de (a) et (b).

 \quest 5)  La probabilité de retour à l'origine est
 $\sum_{n=1}^\infty f_0(n)=F_0(1)=1-|p-q|$.   Le retour à
 l'origine n'est certain que si $F_0(1)=1$ et donc $p=\frac 12$.
 Le temps moyen de retour se définit comme l'espérance du temps de
 premier retour, soit $\esp T_0=\sum_{n=1}^\infty nf_0(n)=F'_0(1)=+\infty.$
 (La seconde égalité vient du théorème de convergence monotone).

\fsolution

\dexer {\bf Le temps de première visite en 1}\newline
 Soit $T_1$ le premier temps (éventuellement infini) pour
lequel la marche atteint 1. Soit $F_1$ la fonction génératrice de
$1_{\{T_1<+\infty\}}T_1$ et pour tout entier $n$ positif ou nul
$f_1(n)=\Pro(T_1=n)$.

\quest 1a) Montrer que $f_1(1)=p$ et que pour tout entier $n\geq
2$, on a la relation de r\'ecurrence
$f_1(n)=q\sum_{\nu=2}^{n-1}f_1(\nu -1)f_1(n-\nu)$

\quest 1b) En déduire que l'on a $F_1(s)=qsF_1(s)^2+ps,$ puis que
$F_1$ satisfait $F_1(s)=\cfrac{1-\sqrt{1-4pqs^{2}}}{2qs}$

\quest 2) En déduire la distribution de $T_1$ :\newline $\Pro
(T_1=2k)=0 \; , \; \Pro
(T_1=2k-1)=\cfrac{(-1)^{k-1}}{2q}C_{1/2}^k(4pq)^{k}.$ \fexer

 \dsolution{}
 1a) Le r\'esultat pour $n=1$ \'etant trivial, soit donc $n\geq 2$. On a :
\begin{eqnarray*}
&&\Pro(T_1=n)=\Pro(S_n =1, S_{n-1}\leq 0, \ldots, S_{1}\leq 0)=\\
&&\sum_{\nu =2}^{n-1}\Pro(X_1=-1,\; \inf\{j\geq 2,
-1+X_{2}+\ldots+X_{j}=0\}=
\nu, \; \inf\{k\geq \nu + 1, X_{\nu +1}+\ldots+X_{k}=1\}=n)=\\
&&q\sum_{\nu =2}^{n-1}\Pro(\inf\{j\geq 2;
-1+X_{2}+\ldots+X_{j}=0\}=
\nu)\Pro(\inf\{k\geq \nu + 1, X_{\nu +1}+\ldots+X_{k}=1\}=n)=\\
&&q\sum_{\nu =2}^{n-1}\Pro(\inf\{j\geq 1; X_{1}+\ldots+X_{j}=1\}=
\nu-1)\Pro(\inf\{k\geq 1, X_{1}+\ldots+X_{k}=1\}=n-\nu)=\\
&&q\sum_{\nu =2}^{n-1}f_1(\nu-1)f_1(n-\nu).\\
\end{eqnarray*}
La première égalité résulte du fait que l'on est en dimension $1$ et que la marche est plus
 proche voisin. Puisque $n\geq 2$, c'est que la marche est partie à gauche (sinon $T_1=1$) et puisque la marche est
plus proche voisin, la marche ne peut redevenir strictement positive sans passer par $1$.\\
La deuxième égalité repose sur l'observation suivante : puisque $n\geq 2$, la marche part à gauche,
 reste strictement négative jusqu'au temps $\nu -1$, redevient nulle à l'instant $\nu$
 (pour la première fois depuis l'instant $0$) et  au temps $n$ devient strictement positive égale à $1$ (et pour la première fois!).\\
La troisième et quatrième égalité sont de simples conséquences de l'indépendance et du
caractère équidistribué des $X_{k}$.\\

\medskip 1b) On a :
\begin{eqnarray*}
\sum_{n=1}^{\infty}f_1(n)s^n
&=& qs\sum_{n=2}^{\infty}\left(\sum_{j=1}^{n-1}f_1(j)f_1(n-1-j)\right)s^{n-1}+ps\\
&=&
qs\sum_{n=1}^{\infty}\left(\sum_{j=0}^{n}f_1(j)f_1(n-j)\right)s^{n}+ps
\end{eqnarray*}
soit
$$F_1(s)=qsF_1(s)^{2}+ps$$

On obtient donc une équation du second degré pour $F_1(s)$ et on a
:
$$F_1(s)=\cfrac{1 \pm \sqrt{1-4pq{s}^2}}{2qs}$$
et puisque $F_1(s)$ tend vers $0$ quand $s\rightarrow 0$, on a
donc :
$$F_1(s)=\cfrac{1-\sqrt{1-4pqs^2}}{2qs}.$$

\quest 2) En utilisant le développement en série entière de
$\sqrt{1-x}$, on obtient le résultat annoncé dans la question $2$.
Remarquer qu'il était évident que $\Pro(T_1=2k)=0$ (on doit faire
un nombre impair de pas  pour de $0$ aller en $1$).


\fsolution

\dexer {\bf Le temps de première visite en $r$}\newline
Soit $T_r$ le temps de première visite au point $r$. On pose
$f_r(n)=\Pro(S_1\neq r,\;...,\; S_{n-1}\neq r,\; S_n=r)$, c'est-à-dire la probabilité que la première visite se
produise au $n$-ième pas. On note sa fonction génératrice $F_r(s)=\sum_{n=1}^\infty f_r(n)s^n.$

\quest 1) Montrer que $f_r(n)=\sum_{k=1}^{n-1} f_{r-1}(n-k)f_1(k)$
si $r>1$.

 \quest 2) En déduire  que pour $r\geq 1$,
$$F_r(s)=[F_1(s)]^r.$$

 \quest 3) Montrer que la probabilité que la marche aléatoire
entre dans $\natural^*=\{1,\;2,\;...,\; n,\;...\}$ est
$$F_1(1)=\frac {1-|p-q|}{2q}=\min(1,\; \frac pq).$$
(Cette probabilité est la même que celle de passer par 1, qui  est
le vestibule de $\natural^*.$)

\quest 4) Démontrer, en considérant les probabilités
conditionnelles par rapport aux valeurs possibles de $X_1$, que
$f_0(n)=qf_1(n-1)+pf_{-1}(n-1)$ et que donc
$F_0(s)=qsF_1(s)+psF_{-1}(s).$

\quest 5) Montrer que $F_{-1}(s) =\frac{1-(1-4pqs^2)^\frac
12}{2ps}$. Pour cela, on appliquera une {\it méthode de réflexion}
: Soit $\omega$ une marche quelconque arrivant en $-1$ et
$\omega^*$ la marche symétrique par rapport à 0, qui arrive donc
en 1. Soit $\Pro_{p,q}(\pi)$ la probabilité de $\pi$. Alors
$\Pro_{p,q}(\pi)=\Pro_{q,p}(\pi^*)$.

\quest 6) En déduire à nouveau $F_0(s)$ : par le principe de
réflexion on peut donc déduire directement $F_0$ de $F_1$.


\fexer

\dsolution{}

\quest 1) On reprendra point par point  l'argument qui donnait la
relation (\ref{relationutilemarchealeatoire}).

\quest 2) On multiplie par $s^n$ la relation du 1) et on somme sur
$n$ pour obtenir $F_r(s)=F_{r-1}(s) F_1(s)=F_1(s)^r.$

\quest 4) L'argument suggéré conduit à  échanger les rôles de $p$
et $q$ dans la formule donnant $F_1$ pour obtenir $F_{-1}$.

\quest 5) Simple calcul.

 \fsolution

 \section{Le principe de réflexion et ses conséquences}
 {\it \cite{GS}, 3.10, pages 75 à 82}.\newline

Dans la suite, on pose $S_0=a$, $S_n =a+\sum_{i=1}^n X_i$ où $X_i$
sont
 des variables de Bernoulli i.i.d. de paramètre $p$ :
 $\Pro(X_1=1)=p$, $\Pro(X_1=-1)=1-p=q.$
 On représente une marche aléatoire  par la suite des couples
 temps-position, $\{(n,\;S_n), \; n\geq 0\}.$  On note $N_n(a,b)$ le
 nombre de chemins distincts allant de $(0,a) $ à $(n,b)$ et
 $N_n^0(a,b)$ le nombre de chemins allant de $(0,a)$ à $(n,b)$ et
 passant au moins une fois par 0 : de tels chemins contiennent
 $(k, 0)$ pour un $k$ tel que  $0\leq k\leq n$.

\dexer

\quest 1) Démontrer que
\begin{equation*}
\Pro(S_n=b)=
\begin{cases}
C_{n}^{\frac12(n+b-a)}p^{\frac 12(n+b-a)}q^{\frac 12(n-b+a)}\hbox{
si } \frac 12(n+b-a)\in \{0,\;1,\;...,\;n\}\\
0 \;\;\hbox{sinon}
\end{cases}
\end{equation*}


\quest 2) {\it Le principe de réflexion}. On  suppose que $S_0=a$ et $S_n=b$. Montrer que si $a,\; b>0$, alors
$N_n^0(a,b)=N_n(-a,b)$. On appliquera le principe de réflexion, qui consiste à associer à tout chemin de $(0, -a)$ à
$(n,\;b)$ passant pour la première fois en 0 à l'instant $k$ le chemin de $(0,\; a)$ à $(n, \; b)$ obtenu en changeant
en leur opposé tous les points avant $k$. (Faire un dessin où l'axe des $x$ représente le temps et l'axe des $y$ la
position $S_n$. La réflexion se fait par rapport à l'axe $Ox$.)

\quest 3) Montrer que pour tous $n\in \natural$, $a<b$, tels que
$0\leq \frac 12(n+b-a)\leq n,$ on a $N_n(a,b)=C_{n}^{\frac
12(n+b-a)},$ et $N_n(a,b)=0$ si cette condition sur $n, a, b$
n'est pas satisfaite.

\quest 4) Montrer le {\it théorème de scrutin} : Si $b>0$, alors
le nombre de chemins de $(0,0)$ à $(n,b)$ qui ne repassent pas par
0 est égal à $\frac bn N_n(0,b)$.


\quest 5) On prend $a=0$. Montrer que
$$\Pro(S_1S_2\dots S_n\neq 0,\; S_n=b)=\frac{|b|}n\Pro(S_n=b)$$

\quest 6) En déduire que $$\Pro(S_1S_2\dots S_n\neq 0)=\frac
1n\esp |S_n|.$$

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

\fexer

 \dsolution{}

\quest 1) Si $S_n=b$, et s'il y a eu $r$ pas vers la droite et $l$
pas vers la gauche, on a $a+r-l=b$ et $r+l=n$. On trouve $r=\frac
12(n+b-a)$ et $l=\frac 12(n-b+a).$  Le nombre de chemins distincts
est le nombre de manières de placer les $r$ pas vers la droite
parmi les $n$ pas, soit $C_n^r=C_n^{\frac 12(n+b-a)}.$  Tous les
chemins ont la même probabilité $p^rq^l$, d'où le résultat.

\quest 2) La réflexion définit une bijection entre les chemins de
$a$ à $b$ passant par 0 et les chemins de $-a$ à $b$. Leurs
nombres sont donc égaux.

\quest 3) Ce raisonnement a déja été fait au 1).

\quest 4) Comme tous les chemins ne repassant pas par 0 vont
d'abord en $(1,1)$, leur nombre est $N_{n-1}(1,b)-N_{n-1}^0(1,b)=$
$N_{n-1}(1,b)-N_{n-1}(-1,b),$ par le 2). Un calcul facile
utilisant 3) donne le résultat.


\quest 5) Prenons d'abord $b>0$. Le nombre de chemins dans
l'événement considéré est par le théorème de scrutin $\frac bn
N_n(0,b)$. et chaque chemin a $\frac 12(n+b)$ pas vers la  droite
et $\frac 12(n-b)$ pas vers la gauche.  Donc
$$\Pro(S_1S_2\dots S_n\neq 0,\; S_n=b)=\frac bn N_n(0,b)p^{\frac
12(n+b)}q^{\frac 12(n-b)}=\frac bn\Pro(S_n=b).$$ Un calcul du même
type traite le cas $b<0$.

\quest 6) Il suffit de sommer la relation du 5) sur toutes les
valeurs de b.

\quest 7)   Les formules du 5) et du 1) sont intéressantes pour le
problème de la fortune du joueur : elle permettent de calculer la
probabilité de fortune ($S_n=b$) sous la condition que le joueur
ne se ruine pas ($S_0...S_n\neq 0$).

 \fsolution

\dexer {\bf Interprétation du théorème de scrutin} Ce théorème
(``Ballot theorem") est parfois traduit improprement par "théorème
de ballotage". En fait, il s'agit plutôt du théorème de scrutin et
il concerne le dépouillement des votes. La question est de savoir
: supposons que le candidat $A$ a plus de votes que le candidat
$B$ : quelle est la probabilité que cette supériorité soit
vérifiée tout au long du dépouillement ?

\quest 1) Supposons que le candidat $A$ ait $\alpha$ votes et que
le candidat $B$ ait $\beta$ votes, avec $\alpha> \beta$.  Montrer
en utilisant le théorème de scrutin que la probabilité que le
candidat $A$ ait tout au long du dépouillement un score supérieur
à celui de $B$ est égale à $\frac {\alpha-\beta}{\alpha+\beta}.$

\quest 2) Interpréter.
 \fexer

\dsolution \quest 1) Le dépouillement se fait bulletin par
bulletin. On pose pour $i=1,\dots,\; \alpha+\beta$ $X_i=1$ si le
bulletin est pour $A$ et $-1$ s'il est pour $B$. On suppose les
$X_i$ i.i.d.  On a $S_0=0$ et $S_n$ représente l'avantage de $A$
sur $B$. Les chemins tels que $S_k$ soit toujours différent de 0
pour $k\geq 1$ sont en nombre $N_n^0(0,b)=\frac bn N_n(0,b)$, et
comme tous les chemins arrivant en $\alpha+\beta$ sont
équiprobables, la probabilité recherchée est la proportion de
chemins ne repassant pas par zéro, soit $\frac bn
=\frac{\alpha-\beta}{\alpha+\beta}.$

\quest 2)  Remarquons d'abord que le résultat ne dépend pas de la
connaissance de $p$, la probabilité de voter $A$. Dans les
démocraties, $\alpha$ est en général proche de $\beta$ ($1\%$ de
différence) et un ordre de grandeur de la probabilité précédente
est donc $p=\frac 1{100}.$ Il est donc très probable que le
dépouillement soit incertain. Toutefois, on peut se demander si
cette incertitude ne se produit pas, en fait, au début du
dépouillement, et s'il n'y a pas stabilisation du résultat bien
avant la fin du dépouillement. Peut-on utiliser directement la loi
des grands nombres, le théorème central limite ou des inégalités
de grande déviation pour démontrer une stabilisation des
proportions ? La réponse est ``non", car nous avons une
information a priori supplémentaire, à savoir $S_{\alpha
+\beta}=\alpha-\beta$ et par contre nous ignorons la probabilité
$p$ de vote pour $A$.


\fsolution


\dexer{\bf La méthode d'inversion du temps}

On va montrer :
\begin{thf}
La probabilité $f_b(n)$ qu'une marche aléatoire $S_n$ partant de 0
arrive en $b>0$ pour la première fois au temps $n$ vérifie
$$f_b(n)=\frac{|b|}n\Pro(S_n=b),\quad n\geq 1.$$
\end{thf}
Cette conclusion ressemble beaucoup à celle du théorème de scrutin
et s'en déduit grâce à la méthode d'inversion du temps. On associe
à la marche aléatoire
$$\{0, S_1,\; S_2,\;...,\; S_n\}=\{0,\; X_1,\;
X_1+X_2,\;...,\sum_1^nX_i\}$$ la marche aléatoire à rebours
$$\{0,\;T_1,\;T_2,...,\;T_n\}=\{0,\;X_n,\;X_n+X_{n-1},...,\;
\sum_1^n X_i\}.$$

\quest 1) Montrer que les deux marches ont la même loi (quelle que
soit la valeur de $p$).

\quest 2)  Montrer que la marche directe ne repasse pas par 0 et
vérifie $S_n=b$ si et seulement si la marche inverse vérifie
$T_n=b$ et que la première visite de $T_n$ en $b$ se produit au
temps $n$ (faire un dessin).  En déduire le théorème.


\fexer

\dsolution{}
 Le fait que les marches aient même loi est immédiat,
puisque les $X_i$ sont i.i.d.  On $S_n=b$ et $S_1S_2...S_n\neq 0$
si et seulement si $T_n=b$ et $T_n-T_{n-i}=X_1+...+X_i>0$ pour
tout $i\geq 1$, ce qui veut bien dire que la première visite de
$T_n$ en $b$ se fait au temps $n$.

\fsolution

\dexer Faire une synthèse des questions posées et des résultats
obtenus sur les marches aléatoires : que sait-on ? \fexer

%Lemme d'Abel (ou théorème radial d'Abel).  Soit $f$ développable
%en série entière de rayon  de convergence supérieur ou égal à 1.
%Si $f(t)=\sum_{n=0}^\infty a_n t^n$, et si $\sum_n
%a_n=l\in\real$, alors $\lim_{t\to  1^-}f(t) existe et vaut $l$.
