Niveau exercices

Jeu de probabilités viral

Posté par
Zormuche 08-04-24 à 23:14

Bonjour à tous
Voici un jeu qui est devenu viral récemment sur internet
Je vous le propose en détente, mais je n'ai pas l'intention de m'y pencher (les chaines de markov hyper-calculatoires n'ont jamais été mon "délire")

Il y a un gros bouton rouge et un compteur de score initialisé à zéro. Chaque fois qu'on appuie sur le bouton rouge ("étape"), le compteur peut soit s'incrémenter de 1, soit se réinitialiser à 0. La valeur du compteur à chaque étape indique la probabilité qu'il se réinitialise à la prochaine étape.

Autrement dit, au début du jeu, le compteur est à 0. Il y a 0% de chance que le compteur se réinitialise en appuyant dessus. Le compteur s'incrémentera forcément à la prochaine étape.
Après avoir appuyé une fois, le compteur passe à 1. Il y a désormais 1% de chance que celui-ci se réinitialise à la prochaine étape
Si on arrive à faire monter le compteur jusqu'à 50 (ce qui demande BEAUCOUP de persévérance), alors il passera à 51 avec seulement 50% de chance à la prochaine étape.

On considère que le jeu termine si on arrive à 100 puisqu'on ne pourra jamais dépasser ce score.

Question : pour k un entier naturel entre 1 et 100, combien de fois en moyenne faut-il appuyer sur le bouton avant que le compteur affiche un score de k ?

Posté par re : Jeu de probabilités viral 09-04-24 à 10:37

Mon intuition me dit que dans 100-k % das cas, C(k+1) = C(k)+1.

Et donc $\frac{100-k}{100}E(k+1) = E(k) +1 \Rightarrow E(k+1) = \frac{100}{100-k}(E(k)+1)$ . Avec $E(0) = 0$ .

La preuve formelle m'échappe ceci dit.

Une démonstration empirique semble confirmer ce résultat:

Jeu de probabilités viral

Figure générée avec ce code:

Cliquez pour afficher

from itertools import count
from random import random

from matplotlib import pyplot


def test(n=40):
    e = []
    p = 0

    for i in count():
        if p >= len(e):
            e.append(i)
            if p >= n:
                return e
        if random() * 100 < p:
            p = 0
        else:
            p += 1


def main():
    n, total, count = 40, [], []
    for _ in range(1000):
        sample = test(n)
        pyplot.plot(sample, 'b.', alpha=0.1, ms=0.5)
        # print(sample)
        for i, e in enumerate(sample):
            if i >= len(total):
                total.append(e)
                count.append(1)
            else:
                total[i] += e
                count[i] += 1

    pyplot.plot([0, 1], 'b.', label='samples')
    pyplot.plot([t / c for t, c in zip(total, count)], 'r', label='mean')

    e = [0]
    for k in range(n):
        e.append((e[-1] + 1) * 100 / (100 - k))

    pyplot.plot(e, 'g', label='theoretical')

    pyplot.yscale('log')
    pyplot.legend()
    pyplot.show()


if __name__ == '__main__':
    main()

Il faudrait en moyenne ~43049957 appuis pour arriver à k = 50.