Calculez des probabilités d'absorption

Vous jouez à pile ou face contre un ami, un euro par lancer. Vous avez 3 €, lui 2 €, et la partie s’arrête quand l’un de vous deux est ruiné. Quelle est votre probabilité de gagner ? Combien de lancers faudra-t-il en moyenne ? La partie finira forcément (les états « ruiné » sont absorbants), mais où et quand ?

Au chapitre 2, vous avez appris à repérer les classes transitoires et les classes fermées. Ici, vous allez calculer ce qui se passe entre les deux : la probabilité d’être absorbé par chaque classe fermée, et le temps moyen pour y arriver. Nous suivrons la ruine du joueur, un exemple classique du cours, puis nous reviendrons au visiteur du site de presse.

Le fil rouge : la ruine du joueur

Notons $X_n$ votre fortune après $n$ lancers et $K$ la fortune totale en jeu (ici $K = 5$). À chaque lancer, vous gagnez un euro avec probabilité $p$ et en perdez un avec probabilité $q = 1 - p$. Les états sont $0, 1, \dots, K$ :

• depuis $i \in \lbrace 1, \dots, K-1 \rbrace$ : $p_{i,i+1} = p$ et $p_{i,i-1} = q$ ;
• $0$ (vous êtes ruiné) et $K$ (votre ami est ruiné) sont absorbants : $p_{00} = p_{KK} = 1$.

      q        q        q        q
  0 ◄──── 1 ◄───► 2 ◄───► 3 ◄───► 4 ────► 5
             p        p        p        p

  (0 et 5 bouclent sur eux-mêmes avec probabilité 1)

Les états 1 à 4 forment une classe ouverte, donc transitoire ; $\lbrace 0 \rbrace$ et $\lbrace 5 \rbrace$ sont deux classes fermées. La chaîne sera absorbée en 0 ou en 5 avec probabilité 1. Reste à savoir avec quelle probabilité chacun.

Huit parties simulées avec une pièce équilibrée, toutes parties de 3 €. Chacune erre dans les états transitoires 1 à 4 puis se fige dans un état absorbant : ruine (0 €) ou victoire (5 €).

Conditionner sur le premier pas

L’idée clé du chapitre tient en une phrase : pour calculer une grandeur depuis l’état $i$, regardez où va la chaîne au premier pas, puis utilisez la propriété de Markov.

Notons $h_i$ la probabilité de finir en $K$ (vous gagnez) en partant de $i$. Depuis $i$, au premier lancer, on va en $i+1$ avec probabilité $p$, en $i - 1$ avec probabilité $q$, et ensuite tout recommence depuis ce nouvel état. D’où le système :

$$h_0 = 0, \qquad h_K = 1, \qquad h_i = p\, h_{i+1} + q\, h_{i-1} \quad (0 < i < K).$$

Plus généralement, pour une chaîne quelconque et un ensemble d’états cible $C$, la probabilité $h_i$ d’atteindre $C$ depuis $i$ vérifie

$$h_i = 1 \text{ si } i \in C, \qquad h_i = \sum_{j} p_{ij}\, h_j \text{ sinon},$$

avec $h_i = 0$ pour les états d’où $C$ est inaccessible (les autres classes fermées). C’est exactement ce que vous avez fait au chapitre 2 pour calculer une probabilité de retour.

Exemple

Avec une pièce équilibrée ($p = q = \tfrac12$), l’équation s’écrit $h_i = \tfrac12 (h_{i+1} + h_{i-1})$ : chaque $h_i$ est la moyenne de ses voisins. Les $h_i$ sont donc alignés, et avec $h_0 = 0$ et $h_5 = 1$, on obtient $h_i = i/5$.

Avec 3 € sur 5 en jeu, vous gagnez avec probabilité $3/5 = 0{,}6$. Le jeu est équitable, et votre chance de gagner est simplement proportionnelle à votre mise de départ.

On calcule de la même façon le temps moyen d’absorption $k_i$, c’est-à-dire le nombre moyen de pas avant d’atteindre un état absorbant. Le premier pas coûte 1, puis tout recommence :

$$k_i = 0 \text{ si } i \text{ est absorbant}, \qquad k_i = 1 + \sum_j p_{ij}\, k_j \text{ sinon}.$$

Pour la ruine du joueur équitable, la solution est $k_i = i\,(K - i)$. Partant de 3 € sur 5, la partie dure en moyenne $3 \times 2 = 6$ lancers.

Jeu équitable : la probabilité de gagner croît en ligne droite (chaque h_i est la moyenne de ses voisins), la durée moyenne est une parabole, maximale au milieu. Depuis 3 € (cercle orange) : 0,6 et 6 lancers.

