Arrêt optimal pour un dé — Les-mathematiques.net The most powerful custom community solution in the world

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.)

Réponses

  • Hum, mes calculs me disaient d’arrêter dès que le dé montre $13$ ou plus et mon ordinateur me dit que c’est $87$ qu’il faut attendre... Je m’y remets demain !

    Problème très rigolo, en effet, merci du partage !
  • J'ai un dé à 100 faces, numérotées de 1 à 100.
    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
  • Je prends $100 = N$.

    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)}$.
  • lourran et marsup : (tu)
  • La notion de stratégie optimale est-elle si claire ? Le paradoxe de Saint-Pétersbourg permet d'en douter.
  • @Georges Abitbol : je viens de voir que tu avais écrit un truc en blanc. Je ne comprends pas très bien : ton programme réussit à te trouver une stratégie sans que tu aies calculé quelque chose explicitement ? Qu'est-ce que tu as codé ?

    @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 ! ;-)
  • J’ai calculé quelque chose comme ce qu’a proposé marsup mais je me suis gouré en cherchant les racines. Par contre, le tableur m’a permis de trouver le maximum, mais comme je me suis trompé dans la formule pour l’espérance d’une loi uniforme, c’est faux mais pas de beaucoup.

    @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 :D
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!