Właśnie grałem z moimi dziećmi, która w zasadzie sprowadza się do: kto rzuci każdą liczbą przynajmniej raz na 6-stronnej kości, wygrywa.
W końcu wygrałem, a inni ukończyli 1-2 tury później. Teraz zastanawiam się: jaka jest oczekiwana długość gry?
Wiem, że oczekiwanie na liczbę rzutów do momentu trafienia w określoną liczbę wynosi .
Mam jednak dwa pytania:
- Ile razy musisz rzucić sześciościenną kostką, aż co najmniej raz uzyskasz każdą liczbę?
- Spośród czterech niezależnych prób (tj. Z czterema graczami), jaka jest oczekiwana maksymalna liczba wymaganych rzutów? [uwaga: jest maksymalna, a nie minimalna, ponieważ w ich wieku chodzi bardziej o ukończenie niż o dotarcie tam jako pierwsze dla moich dzieci]
Mogę zasymulować wynik, ale zastanawiam się, jak bym go obliczył analitycznie.
Oto symulacja Monte Carlo w Matlabie
mx=zeros(1000000,1);
for i=1:1000000,
%# assume it's never going to take us >100 rolls
r=randi(6,100,1);
%# since R2013a, unique returns the first occurrence
%# for earlier versions, take the minimum of x
%# and subtract it from the total array length
[~,x]=unique(r);
mx(i,1)=max(x);
end
%# make sure we haven't violated an assumption
assert(numel(x)==6)
%# find the expected value for the coupon collector problem
expectationForOneRun = mean(mx)
%# find the expected number of rolls as a maximum of four independent players
maxExpectationForFourRuns = mean( max( reshape( mx, 4, []), [], 1) )
expectationForOneRun =
14.7014 (SEM 0.006)
maxExpectationForFourRuns =
21.4815 (SEM 0.01)
Odpowiedzi:
Ponieważ zażądano „całkowicie analitycznego podejścia”, oto dokładne rozwiązanie. Zapewnia również alternatywne podejście do rozwiązania pytania przy prawdopodobieństwie narysowania czarnej kulki w zestawie czarno-białych kulek z mieszanymi warunkami wymiany .
Liczba ruchów w grze,X może być modelowane jako sumę sześciu niezależnych realizacji geometrycznych ( p ) zmiennymi prawdopodobieństw p = 1 , 5 / 6 , 4 / 6 , 3 / 6 , 2 / 6 , 1 / 6 , każdy z nich przesunięty o 1 (ponieważ zmienna geometryczna liczy tylko wcześniejsze rolkisukces i musimy również liczyć rzuty, w których zaobserwowano sukcesy). Dzięki obliczeniom z rozkładem geometrycznym otrzymamy zatem odpowiedzi, które są o 6 mniejsze niż pożądane, dlatego też na końcu należy dodać 6 .
Funkcja generująca prawdopodobieństwo (pgf) takiej zmiennej geometrycznej z parametremp wynosi
Dlatego pgf dla sumy tych sześciu zmiennych wynosi
(Produkt można obliczyć w tej zamkniętej formie, dzieląc go na pięć części za pomocą ułamków częściowych).
(Napisałem to wyrażenie w formie, która sugeruje alternatywne wyprowadzenie poprzez zasadę włączenia-wykluczenia).
Z tego otrzymujemy oczekiwaną liczbę ruchów w grze (odpowiadając na pierwsze pytanie) jako
źródło
W Pythonie:
źródło
Szybkie i brudne oszacowanie Monte Carlo w R długości gry dla 1 gracza:
Aby określić długość gry dla czterech graczy, możemy pogrupować próbki w czwórki i przyjąć średnią minimalną długość każdej grupy (pytałeś o maksymalną, ale zakładam, że miałeś na myśli minimalną, ponieważ sposób, w jaki ją czytałem, gra kończy się, gdy komuś uda się zdobyć wszystkie liczby):
źródło
źródło
Proste i intuicyjne wyjaśnienie pierwszego pytania:
Najpierw musisz rzucić dowolną liczbą. To łatwe, zawsze zajmie dokładnie 1 rzut.
I tak dalej, aż pomyślnie zakończymy nasz 6. rzut:
Ta odpowiedź jest podobna do odpowiedzi Neila G., tylko bez łańcucha markowa.
źródło
funkcja gęstości prawdopodobieństwa (lub dyskretny ekwiwalent) dla uzyskania następnego nowego numeru to:
f = suma (p * (1 - p) ^ (i - 1), i = 1 .. inf)
gdzie p jest prawdopodobieństwem na rzut, 1, gdy nie zostały wyrzucone żadne liczby, 5/6 po 1, 4/6 .. do 1/6 dla ostatniej liczby
wartość oczekiwana, mu = suma (i * p * (1 - p) ^ (i - 1), i = 1 .. inf) pozwalając n = i - 1 i wyprowadzając p poza sumę,
mu = p * suma ((n + 1) * (1 - p) ^ n, n = 0 .. inf)
mu = p * suma (n (1-p) ^ n, n = 0 .. inf) + p * suma ((1-p) ^ n, n = 0 .. inf) mu = p * (1-p ) / (1-p-1) ^ 2 + p * 1 / (1- (1-p))
mu = p * (1 - p) / p ^ 2 + p / p
mu = (1 - p) / p + p / p
mu = (1 - p + p) / p
mu = 1 / p
Suma oczekiwanych wartości (mus) dla ps wynoszących 1, 5/6, 4/6, 3/6, 2/6 i 1/6 wynosi 14,7, jak poprzednio podano, ale 1 / p na wymaganą liczbę jest ogólna niezależnie od wielkości matrycy
podobnie możemy obliczyć odchylenie standardowe w sposób analityczny
sigma ^ 2 = suma ((i - mu) ^ 2 * p * (1 - p) ^ (i - 1), i = 1 .. inf)
Oszczędzę ci tutaj algebry, ale sigma ^ 2 = (1-p) / p ^ 2
W przypadku liczby 6 suma sigma ^ 2 dla każdego kroku wynosi 38,99 dla odchylenia standardowego około 6,24, ponownie, jak zasymulowano
źródło
Pytanie 1 brzmiało:
Ile razy musisz rzucić sześciościennymi kostkami, aż przynajmniej raz uzyskasz każdą liczbę?
Oczywiście poprawna odpowiedź musi być „nieskończona”.
źródło