À retenir

Pour une probabilité d’absorption ou un temps moyen, conditionnez sur le premier pas : $h_i = \sum_j p_{ij} h_j$ et $k_i = 1 + \sum_j p_{ij} k_j$ pour les états transitoires, avec les bonnes conditions aux bords (1 ou 0 pour $h$, 0 pour $k$). On obtient un système linéaire.

La forme matricielle : la matrice fondamentale

Pour une grande chaîne, on écrit ces systèmes sous forme matricielle. On range les états transitoires en premier, les états absorbants ensuite. La matrice de transition prend alors la forme canonique :

$$P = \begin{pmatrix} Q & R \\ 0 & I \end{pmatrix}$$

• $Q$ contient les transitions entre états transitoires ;
• $R$ contient les transitions des états transitoires vers les états absorbants ;
• $0$ et $I$ traduisent le fait qu’un état absorbant ne mène qu’à lui-même.

On définit alors la matrice fondamentale

$$N = (I - Q)^{-1} = I + Q + Q^2 + Q^3 + \cdots$$

Son coefficient $N_{ij}$ est le nombre moyen de passages par l’état transitoire $j$ quand on part de $i$ : chaque terme $Q^n$ compte la probabilité d’être en $j$ au pas $n$, et la somme compte les passages. On en déduit tout le reste :

• temps moyens d’absorption : $k = N\,\mathbf{1}$, où $\mathbf{1}$ est le vecteur colonne de 1 (on somme les passages dans tous les états transitoires) ;
• probabilités d’absorption : $B = N\,R$, où $B_{ia}$ est la probabilité d’être absorbé en $a$ en partant de $i$ (on passe un certain nombre de fois par chaque état transitoire, puis on sort vers $a$).

Exemple

Pour la ruine du joueur équitable avec $K = 5$, les états transitoires sont 1, 2, 3, 4 et on obtient

$$N = \frac{1}{5}\begin{pmatrix} 8 & 6 & 4 & 2 \\ 6 & 12 & 8 & 4 \\ 4 & 8 & 12 & 6 \\ 2 & 4 & 6 & 8 \end{pmatrix}, \qquad k = N\mathbf 1 = \begin{pmatrix} 4 \\ 6 \\ 6 \\ 4 \end{pmatrix}, \qquad B = NR = \frac15\begin{pmatrix} 4 & 1 \\ 3 & 2 \\ 2 & 3 \\ 1 & 4 \end{pmatrix}.$$

La troisième ligne concerne votre fortune de 3 € : en moyenne, vous aurez exactement 3 € pendant $12/5 = 2{,}4$ lancers (le lancer initial compris), la partie dure 6 lancers, et vous finissez ruiné avec probabilité $2/5$ ou gagnant avec probabilité $3/5$. Nous retrouvons les résultats précédents.

Chaque ligne de N répartit la durée de la partie entre les états visités : depuis 3 €, on passe en moyenne 0,8 + 1,6 + 2,4 + 1,2 = 6 lancers, c'est la somme qui donne k. La diagonale, plus foncée, rappelle qu'on repasse souvent par son point de départ.

Et si la pièce est défavorable ? Avec $p = 0{,}4$, le calcul matriciel donne une probabilité de gagner de 0,360 seulement depuis 3 €, pour une durée moyenne d’environ 6,0 lancers. Un faible désavantage à chaque lancer se transforme en un net désavantage sur la partie. L’exercice 3 pousse ce constat jusqu’au casino.

Une pièce à peine défavorable creuse toute la courbe : depuis 3 €, la probabilité de gagner tombe de 0,6 à 0,360, alors que le désavantage n'est que de 0,2 € par lancer.

Retour au site : qui s’abonne ?

Au chapitre 2, nous avions établi que tout visiteur finit abonné ou parti. Calculons maintenant les probabilités. La classe fermée « Abonné, Vidéo » se traite comme un seul état absorbant (une fois entré, on n’en sort plus), de même que Départ. Avec les états transitoires dans l’ordre Accueil, Recherche, Article :

$$Q = \begin{pmatrix} 0 & 0{,}3 & 0{,}4 \\ 0{,}3 & 0 & 0{,}7 \\ 0{,}3 & 0 & 0{,}2 \end{pmatrix}, \qquad R = \begin{pmatrix} 0 & 0{,}3 \\ 0 & 0 \\ 0{,}1 & 0{,}4 \end{pmatrix}$$

(la première colonne de $R$ mène à l’abonnement, la seconde au départ). Le calcul donne :

