Lancez 100 pièces justes et enlevez les queues; jetez les pièces restantes et enlevez les queues. Continuez jusqu'à ce qu'il ne reste plus de pièces. [dupliquer]
100 participants ont chacun une pièce équitable, sur un tour donné, les participants non déjà défaussés retournent leurs pièces, ceux qui retournent une queue sont écartés du jeu, les autres continuent à jouer jusqu'à ce qu'il ne reste plus personne (tout le monde a été défaussé).
Quel serait le nombre moyen d'essais (où chaque essai consiste en un lancer et en retirant les queues) auquel on s'attendrait de faire cette expérience?
L'attente conditionnelle fonctionne-t-elle pour quelque chose comme ça?
Je sais que chaque pièce individuelle suit une distribution géométrique, mais j'essaie d'en calculer la somme pour déterminer le nombre moyen d'essais pour un jeu comme celui-ci.
Mon processus de logique / pensée: j'ai commencé par essayer de penser à la probabilité qu'une pièce particulière parvienne à arrondir $r$ lequel est $\frac{1}{2^m}$. J'ai alors réalisé que chaque résultat de pièce pouvait être modélisé par des variables aléatoires géométriques avec$p = 0.5$. Je ne sais pas comment faire le saut de ce cas unique à un cas de 100 pièces. Je suppose que cela a à voir avec la somme des variables aléatoires géométriques, mais je ne suis pas sûr.
Réponses
Cela équivaut essentiellement au calcul de la valeur attendue du maximum de$n=100$iid variables aléatoires géométriques , pour$p=\frac12$
(BTW: la question liée inclut la récursivité donnée par la réponse de @ saulspatz)
Il n'y a pas de solution de forme fermée, mais cette approximation pour les grands $n$ (avec bornes) est donné:
$$E_n \approx \frac{1}{2} + \frac{1}{\lambda} H_n$$
où $\lambda = - \log(1-p)=0.69314718\cdots$ et $H_n$ est le nombre harmonique.
Par exemple, pour $n=3$ cela donne $E_3 \approx 3.14494$ , très proche de l'exact $E_3=22/7=3.14285$
Pour $n=100$ cela donne $E_{100} \approx 7.98380382$.
Plus dans "Encore une autre application d'une statistique d'ordre de récurrence binomiale", W. Szpankowski; V. Rego, Computing, 1990, 43, 4, 401-410.
Je doute qu'il y ait une expression simple pour l'attente. Laisser$E_n$ être le nombre prévu d'essais lorsque $n$ les pièces restent, de sorte que l'on nous demande de calculer $E_{100}$. Nous savons que$E_0=0$ et cela $E_1=2$. Maintenant$$E_2=1+\frac14E_2+\frac12E_1+\frac14E_0$$ parce que nous devons faire un essai, et avec probabilité $\frac14$ nous jetons deux têtes et avons encore deux pièces, avec probabilité $\frac12$ nous jetons une tête et une queue, et avec probabilité $\frac14$, nous lançons deux queues et l'expérience se termine. Cela donne$E_2=\frac83$.
Nous pouvons continuer de cette manière: $$E_3=1+\frac18E_3+\frac38E_2+\frac38E_1+\frac18E_0$$ qui donne $E_3=\frac{22}7$ si je ne me trompe pas.
On pourrait facilement écrire un programme informatique sur lequel travailler $E_{100}$, mais il serait plus facile de procéder par simulation.
ÉDITER
J'ai écrit le scénario que j'ai suggéré. La valeur exacte si une fraction dont le numérateur a$894$ chiffres décimaux et dont le dénominateur a $893$. La valeur approximative est$7.98380153515692$.
En recherchant OEIS avec les premières valeurs @saulspatz, nous pouvons trouver que:
$$E_n = \frac{a(n)}{b(n)}$$
où $a(n)$est OEIS A158466 et$b(n)$est OEIS A158467 . Chez OEIS A158466, vous pouvez également trouver les formules suivantes:
$$E_n = -\sum_{k=1}^n (-1)^k \frac{{n \choose k}}{1-\frac{1}{2^k}}$$
$$E_n = \sum_{k=1}^{\infty} k \left(\left(1-\frac{1}{2^k}\right)^n - \left(1-\frac{1}{2^{k-1}}\right)^n\right)$$
et donc (voir ici ):
$$E_{100} \approx 7.983801535$$
Ensemble $N_0=100$ et prend $N_k$ être le nombre de pièces qui restent après le $k^\text{th}$procès dans ce processus. Donc nous pouvons dire quelque chose comme$$P(N_1=81|N_0=100)={100 \choose 19}\Big(\frac{1}{2}\Big)^{100}$$
Maintenant pour $i\in \{0,1,\ldots, 100\}$ et $j\in \{0,1,\ldots ,i\}$ nous avons $$P(N_{k+1}=j|N_{k}=i)={i \choose j-i}\Big(\frac{1}{2}\Big)^i$$ Remarquer $\{N_k\}_{k=0}^{\infty}$ est une chaîne de Markov absorbante avec $0$comme état absorbant. Vous cherchez à calculer le nombre d'essais attendu dans ce processus aléatoire avant d'être absorbé dans l'état$0$ à partir de l'état $100$. Il existe de nombreuses façons de calculer cette valeur attendue, la plus efficace est probablement d'utiliser la matrice fondamentale que vous pouvez découvrir ici