Un exemple de marche aléatoire
Yves Coudène, 1/9/04

Certains problèmes de la vie courante peuvent être modélisés par des marches aléatoires. On montre comment, par des raisonnements élémentaires, on peut étudier le comportement d’une de ces marches.

1 Le problème du collectionneur

Nicolas, 10 ans, se lance dans une collection de cartes Pokémon. Chaque carte représente un Pokémon, et il existe 150 Pokémons différents. Les cartes sont vendues dans des paquets scellés, si bien que lorsque Nicolas achète une carte, il peut tomber sur n’importe quel Pokémon ; en particulier sur un Pokémon qu’il possède déjà.
En supposant qu’à chaque achat, on ait même probabilité d’obtenir chacun des 150 Pokémons, quel est le nombre moyen de cartes que Nicolas doit acheter afin d’obtenir tous les Pokémons ?

Un raisonnement simple permet d’obtenir la réponse. Traitons le cas général où le nombre total de Pokémons est quelconque, égal à n. Notons tk le nombre moyen de cartes à se procurer pour terminer la collection, sachant que l’on est déjà en possession de k Pokémons distincts.

Supposons que nous avons k Pokémons, tous différents, et achetons une carte supplémentaire. Avec probabilité pk = kn, cette carte était déjà en notre possession ; il faut donc encore acheter en moyenne tk cartes pour terminer la collection. Avec probabilité 1 pk, c’est une nouvelle carte ; il faut donc acheter en moyenne tk+1 cartes supplémentaires. Par conséquent :

tk = pktk + (1 pk)tk+1 + 1

Ce qui donne : tk = tk+1 + 1 (1 pk)  , soit tk = tn + l=kn1 n n l.
Le nombre de cartes nécessaires pour terminer la collection, sachant que l’on possède déjà n Pokémons distincts, est égal à zéro : tn = 0. Le nombre moyen total de cartes à se procurer pour posséder l’ensemble des n Pokémons est égal à t0, avec

t0 = n j=1n1 j

Une comparaison série-intégrale, appliquée à la fonction 1x, donne l’encadrement ln(n) < j=1n1j < ln(n) + 1. La différence 1j ln(n) est décroissante ; elle converge donc vers une certaine constante γ, appelée constante d’Euler. Si bien que le nombre recherché est de l’ordre de n(ln(n) + γ). En première approximation, on peut prendre γ = 0.577. Pour n = 150, on obtient t0 838. Nicolas peut espérer terminer sa collection après avoir acheté 838 cartes.

2 Interprétation en terme de marche aléatoire

Cherchons à formaliser les raisonnements précédents. Pour cela, il faut se donner un univers, composé des résultats qui peuvent être obtenus à l’issue de l’épreuve, d’une probabilité sur cet ensemble, et d’une variable aléatoire qui représente la quantité à étudier.

L’univers Ω

Dans chacun des deux exemples, on peut modéliser la situation par une suite de nombres X0,X1... compris entre 0 et n. Dans le premier exemple, le terme de rang i de la suite, noté Xi, correspond au nombre de Pokémons différents en possession de Nicolas, après l’achat de i cartes.

L’univers Ω de tous les résultats possibles correspond donc à l’ensemble des suites indexées par les entiers, à valeurs dans {0..n}.

Ω = {0..n}N

La variable aléatoire Xi : Ω R est donnée par la projection sur la ieme coordonnée.

La probabilité P

Cherchons à définir sur Ω une probabilité P rendant compte du phénomène étudié. Rappelons que le cylindre [X0 = k0,X1 = k1,..Xl = kl] est le sous-ensemble de Ω composé des suites qui débutent par k0,..kl. Pour définir une probabilité P sur Ω, il suffit de spécifier sa valeur sur les cylindres [X0 = k0,X1 = k1,..Xl = kl], et ce pour tout l et tout l-uplet k0,..kl.
Nous allons définir la probabilité P par une récurrence sur la taille des cylindres. Pour cela, rappelons la notion de probabilité conditionnelle. Soit A, B deux sous-ensembles de Ω, et P une probabilité sur Ω. La probabilité de A sachant B est donnée par