Point d’entrée	Probabilité de s’abonner	Probabilité de partir	Clics moyens avant absorption
Accueil	0,112	0,888	3,03
Recherche	0,150	0,850	3,58
Article	0,167	0,833	2,39

Un visiteur qui arrive directement sur un article (depuis un moteur de recherche, par exemple) s’abonne plus souvent que celui qui arrive par l’accueil. Et le coefficient $N_{\text{Article},\text{Article}} \approx 1{,}67$ est bien le nombre moyen de pages « Article » calculé à l’exercice 3 du chapitre 2.

Quelle que soit la porte d'entrée, la grande majorité des visiteurs part ; mais ceux qui arrivent par un article s'abonnent environ une fois et demie plus souvent que ceux qui arrivent par l'accueil.

import numpy as np

# États transitoires : Accueil, Recherche, Article ; absorbants : Abonné, Départ
Q = np.array([[0.0, 0.3, 0.4],
              [0.3, 0.0, 0.7],
              [0.3, 0.0, 0.2]])
R = np.array([[0.0, 0.3],
              [0.0, 0.0],
              [0.1, 0.4]])

N = np.linalg.inv(np.eye(3) - Q)    # matrice fondamentale
k = N @ np.ones(3)                  # clics moyens avant absorption
B = N @ R                           # probabilités d'absorption
print(np.round(k, 2))               # [3.03 3.58 2.39]
print(np.round(B, 3))               # ligne Accueil : [0.112 0.888]
assert np.allclose(B.sum(axis=1), 1)

Attention

Inverser $I - Q$ n’est possible que parce que tous les états de $Q$ sont transitoires : alors $Q^n \to 0$ et la série $I + Q + Q^2 + \cdots$ converge. Si vous laissez par erreur un état récurrent dans $Q$, la matrice $I - Q$ devient non inversible (ou presque, et les résultats numériques explosent).

Le lien avec les processus de décision markoviens

Regardez à nouveau l’équation des temps moyens : $k_i = 1 + \sum_j p_{ij}\, k_j$. Remplacez « 1 » par une récompense $r(i)$ reçue dans l’état $i$ et ajoutez un facteur d’actualisation $\gamma$ : vous obtenez

$$V(i) = r(i) + \gamma \sum_j p_{ij}\, V(j),$$

l’équation de Bellman qui donne la valeur d’un état sous une politique fixée. Un processus de décision markovien, c’est une chaîne de Markov dont un agent choisit les transitions par ses actions, et l’évaluation d’une politique se résout exactement comme nos probabilités d’absorption : par conditionnement sur le premier pas, soit en résolvant un système linéaire, soit en itérant. Le cours d’Apprentissage par renforcement part de là.

En entretien

« Pour une probabilité d’absorption ou un temps moyen d’atteinte, je conditionne sur le premier pas : cela donne un système linéaire. Sous forme matricielle, la matrice fondamentale $(I - Q)^{-1}$ donne le nombre moyen de visites de chaque état transitoire, et $NR$ les probabilités d’absorption. »

En résumé

• Dans une chaîne finie, on finit toujours par quitter les classes transitoires ; la question est dans quelle classe fermée et en combien de temps.
• Conditionnement sur le premier pas : $h_i = \sum_j p_{ij} h_j$ (probabilité d’atteindre une cible), $k_i = 1 + \sum_j p_{ij} k_j$ (temps moyen), avec les conditions aux bords.
• Forme canonique $P = \begin{pmatrix} Q & R \\ 0 & I \end{pmatrix}$ ; matrice fondamentale $N = (I - Q)^{-1}$, dont le coefficient $N_{ij}$ est le nombre moyen de passages en $j$ depuis $i$.
• Temps moyens d’absorption $k = N\mathbf 1$ ; probabilités d’absorption $B = NR$.
• Ruine du joueur équitable : gain avec probabilité $i/K$, durée moyenne $i(K - i)$. Un léger désavantage par partie devient un fort désavantage global.
• L’équation des temps moyens a la même forme que l’équation de Bellman des processus de décision markoviens.

Exercices

Exercice · Petit contre gros

facile

Vous jouez à pile ou face équilibré, un euro par lancer, avec 2 € contre un adversaire qui en a 8. Quelle est votre probabilité de ruiner votre adversaire ? Combien de lancers dure la partie en moyenne ?

Voir la solution

Ici $K = 10$ et $i = 2$. Dans le cas équitable, $h_i = i/K = 2/10 = 0{,}2$ : vous gagnez une fois sur cinq. La durée moyenne vaut $k_i = i(K - i) = 2 \times 8 = 16$ lancers. Le jeu est équitable (votre gain moyen est nul), mais le joueur le plus riche gagne le plus souvent.

