La ruine relue avec des matrices

Le DM3 a étudié la ruine du joueur avec les suites : la relation $r_k = p\,r_{k+1} + q\,r_{k-1}$, valable pour tout $k \in \llbracket 1\,;N-1 \rrbracket$, puis les différences, puis la formule close. Cette page refait le chemin avec un objet que vous n’avez pas encore rencontré en classe, la matrice, et qui est l’outil roi du programme de maths expertes. Aucun prérequis : tout est défini en passant.

Photographier le hasard

Reprenons le jeu du DM : $N$ jetons en tout, Alice en possède $k$, elle en gagne un avec la probabilité $p$ et en perd un avec la probabilité $q = 1 - p$ ; la partie s’arrête en $0$ ou en $N$. Le point crucial, déjà présent dans le résultat R1 du DM, est que le jeu n’a pas de mémoire : ce qui peut arriver après le coup numéro $n$ ne dépend que de la fortune d’Alice à cet instant, pas du chemin qui l’y a menée.

Une partie en cours est donc entièrement décrite par une liste de $N+1$ nombres : la probabilité que la fortune vaille $0$, celle qu’elle vaille $1$, et ainsi de suite jusqu’à $N$. Toute la question devient : comment cette liste évolue-t-elle d’un coup au suivant ?

Le petit cas, et le tableau

Prenons $N = 4$ et $p = \frac{1}{2}$. Les fortunes possibles sont $0$, $1$, $2$, $3$, $4$. Depuis une fortune $k$ comprise entre $1$ et $3$, un coup envoie Alice en $k+1$ avec la probabilité $\frac{1}{2}$ et en $k-1$ avec la probabilité $\frac{1}{2}$ ; depuis $0$ ou $4$, la partie est finie, la fortune ne bouge plus. Rangeons ces informations dans un tableau $T$ à cinq lignes et cinq colonnes : à la ligne $k$ et à la colonne $j$, on écrit la probabilité de passer de la fortune $k$ à la fortune $j$ en un coup.

$$T = \begin{pmatrix} 1 & 0 & 0 & 0 & 0\\[2pt] \tfrac{1}{2} & 0 & \tfrac{1}{2} & 0 & 0\\[2pt] 0 & \tfrac{1}{2} & 0 & \tfrac{1}{2} & 0\\[2pt] 0 & 0 & \tfrac{1}{2} & 0 & \tfrac{1}{2}\\[2pt] 0 & 0 & 0 & 0 & 1 \end{pmatrix}$$

Les lignes et les colonnes sont numérotées de $0$ à $4$. Chaque ligne a pour somme $1$ : depuis n’importe quelle fortune, il se passe forcément quelque chose. Les deux lignes extrêmes, avec leur $1$ sur la diagonale, disent que $0$ et $4$ sont des états absorbants : on y entre, on n’en sort plus. Un tel tableau s’appelle une matrice de transition, et l’évolution aléatoire qu’il code, cette marche sans mémoire de fortune en fortune, s’appelle une chaîne de Markov, du nom du mathématicien russe qui a étudié ces processus au début du XXe siècle.

Deux coups, et le produit

Quelle est la probabilité de passer de la fortune $i$ à la fortune $j$ en deux coups ? Il faut passer par une fortune intermédiaire $l$, et les possibilités s’excluent mutuellement : c’est un arbre à deux étages, exactement comme en Q2 du DM. En sommant sur toutes les fortunes intermédiaires :

$$\forall (i\,;j) \in \llbracket 0\,;4 \rrbracket^2, \qquad \mathbb{P}(\text{de } i \text{ à } j \text{ en deux coups}) = \sum_{l=0}^{4} T_{i,l}\, T_{l,j},$$

où $T_{i,l}$ désigne le coefficient de la ligne $i$ et de la colonne $l$. Cette formule, « multiplier le long de chaque chemin, additionner les chemins », est prise comme définition du produit de deux matrices : le coefficient $(i\,;j)$ du produit $AB$ est $\sum_{l} A_{i,l} B_{l,j}$, la ligne $i$ de $A$ contre la colonne $j$ de $B$. Le produit matriciel n’est donc pas une convention arbitraire : c’est la formule des probabilités totales rangée en tableau. Calculons $T^2 = T \times T$ :

$$T^2 = \begin{pmatrix} 1 & 0 & 0 & 0 & 0\\[2pt] \tfrac{1}{2} & \tfrac{1}{4} & 0 & \tfrac{1}{4} & 0\\[2pt] \tfrac{1}{4} & 0 & \tfrac{1}{2} & 0 & \tfrac{1}{4}\\[2pt] 0 & \tfrac{1}{4} & 0 & \tfrac{1}{4} & \tfrac{1}{2}\\[2pt] 0 & 0 & 0 & 0 & 1 \end{pmatrix}$$

Vérifiez un coefficient à la main : depuis la fortune $2$, être ruiné en deux coups exige de perdre deux fois, probabilité $\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$, et c’est bien le coefficient $(2\,;0)$.

En itérant le même argument (conditionner sur la fortune après $n$ coups, c’est une récurrence sur $n$) :