P(AB) = P(A B) P(B) .

Prenons pour A l’événement (Xi+1 = ki+1) et pour B l’événement [X0 = k0,X1 = k1,..Xi = ki]. L’intersection de A et de B correspond à l’événement [X0 = k0,X1 = k1,..Xi+1 = ki+1], si bien qu’il suffit de spécifier les valeurs P(Xi+1 = ki+1X0 = k0,X1 = k1,..Xi+1 = ki+1) pour déterminer P.

Dans nos exemples, la valeur prise par Xi+1 ne dépend pas des valeurs prises par X0...Xi1, mais juste de la valeur prise par Xi (C’est la propriété de Markov). En effet, si la valeur de Xi est connue, disons égale à k, la variable aléatoire Xi+1 ne peut prendre que les deux valeurs k et k + 1, et les probabilités associées à ces deux valeurs sont complètement déterminées.

P(Xi+1 = lXi = k)=pk si l=k =1 pksi l=k+1 =0 sinon

avec pk = kn.

PICT

Nous décidons donc de munir Ω de la probabilité P définie par les relations précédentes, car nous pensons qu’elle correspond aux situations que nous sommes en train d’étudier.
Remarquons que la probabilité P n’est pas entièrement déterminée par les relations données plus haut ; les quantités P(X0 = k0) n’ont pas été spécifiées. Elles n’interviendront pas dans la suite.

La variable aléatoire T

On s’intéresse au temps T nécessaire pour atteindre la valeur n. Cette quantité est une variable aléatoire définie sur Ω qui peut s’exprimer en fonction des Xi.

T = Card{i NXi < n} = i=01 {Xi<n}.

Rappelons maintenant comment est défini le concept d’espérance conditionnelle. Soit T une variable aléatoire définie sur Ω, prenant des valeurs entières, et soit A un sous-ensemble de Ω. L’espérance conditionnelle de T sachant A est donnée par une des deux expressions équivalentes suivantes.

E(TA) = E(T1A) P(A) = i=0iP(T = iA).

La quantité que nous cherchons à calculer correspond au temps moyen nécessaire pour atteindre la valeur n, sachant que nous sommes parti de la valeur 0. Il s’agit donc de l’espérance de T, sachant que X0 = 0 :

t0 = E(TX0 = 0)

3 Calcul des tk

On peut maintenant définir précisément les quantités tk et dériver la relation de récurrence qui permet de les calculer. Les quantités tk correspondent au temps moyen nécessaire pour atteindre la valeur n, sachant qu’on part de la valeur k. On a donc :

tk = E(TX0 = k)

Le résultat suivant se déduit aisément de la définition de l’espérance conditionnelle.

Théorème
Soit T une variable aléatoire définie sur Ω, A un sous-ensemble de Ω. Soit B0,...Bn une partition de Ω : les Bi sont des sous-ensembles de Ω disjoints deux à deux, et l’union de tous ces sous-ensembles est égale à Ω. On a alors la relation suivante :

E(TA) = lE(TBl A)P(BlA).

Soit k un entier strictement inférieur à n. Considérons l’événement A = (X0 = k) et les événements Bl = (X1 = l). Posons T = i11{Xi<n}, si bien que T = 1{X0<n} + T. La relation précédente devient :

E(TX0 = k)= lE(TX1 = l,X0 = k)P(X1 = lX0 = k) = lE(1{X0<n} + TX1 = l,X0 = k)P(X1 = lX0 = k) = lE(TX1 = l,X0 = k)P(X1 = lX0 = k) + 1

La quantité T ne dépend que des variables X1,X2... mais pas de la variable X0. Par conséquent, on a l’égalité E(TX1 = l,X0 = k) = E(TX1 = l), ce qui donne :

E(TX0 = k) = lE(TX 1 = l)P(X1 = lX0 = k) + 1

La quantité E(TX1 = l) correspond au temps moyen nécessaire pour atteindre n, sachant qu’on est parti de l. Elle est donc égale à tl (Il s’agit du caractère stationnaire de la marche aléatoire). L’équation précédente devient :

tk = pktk + (1 pk)tk+1 + 1

C’est la relation attendue.