En code

Python

import numpy as np

K, p = 10, 0.5                           # 10 € en jeu, pièce équilibrée
n = K - 1                                # états transitoires 1, ..., 9
Q = np.diag([p] * (n - 1), 1) + np.diag([1 - p] * (n - 1), -1)
R = np.zeros((n, 2))
R[0, 0] = 1 - p                          # de 1 € vers la ruine (0)
R[-1, 1] = p                             # de 9 € vers la victoire (K)

N = np.linalg.inv(np.eye(n) - Q)         # matrice fondamentale
i = 2                                    # vous partez avec 2 €
print((N @ R)[i - 1, 1])                 # 0.2 : probabilité de ruiner l'adversaire
print(N.sum(axis=1)[i - 1])              # 16.0 lancers en moyenne

R

K <- 10; p <- 0.5                       # 10 € en jeu, pièce équilibrée
n <- K - 1                              # états transitoires 1, ..., 9
Q <- matrix(0, n, n)
Q[cbind(1:(n - 1), 2:n)] <- p           # gagner un euro
Q[cbind(2:n, 1:(n - 1))] <- 1 - p       # perdre un euro
R <- matrix(0, n, 2)
R[1, 1] <- 1 - p                        # de 1 € vers la ruine
R[n, 2] <- p                            # de 9 € vers la victoire

N <- solve(diag(n) - Q)                 # matrice fondamentale
i <- 2                                  # vous partez avec 2 €
(N %*% R)[i, 2]                         # 0.2 : probabilité de ruiner l'adversaire
rowSums(N)[i]                           # 16 lancers en moyenne

Exercice · Une souris dans un labyrinthe

moyen

Une souris se déplace entre deux salles, 1 et 2. Depuis la salle 1, elle y reste avec probabilité 0,2, passe en salle 2 avec probabilité 0,4 et tombe dans un piège (T) avec probabilité 0,4. Depuis la salle 2, elle passe en salle 1 avec probabilité 0,3, reste avec probabilité 0,2 et trouve le fromage (C) avec probabilité 0,5. Le piège et le fromage sont absorbants.

Calculez, depuis chaque salle, la probabilité de trouver le fromage et le nombre moyen de pas avant absorption.

Voir la solution

Notons $h_1, h_2$ les probabilités de trouver le fromage :

• $h_1 = 0{,}2\,h_1 + 0{,}4\,h_2$, soit $0{,}8\,h_1 = 0{,}4\,h_2$, donc $h_2 = 2\,h_1$ ;
• $h_2 = 0{,}3\,h_1 + 0{,}2\,h_2 + 0{,}5$, soit $0{,}8\,h_2 = 0{,}3\,h_1 + 0{,}5$.

En substituant, $1{,}6\,h_1 = 0{,}3\,h_1 + 0{,}5$, d’où $h_1 = 0{,}5/1{,}3 = 5/13 \approx 0{,}385$ et $h_2 = 10/13 \approx 0{,}769$.

Pour les temps moyens :

• $k_1 = 1 + 0{,}2\,k_1 + 0{,}4\,k_2$ ;
• $k_2 = 1 + 0{,}3\,k_1 + 0{,}2\,k_2$, donc $k_2 = (1 + 0{,}3\,k_1)/0{,}8$.

En substituant dans la première : $0{,}8\,k_1 = 1 + 0{,}5\,(1 + 0{,}3\,k_1) = 1{,}5 + 0{,}15\,k_1$, d’où $k_1 = 1{,}5/0{,}65 = 30/13 \approx 2{,}31$ pas, puis $k_2 = 55/26 \approx 2{,}12$ pas.

On peut vérifier avec la matrice fondamentale : $Q = \begin{pmatrix} 0{,}2 & 0{,}4 \\ 0{,}3 & 0{,}2 \end{pmatrix}$, $N = (I - Q)^{-1}$ a pour sommes de lignes $30/13$ et $55/26$.

En code

Python

import numpy as np

# États transitoires : salles 1 et 2 ; absorbants : piège T, fromage C
Q = np.array([[0.2, 0.4],
              [0.3, 0.2]])
R = np.array([[0.4, 0.0],
              [0.0, 0.5]])

N = np.linalg.inv(np.eye(2) - Q)
B = N @ R
k = N.sum(axis=1)
print(B[:, 1])                           # [0.3846 0.7692] : trouver le fromage
print(k)                                 # [2.3077 2.1154] : pas avant absorption
print(5/13, 10/13, 30/13, 55/26)         # 0.3846 0.7692 2.3077 2.1154

