[SOLUTION] Biaiser les probabilités

[Supersedes pour corriger le titre]

Le 28/01/2024 11:11, Julien Arlandis a écrit :

 
Vous disposiez d'un ticket composé de N cases à gratter, chaque case
représente soit un gain soit une perte avec une probabilité de 1/2. Le
jeu consiste à miser sur n'importe quelle case non grattée et pour faire
votre choix vous avez la possibilité de gratter autant de cases que vous
le désirez (dans la limite de N-1 sinon vous ne pouvez plus jouer).
La question est la suivante : existe t-il une stratégie qui permette de
gagner avec une probabilité strictement supérieure à 1/2 ?

Je vais prouver par récurrence que l'on ne peut pas faire mieux que miser
sur une case au hasard et ne gratter que celle-là. Et que ce résultat est
vrai même si on sait au départ combien de cases de la grille sont gagnantes
(donc par exemple une grille équilibrée avec N/2 cases gagnantes et N/2
cases perdantes).


Définissons une fonction de choix c(n,*) à valeurs dans [0, 1]. Le premier
paramètre n est le nombre de cases non encore grattées, mais il peut y avoir
d'autres paramètres (que je note *), par exemple le nombre de cases gagnantes
nos grattées (si tant est qu'on connaisse ce nombre), ou bien le nombre de
cases gagnantes ou perdantes déjà grattées.

Si c(n,*) = 1, on mise sur la prochaine case et on la gratte.
Si c(n,*) = 0, on gratte une nouvelle case sans avoir misé dessus.
Si c(n,*) est strictement compris entre 0 et 1, alors on tire au hasard pour
savoir si on doit miser (avec la probabilité c(n,*)) avant de gratter la case
suivante.

J'impose juste que c(1,*) = 1 parce que le contraire serait stupide, mais
pour n > 1 je te laisse choisir c(n,*) comme tu veux.


Je vais prouver par récurrence que pour tout n, si g est le nombre de cases
gagnantes parmi les n cases restantes, alors la probabilité de gain est égale
à g/n quelle que soit la stratégie c(n,*).


Tout d'abord, si n=1, c(1,*) valant 1 on est forcé de miser, et on gagne si
g=1 tandis qu'on perd si g=0. On vérifie bien dans ce cas que la probabilité
de gagner est g/n (c'est-à-dire g puisque n=1).

Supposons maintenant que l'hypothèse est vraie au rang n-1, et vérifions la
au rang n. On choisit de miser avec une probabilité c(n,*) et de ne pas miser
avec une probabilité (1 - c(n,*)).

Si on mise, on gagne avec une probabilité g/n.

Si on ne mise pas, on se retrouve alors dans l'un des deux cas suivants après
avoir gratté :
− (n-1, g-1) avec une probabilité g/n
− (n-1, g) avec une probabilité (n-g)/n

D'après l'hypothèse de récurrence, la probabilité de gagner devient alors :
− (g-1)/(n-1) dans le premier cas
− g/(n-1) dans le second cas


On peut maintenant calculer la probabilité de gagner depuis (n, g) :
proba = c(n,*)×g/n + (1 - c(n,*)) × (g/n × (g-1)/(n-1) + (n-g)/n × g/(n-1))
      = c(n,*)×g/n + (1 - c(n,*)) × (g(g-1) / n(n-1) + g(n-g) / n(n-1))   (*)
      = c(n,*)×g/n + (1 - c(n,*)) × (g(n-1) / n(n-1))
      = c(n,*)×g/n + (1 - c(n,*)) × g/n
      = g/n

Ce résultat démontré par récurrence est complètement indépendant de la fonction
de choix, CQFD.

--
Olivier Miakinen
(*) pour simplifier l'écriture je suppose ici que la multiplication n(n-1) est
prioritaire sur la division par /