Arrêt optimal pour un dé
Bonjour,
Il paraît que ça roupille sur le forum de probas...
Un petit exo rigolo : un joueur a le droit de lancer un dé à 100 faces autant de fois qu'il le souhaite. Chaque lancer lui coûte un euro, il gagne la valeur indiquée par le dé lorsqu'il choisit de s'arrêter.
Quelle est la stratégie optimale?
(J'ai vu ce problème dans le dernier numéro de Mathematics Magazine.)
Il paraît que ça roupille sur le forum de probas...
Un petit exo rigolo : un joueur a le droit de lancer un dé à 100 faces autant de fois qu'il le souhaite. Chaque lancer lui coûte un euro, il gagne la valeur indiquée par le dé lorsqu'il choisit de s'arrêter.
Quelle est la stratégie optimale?
(J'ai vu ce problème dans le dernier numéro de Mathematics Magazine.)
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Problème très rigolo, en effet, merci du partage !
On choisit un seuil S ( 80, 85 ... ??? )
Et tant qu'on n'a pas tiré un nombre supérieur à ce seuil, on rejoue.
Supposons on vient de tirer S.
Peu importe qu'on soit au 1er tirage, ou au 50ème, ça ne change rien.
S est la plus grande valeur que j'avais décidé de refuser, donc je rejoue.
Je suis au tirage t=0
La proba de faire un seul tirage supplémentaire est $(100-S-1)/100$, l'espérance du nombre obtenu dans ce cas est (100+S+1)/2, mais comme j'aurai misé 1€, mon gain sera $(100+S+1)/2-1$
Généralisation.
La proba que le jeu s'arrête au tirage n°k est $(100-S-1)/100 * ( S/100)^{k-1}$, l'espérance du gain dans ce cas là est $(100+S+1)/2-k$.
On regarde donc la série $s= \sum_k (100-S-1)/100 * ( S/100)^{k-1} * ((100+S+1)/2-k)$
Cette série converge.
On cherche pour quelle valeur de S la somme de cette série est la plus élevée. Et on espère que pour cette configuration, la somme obtenue sera bien supérieure à S !
On constate que jusqu'à 86, on a intérêt à rejouer. Et l'espérance est de 86.35
D'abord, faut-il bien choisir un seuil ?
Eh bien, si j'en suis au $n$ ème lancer, de résultat observé $X_n$, mon gain si je m'arrète est $X_n - n$.
Mon gain potentiel si je continue est $Z_n = \sup_{t>n} \{X_t-t\}$.
Alors $Z_n$ est indépendant de $X_n$, et la loi de $Z_n + n$ ne dépend pas de $n$.
Donc j'ai intérêt à continuer si $E[Z_n] \ge X_n - n$, si $X_n \le E[Z_0] < \infty$.
Donc oui, il faut choisir un seuil $S_0$ : partie entière de $E[Z_0]$.
Mais combien vaut ce seuil, donc cette espérance ?
Si j'ai choisi le seuil $S$, mon gain s'écrit : $G(S) = X_T - T$ où $T$ est le numéro du lancer où je dépasserai strictement le seuil $S$ pour la première fois.
Or :
$T$ est géométrique de paramètre $1 - \frac{S}{N} = \frac{N-S}{N}$.
$X_T$ est uniforme sur $S+1:N$. (et indépendante de $T$)
Donc $g(S) = E[G_S] = \frac{N+1+S}{2} - \frac{N}{N-S}$.
Je regarde les variations :
$g(S) - g(S-1) =
\frac{1}{2} + \frac{N}{N+1-S} - \frac{N}{N-S}
= \frac{1}{2(N+1-S)(N-S)} \cdot \big[S^2 - (2N+1)S + N(N-1)\big]
$
Discriminant $\Delta = 8N+1$.
Donc $g$ est maximisée pour $S = S_0 = \left\lfloor\frac{2N+1 - \sqrt{8N+1}}{2}\right\rfloor \approx \left\lfloor N - \sqrt{2N} + \frac{1}{2}\right\rfloor$.
Pour $N = 100$, ce qu'il y a dans la partie entière vaut $86.3490283019151$, donc le seuil est bien donné par lourrran $S_0 = 86$ et l'espérance est $g(S_0) = \frac{187}{2} - \frac{100}{14} = 86.35714285714286$ aussi donnée par lourrran.
Bonus, espérance de $Z_0$.
La fonction de répartition de $Z_0$ est :
$P(Z_0 \le x) =
\prod\limits_{t\ge 1} P(X_t \le x + t) = \frac{(x+1)(x+2)\times\dots \times N}{N^{N-x}}$.
Donc $E[Z_0] = N - \sum\limits_{x=0}^{N-1} P(Z_0 \le x) = 86.79003936978403$
Et on trouve aussi le seuil ainsi : c'est la partie entière $86$.
J'ajoute, mais je sais pas si ça veut dire quelque chose, que, pour $Y$ de Poisson $\mathcal{P}(N)$, l'espérance s'écrit $E[Z_0] = N - \frac{P(Y<N)}{P(Y=N)}$.
@sol : C'est vrai que j'ai sous-entendu sans le dire que l'on cherchait à maximiser l'espérance.
@marsup : Tu as le droit à un point de bonus pour avoir justifié la forme de la stratégie optimale ! ;-)
@marsup : Je vais essayer de formaliser un peu plus ta proposition : j’ai l’impression que tu affirmes « pour toute stratégie, si l’espérance est inférieure à un certain nombre, alors en moyenne, j’ai intérêt à continuer à jouer pendant un certain nombre -aléatoire- de coups », auquel cas je pense, a priori, que ce n’est pas exactement ça qu’on veut ; mais je fais peut-être la fine bouche parce que je suis jaloux de n’avoir pas été aussi loin que toi