$$\forall n \in \mathbb{N}^*,\ \forall (k\,;j) \in \llbracket 0\,;4 \rrbracket^2, \qquad \text{le coefficient } (k\,;j) \text{ de } T^n = \mathbb{P}(\text{de } k \text{ à } j \text{ en } n \text{ coups}).$$

Élever $T$ à la puissance $n$, c’est jouer $n$ coups d’un seul geste.

Faire tourner, et regarder la colonne 0

Le coefficient $(k\,;0)$ de $T^n$ est la probabilité qu’Alice, partie de $k$ jetons, soit ruinée en au plus $n$ coups : l’état $0$ étant absorbant, y être après $n$ coups, c’est y être tombé une fois au moins. Or le résultat R1 du DM définit précisément $r_k$ comme la limite de cette probabilité quand $n$ tend vers $+\infty$. La colonne $0$ des puissances de $T$ doit donc converger vers les $r_k$, dont le DM (question Q4.b, avec $N = 4$) donne la valeur : pour tout $k \in \llbracket 0\,;4 \rrbracket$, $r_k = 1 - \frac{k}{4}$, soit $1$, $0{,}75$, $0{,}5$, $0{,}25$, $0$. Le script suivant fait le calcul, sans autre outil que la règle ligne par colonne :

T = [[1.0, 0.0, 0.0, 0.0, 0.0],
     [0.5, 0.0, 0.5, 0.0, 0.0],
     [0.0, 0.5, 0.0, 0.5, 0.0],
     [0.0, 0.0, 0.5, 0.0, 0.5],
     [0.0, 0.0, 0.0, 0.0, 1.0]]

def produit(A, B):
    """Produit de deux matrices carrees (regle ligne par colonne)."""
    n = len(A)
    C = [[0.0] * n for i in range(n)]
    for i in range(n):
        for j in range(n):
            for l in range(n):
                C[i][j] = C[i][j] + A[i][l] * B[l][j]
    return C

def puissance(M, n):
    """M multipliee n - 1 fois par elle-meme."""
    R = M
    for i in range(n - 1):
        R = produit(R, M)
    return R

for n in (1, 2, 4, 16, 64):
    M = puissance(T, n)
    colonne = [round(M[k][0], 6) for k in range(5)]
    print("n =", n, ":", colonne)

Sortie :

n = 1 : [1.0, 0.5, 0.0, 0.0, 0.0]
n = 2 : [1.0, 0.5, 0.25, 0.0, 0.0]
n = 4 : [1.0, 0.625, 0.375, 0.125, 0.0]
n = 16 : [1.0, 0.748047, 0.498047, 0.248047, 0.0]
n = 64 : [1.0, 0.75, 0.5, 0.25, 0.0]

À $n = 64$, la colonne $0$ affiche $1$, $0{,}75$, $0{,}5$, $0{,}25$, $0$ à six décimales près : la formule close du DM, retrouvée par la seule mécanique des puissances. La colonne $4$ converge symétriquement vers les probabilités de victoire $g_k = \frac{k}{4}$ de Q6, et les colonnes centrales fondent vers $0$ : la probabilité que la partie dure encore s’évanouit, ce qui rend visible, numériquement, l’affirmation admise dans R1 selon laquelle la partie s’arrête avec probabilité $1$.

La récurrence du DM en une ligne

Le lien avec le chapitre est plus qu’une coïncidence numérique. Rangez les probabilités de ruine dans une colonne $r = (r_0, r_1, r_2, r_3, r_4)$ et appliquez-lui $T$ : la ligne $k$ du produit $Tr$ vaut $\frac{1}{2} r_{k-1} + \frac{1}{2} r_{k+1}$ pour $k$ entre $1$ et $3$, et $r_0$ ou $r_4$ aux bords. La relation de conditionnement au premier coup de R1 s’écrit donc en une ligne :

$$T\,r = r.$$

La colonne des $r_k$ est un vecteur fixe de la matrice : appliquer un coup de jeu ne la change pas. Et comme en Q19 du DM, cette équation jointe aux conditions $r_0 = 1$ et $r_4 = 0$ détermine $r$ entièrement : la différence de deux solutions vérifie la récurrence homogène avec des bords nuls, donc est nulle. Tout le travail des parties I et II du DM peut se relire ainsi : résoudre $T r = r$, à bords imposés, pour une matrice de taille $N + 1$.

En maths expertes, ces objets ont un chapitre entier : produit et puissances de matrices, graphes et marches aléatoires, vecteurs fixes et comportement limite. Vous y retrouverez la ruine du joueur en exercice d’application, et vous saurez d’où elle vient. Une dernière perspective pour mesurer le chemin : de Moivre a établi la formule close de Q8 vers 1712, alors que le calcul matriciel ne naîtra qu’au XIXe siècle. Il a donc fait, avec les seules suites, ce que la matrice $T$ raconte aujourd’hui en cinq lignes de Python.

Sources

• DM3 du chapitre A1 : le résultat R1 (conditionnement au premier coup), les questions Q4, Q6, Q8 et l’argument d’unicité de Q19, que cette page traduit en langage matriciel.
• Le script ci-dessus, exécuté tel quel ; les valeurs limites sont celles de la formule $r_k = 1 - \frac{k}{4}$ démontrée dans le DM.
• Programme de l’option maths expertes : matrices, graphes et marches aléatoires (chapitres M du catalogue).