R

# États transitoires : salles 1 et 2 ; absorbants : piège T, fromage C
Q <- matrix(c(0.2, 0.4,
              0.3, 0.2), nrow = 2, byrow = TRUE)
R <- matrix(c(0.4, 0,
              0,   0.5), nrow = 2, byrow = TRUE)

N <- solve(diag(2) - Q)
(N %*% R)[, 2]                          # 0.3846 0.7692 : trouver le fromage
rowSums(N)                              # 2.3077 2.1154 : pas avant absorption
c(5/13, 10/13, 30/13, 55/26)            # 0.3846 0.7692 2.3077 2.1154

Exercice · La ruine au casino

difficile

On joue avec une probabilité de gain $p \neq \tfrac12$ à chaque partie, et on note $r = q/p$.

1. Vérifiez que $h_i = \dfrac{1 - r^i}{1 - r^K}$ satisfait les équations $h_i = p\,h_{i+1} + q\,h_{i-1}$ et les conditions $h_0 = 0$, $h_K = 1$.
2. Retrouvez la probabilité 0,360 donnée dans le chapitre pour $p = 0{,}4$, $i = 3$, $K = 5$.
3. À la roulette, en misant sur une couleur, on gagne avec une probabilité légèrement inférieure à 1/2. Prenons $p = 0{,}49$. Vous arrivez avec 50 € et comptez partir dès que vous aurez doublé votre mise (ou tout perdu). Quelle est votre probabilité de réussir ?

Voir la solution

1. Les conditions aux bords sont immédiates : $h_0 = 0$ et $h_K = 1$. Pour l’équation, il suffit de vérifier que $r^i$ la satisfait (une constante la satisfait aussi, et l’équation est linéaire) : $p\,r^{i+1} + q\,r^{i-1} = r^{i-1}(p r^2 + q)$. Or $p r^2 = q^2/p$, donc $p r^2 + q = q\,(q + p)/p = q/p = r$, et on obtient bien $r^i$.
2. $r = 0{,}6/0{,}4 = 1{,}5$, donc $h_3 = \dfrac{1 - 1{,}5^3}{1 - 1{,}5^5} = \dfrac{1 - 3{,}375}{1 - 7{,}59375} = \dfrac{-2{,}375}{-6{,}59375} \approx 0{,}360$.
3. $r = 0{,}51/0{,}49$, $i = 50$, $K = 100$. Comme $1 - r^{100} = (1 - r^{50})(1 + r^{50})$, on a $h_{50} = \dfrac{1}{1 + r^{50}}$. Or $r^{50} \approx 7{,}39$, donc $h_{50} \approx 0{,}119$. Avec un désavantage de seulement 1 point par partie, vous n’avez qu’environ 12 % de chances de doubler votre mise, contre 50 % dans un jeu équitable. C’est le principe du casino.

En code

Python

import numpy as np

def h_formule(i, K, p):
    r = (1 - p) / p
    return (1 - r**i) / (1 - r**K)

def h_systeme(i, K, p):
    """Résout h_j = p h_{j+1} + q h_{j-1} avec h_0 = 0 et h_K = 1."""
    n = K - 1
    Q = np.diag([p] * (n - 1), 1) + np.diag([1 - p] * (n - 1), -1)
    b = np.zeros(n); b[-1] = p
    return np.linalg.solve(np.eye(n) - Q, b)[i - 1]

print(h_formule(3, 5, 0.4), h_systeme(3, 5, 0.4))          # 0.3602 0.3602
print(h_formule(50, 100, 0.49), h_systeme(50, 100, 0.49))  # 0.1192 0.1192
print((0.51 / 0.49) ** 50)                                 # 7.391 = r^50

R

h_formule <- function(i, K, p) {
  r <- (1 - p) / p
  (1 - r^i) / (1 - r^K)
}
h_systeme <- function(i, K, p) {        # h_j = p h_{j+1} + q h_{j-1}, h_0 = 0, h_K = 1
  n <- K - 1
  Q <- matrix(0, n, n)
  Q[cbind(1:(n - 1), 2:n)] <- p
  Q[cbind(2:n, 1:(n - 1))] <- 1 - p
  b <- c(rep(0, n - 1), p)
  solve(diag(n) - Q, b)[i]
}
c(h_formule(3, 5, 0.4), h_systeme(3, 5, 0.4))          # 0.3602 0.3602
c(h_formule(50, 100, 0.49), h_systeme(50, 100, 0.49))  # 0.1192 0.1192
(0.51 / 0.49)^50                                       # 7.391 = r^50