Rzuć 100 jasnymi monetami i usuń ogony; wrzuć pozostałe monety i usuń ogony. Kontynuuj, aż nie pozostaną żadne monety. [duplikować]
100 uczestników ma uczciwą monetę, w danej rundzie, nie odrzuceni uczestnicy odwracają swoje monety, ci, którzy odwrócili ogon, są odrzucani z gry, pozostali kontynuują grę, dopóki nikogo nie zostanie (wszyscy zostali odrzuceni).
Jaka byłaby średnia liczba prób (gdzie każda próba składa się z rzucania i usuwania ogonów), jakiej można by się spodziewać po wykonaniu tego eksperymentu?
Czy warunkowe oczekiwanie działa w przypadku czegoś takiego?
Wiem, że każda pojedyncza moneta ma rozkład geometryczny, ale próbuję obliczyć ich sumę, aby określić średnią liczbę prób w takiej grze.
Moja logika / proces myślowy: Zacząłem próbować pomyśleć o prawdopodobieństwie zaokrągleń danej monety $r$ który jest $\frac{1}{2^m}$. Potem zdałem sobie sprawę, że każdy wynik monety można modelować za pomocą geometrycznych zmiennych losowych z$p = 0.5$. Nie jestem teraz pewien, jak przejść od tej pojedynczej skrzynki do skrzynki ze 100 monetami. Przypuszczam, że ma to związek z sumowaniem geometrycznych zmiennych losowych, ale nie jestem pewien.
Odpowiedzi
Jest to zasadniczo równoważne z obliczeniem oczekiwanej wartości maksimum$n=100$iid geometryczne zmienne losowe dla$p=\frac12$
(BTW: połączone pytanie zawiera rekursję podaną przez odpowiedź @ saulspatz)
Nie ma rozwiązania w postaci zamkniętej, ale to przybliżenie dla dużych $n$ (z ograniczeniami) jest podane:
$$E_n \approx \frac{1}{2} + \frac{1}{\lambda} H_n$$
gdzie $\lambda = - \log(1-p)=0.69314718\cdots$ i $H_n$ jest liczbą harmoniczną.
Na przykład dla $n=3$ to daje $E_3 \approx 3.14494$ , bardzo blisko dokładności $E_3=22/7=3.14285$
Dla $n=100$ to daje $E_{100} \approx 7.98380382$.
Więcej w "Kolejne zastosowanie statystyki powtarzalności dwumianowej", W. Szpankowski; V. Rego, Computing, 1990, 43, 4, 401-410.
Wątpię, czy istnieje proste wyrażenie na to oczekiwanie. Pozwolić$E_n$ być oczekiwaną liczbą prób, kiedy $n$ monety pozostają, więc jesteśmy proszeni o obliczenie $E_{100}$. Wiemy to$E_0=0$ i to $E_1=2$. Teraz$$E_2=1+\frac14E_2+\frac12E_1+\frac14E_0$$ ponieważ musimy wykonać jedną próbę i jest to prawdopodobne $\frac14$ rzucamy dwiema głowami i nadal mamy dwie monety, prawdopodobnie $\frac12$ rzucamy głową i ogonem, i to z prawdopodobieństwem $\frac14$, rzucamy dwoma ogonami i eksperyment się kończy. To daje$E_2=\frac83$.
Możemy kontynuować w ten sposób: $$E_3=1+\frac18E_3+\frac38E_2+\frac38E_1+\frac18E_0$$ co daje $E_3=\frac{22}7$ Jeśli się nie mylę.
Można było łatwo napisać program komputerowy do pracy $E_{100}$, ale byłoby łatwiej przeprowadzić symulację.
EDYTOWAĆ
Napisałem scenariusz, który zasugerowałem. Dokładna wartość, jeśli ułamek, którego licznik ma$894$ cyfry dziesiętne i których mianownik ma $893$. Przybliżona wartość to$7.98380153515692$.
Przeszukując OEIS z pierwszymi wartościami @saulspatz, możemy znaleźć, że:
$$E_n = \frac{a(n)}{b(n)}$$
gdzie $a(n)$to OEIS A158466 i$b(n)$to OEIS A158467 . W OEIS A158466 można również znaleźć następujące formuły:
$$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)$$
a zatem (patrz tutaj ):
$$E_{100} \approx 7.983801535$$
Zestaw $N_0=100$ i weź $N_k$ być liczbą monet pozostałych po $k^\text{th}$próba w tym procesie. Więc możemy powiedzieć coś w stylu$$P(N_1=81|N_0=100)={100 \choose 19}\Big(\frac{1}{2}\Big)^{100}$$
Teraz dla $i\in \{0,1,\ldots, 100\}$ i $j\in \{0,1,\ldots ,i\}$ mamy $$P(N_{k+1}=j|N_{k}=i)={i \choose j-i}\Big(\frac{1}{2}\Big)^i$$ Ogłoszenie $\{N_k\}_{k=0}^{\infty}$ jest absorbującym łańcuchem Markowa z $0$jako stan absorbujący. Chcesz obliczyć oczekiwaną liczbę prób w tym losowym procesie, zanim zostaniesz wchłonięty przez stan$0$ począwszy od stanu $100$. Istnieje wiele sposobów obliczenia tej oczekiwanej wartości, najbardziej wydajne jest prawdopodobnie wykorzystanie podstawowej macierzy, o której możesz się dowiedzieć tutaj