2.1 Marche aléatoire simple sur la droite
25
Démonstration. Sachant {X 0 = 0}, l’événement {τ = 2n + 2} correspond à
une trajectoire de longueur 2n + 2 partant de 0 et revenant à zéro en restant
strictement positive ou strictement négative. Ces deux cas sont équiprobables,
d’où le facteur 2 dans le résultat. Dans les deux cas, il y a eu forcément n + 1
incréments +1 et n + 1 incréments −1, d’où
P 0 (τ = 2n + 2) = 2C n p
n+1 (1 − p)
n+1 .
où C n est le nombre de chemins de longueur 2n+2 partant de zéro et revenant
à zéro, et restant strictement positifs. Le premier incrément est forcément +1
et le dernier forcément −1 et C n est égal au nombre de chemins de longueur
2n partant de zéro et revenant à zéro et restant positifs. Il y a n incréments
+1 et n incréments −1. Considérons les chemins partant de zéro et revenant
à zéro et contenant n incréments +1 et n incréments −1. Il y en a
2n
n
. Si
un chemin de ce type n’est pas positif alors juste après la première position
négative, modifions tous les incréments en permutant le signe des +1 et des
−1. Un exemple d’illustration est donné dans la figure 2.2. On obtient de
la sorte un chemin avec n − 1 incréments +1 et n + 1 incréments −1, et il
s’avère que tous les chemins partant de zéro avec n − 1 incréments +1 et n + 1
incréments −1 s’obtiennent de la sorte, et il y en a
2n
n−1
. Cette bijection
donne donc C n =
2n
n
−
2n
n−1
=
1
n+1
2n
n
(formule de Désiré André).
Théorème 2.6 (du scrutin
2 ). Si n = a + b et k = a − b avec 0 b a alors
P(S 1 > 0, . . . , S n > 0 | S 0 = 0, S n = k) =
k
n
=
a − b
a + b
.
Le théorème 2.6 indique que lors d’une élection avec deux candidats A et
B et n votants, dans laquelle A obtient a votes et B obtient b a votes, la
probabilité que A soit devant B tout le long du dépouillement des n bulletins
de vote est (a − b)/(a + b).
Démonstration. Notons tout d’abord que 0 k n et (n+k, n−k) = 2(a, b).
Soit P n,k l’ensemble des chemins de la marche aléatoire simple, de longueur n,
partant de (0, 0) et finissant en (n, k). Tous ces chemins possèdent exactement
a incréments +1 et b incréments −1. Ils sont donc au nombre de
a+b
a
. Soit
P
+
n,k l’ensemble de ces chemins strictement positifs aux temps 1, . . . , n. On a
P(S 1 > 0, . . . , S n > 0 | S 0 = 0, S n = k) = card(P
+
n,k )
p
a (1 − p)
b
P(S n = k | S 0 = 0)
.
D’un autre côté P(S n = k | S 0 = 0) = card(P n,k ) p
a (1 − p)
b et donc
P(S 1 > 0, . . . , S n > 0 | S 0 = 0, S n = k) =
card(P
+
n,k )
card(P n,k )
.
2. «Ballot theorem» en anglais.
25
Démonstration. Sachant {X 0 = 0}, l’événement {τ = 2n + 2} correspond à
une trajectoire de longueur 2n + 2 partant de 0 et revenant à zéro en restant
strictement positive ou strictement négative. Ces deux cas sont équiprobables,
d’où le facteur 2 dans le résultat. Dans les deux cas, il y a eu forcément n + 1
incréments +1 et n + 1 incréments −1, d’où
P 0 (τ = 2n + 2) = 2C n p
n+1 (1 − p)
n+1 .
où C n est le nombre de chemins de longueur 2n+2 partant de zéro et revenant
à zéro, et restant strictement positifs. Le premier incrément est forcément +1
et le dernier forcément −1 et C n est égal au nombre de chemins de longueur
2n partant de zéro et revenant à zéro et restant positifs. Il y a n incréments
+1 et n incréments −1. Considérons les chemins partant de zéro et revenant
à zéro et contenant n incréments +1 et n incréments −1. Il y en a
2n
n
. Si
un chemin de ce type n’est pas positif alors juste après la première position
négative, modifions tous les incréments en permutant le signe des +1 et des
−1. Un exemple d’illustration est donné dans la figure 2.2. On obtient de
la sorte un chemin avec n − 1 incréments +1 et n + 1 incréments −1, et il
s’avère que tous les chemins partant de zéro avec n − 1 incréments +1 et n + 1
incréments −1 s’obtiennent de la sorte, et il y en a
2n
n−1
. Cette bijection
donne donc C n =
2n
n
−
2n
n−1
=
1
n+1
2n
n
(formule de Désiré André).
Théorème 2.6 (du scrutin
2 ). Si n = a + b et k = a − b avec 0 b a alors
P(S 1 > 0, . . . , S n > 0 | S 0 = 0, S n = k) =
k
n
=
a − b
a + b
.
Le théorème 2.6 indique que lors d’une élection avec deux candidats A et
B et n votants, dans laquelle A obtient a votes et B obtient b a votes, la
probabilité que A soit devant B tout le long du dépouillement des n bulletins
de vote est (a − b)/(a + b).
Démonstration. Notons tout d’abord que 0 k n et (n+k, n−k) = 2(a, b).
Soit P n,k l’ensemble des chemins de la marche aléatoire simple, de longueur n,
partant de (0, 0) et finissant en (n, k). Tous ces chemins possèdent exactement
a incréments +1 et b incréments −1. Ils sont donc au nombre de
a+b
a
. Soit
P
+
n,k l’ensemble de ces chemins strictement positifs aux temps 1, . . . , n. On a
P(S 1 > 0, . . . , S n > 0 | S 0 = 0, S n = k) = card(P
+
n,k )
p
a (1 − p)
b
P(S n = k | S 0 = 0)
.
D’un autre côté P(S n = k | S 0 = 0) = card(P n,k ) p
a (1 − p)
b et donc
P(S 1 > 0, . . . , S n > 0 | S 0 = 0, S n = k) =
card(P
+
n,k )
card(P n,k )
.
2. «Ballot theorem» en anglais.