Introduction
J’ai vu passer, sur LinkedIn, un problème du type ruine du joueur posé lors d’une entrevue dans une grande entreprise américaine. Le problème est le suivant:
Supposons que vous avez 30$. Vous jouer à pile ou face. Pour chaque pile, vous gagnez 1$, pour chaque face, vous perdez 1$. Le jeu s’arrête lorsque vous n’avez plus d’argent ou que vous avec 100$. Quelle est la probabilité de terminer le jeu avec 100$ ?
Il s’agit d’un problème de probabilité sur un horizon infini, nommé le problème de la ruine du joueur. Pour compliquer les choses, la candidate ou le candidat se fait proposer des choix de réponses.
Énoncé mathématique du problème
Dans ce problème de la ruine du joueur, on considère que le casino possède 70$ et qu’il est ruiné si vous gagnez. Il existe une démonstration mathématique assez complexe, pour laquelle le résultat est le suivant
\rho = \frac{a}{a+b} \text{ où } a = 30\$ \text{ et } b=70\$
La probabilité recherchée est donc
\rho = 0.3
Dans un contexte d’entrevue, nous n’avons probablement pas en tête ce genre de démonstration. L’intuition pourrait nous faire répondre 30%, mais le but ici est plutôt de démontrer comment résoudre le problème. Donc, voici comment j’aurais expliqué ma démarche.
Approche par simulation pour approximer la ruine du joueur
Premièrement, un horizon infini peut être approximé par un horizon suffisamment long. Disons qu’on va prendre une séquence de 10 000 réalisations d’un tirage de pile ou face. Cette séquence va, avec une probabilité élevée (que nous n’estimerons pas ici, mais qui fait aussi partie de la démonstration mathématique en question) fournir un évènement de ruine ou de gain.
Afin de pouvoir estimer la probabilité de l’évènement de gain, nous allons donc simuler 10 000 fois cette expérience. Nous allons donc tirer 100 000 000 fois à pile ou face. Heureusement, les ordinateurs permettent de faire ce travail en quelques secondes !
Voici un exemple de code avec le langage R, écrit de façon rapide, qui permet d’effectuer ce tirage aléatoire et d’estimer la probabilité de gain.
# Fixer la graine du générateur de nombres aléatoires pour la reproductibilité des résultats set.seed(123) # Effectuer 10000 tirages à pile ou face à l'aide d'une fonction et retourner le temps de la première fois où la série atteint 0 ou 100. f1 <- function(){ sims <- 30+cumsum(c(-1,1)[rbinom(10000,1,.5)+1]) c(min(10001,(1:10000)[sims==0]), min(10001,(1:10000)[sims==100])) } # Effectuer 10000 expériences ex <- data.frame(t(replicate(n = 10000,f1()))) # Compter le nombre d'expériences où 100 survient avant 0 a <- sum(ex$X1>ex$X2) # Compter le nombre d'expériences où 0 survient avant 100 b <- sum(ex$X1<ex$X2) # Calculer la probabilité de gain a / (a+b)
L’exécution de ce code, en utilisant une graine de générateur aléatoire fixe, retourne le résultat suivant:
[1] 0.2966878
On peut donc conclure, en utilisant un algorithme de simulation simple, que la probabilité de gain est d’environ 30% !