Jak często musisz rzucać kostką 6-stronną, aby co najmniej raz zdobyć każdą liczbę?

41

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 n=1n16(56)n1=6.

Mam jednak dwa pytania:

  1. Ile razy musisz rzucić sześciościenną kostką, aż co najmniej raz uzyskasz każdą liczbę?
  2. 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)
Jonas
źródło
11
Zobacz także problem kolekcjonera kuponów - googling da ci o wiele więcej trafień i więcej informacji. Spróbuj także wyszukać to tutaj na stats.SE .
Glen_b
1
@Glen_b: Dzięki, nie znałem tego imienia!
Jonas
1
@whuber: Nie jestem pewien, czy to pytanie powinno zostać zamknięte. Chce spodziewanego minimalnego czasu uderzenia czterech prób. Właśnie miałem naprawić swoją odpowiedź na rozwiązanie do programowania dynamicznego.
Neil G
2
@whuber: Będę edytować mój post, aby wyjaśnić
Jonas
3
Odpowiedni post z matematyki.SE: Rozkład prawdopodobieństwa w problemie kolekcjonera kuponów
Glen_b

Odpowiedzi:

22

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 parametrem p wynosi

f(z,p)=p1(1p)z.

Dlatego pgf dla sumy tych sześciu zmiennych wynosi

g(z)=i=16f(z,i/6)=6z4(5 2z+5+10 3z+45 4z+4+5z+4+5).

(Produkt można obliczyć w tej zamkniętej formie, dzieląc go na pięć części za pomocą ułamków częściowych).

gz

F(z)=6z4((1) 1z+4+(5) 2z+4(10) 3z+4+(10) 4z+4(5) 5z+4+(1) 6z+4).

(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

E(6+X)=6+i=1(1F(i))=14710.

mXF(z)mm=4

6+i=1(1F(i)4)21.4820363.

6.77108.6

Postać

18500.3%

Whuber
źródło
Ta metoda rozwiązania została zainspirowana obserwacją, że sumy zmiennych geometrycznych są mieszaninami (prawdopodobnie o wadze ujemnej) zmiennych geometrycznych o tych samych parametrach. Podobny związek zachodzi między zmiennymi Gamma (o różnych parametrach częstości). Przepraszam za wykonanie pracy w Mathematica, ale jestem pewien, że Matlab również może wykonać te obliczenia :-).
whuber
2
Oto odpowiedź, na którą liczyłem. Dziękuję Ci bardzo! Myślę, że powinienem być w stanie obliczyć wyniki liczbowe w Matlabie :)
Jonas
f(z,p)=p1(1p)zi=16f(z,i/6)F(z)g(z)
1
f(z,p)
@MartijnWeterings Dziękuję - uważam, że jest to bardziej dokładny i konwencjonalny termin. (Możesz powiedzieć, że mam tendencję do myślenia o pmf i pgf jako prawie tym samym, ze względu na długi nawyk korzystania z funkcji generujących.) Zmienię terminologię w tym poście.
whuber
13

{0,,6}ii6ii+16i6

i=0566i=14.7

(6,6,6,6)jiTiijpipijij. Czasy uderzeń i prawdopodobieństwa możesz poznać, programując dynamicznie. To nie jest takie trudne, ponieważ istnieje polecenie przejścia, aby wypełnić czasy uderzeń i prawdopodobieństwa. Na przykład dla dwóch kości: najpierw oblicz T i p dla (0,0), następnie dla (1,0), następnie (1, 1), (2, 0), a następnie (2, 1) itd.

W Pythonie:

import numpy as np
import itertools as it
from tools.decorator import memoized  # A standard memoization decorator

SIDES = 6

@memoized
def get_t_and_p(state):
    if all(s == 0 for s in state):
        return 0, 1.0
    n = len(state)
    choices = [[s - 1, s] if s > 0 else [s]
               for s in state]
    ts = []
    ps = []
    for last_state in it.product(*choices):
        if last_state == state:
            continue
        last_t, last_p = get_t_and_p(tuple(sorted(last_state)))
        if last_p == 0.0:
            continue
        transition_p = 1.0
        stay_p = 1.0
        for ls, s in zip(last_state, state):
            if ls < s:
                transition_p *= (SIDES - ls) / SIDES
            else:
                transition_p *= ls / SIDES
            stay_p *= ls / SIDES
        if transition_p == 0.0:
            continue
        transition_time = 1 / (1 - stay_p)
        ts.append(last_t + transition_time)
        ps.append(last_p * transition_p / (1 - stay_p))
    if len(ts) == 0:
        return 0, 0.0
    t = np.average(ts, weights=ps)
    p = sum(ps)
    return t, p

print(get_t_and_p((SIDES,) * 4)[0])
Neil G.
źródło
1
Przegapiłeś oczekiwaną maksymalną liczbę rzutów w czterech niezależnych powtórzeniach gry.
probabilityislogic
Ach, właśnie to zauważyłem. Myślę, że masz na myśli minimum, ale tak.
Neil G
@ NeilG: Mam na myśli maksimum (patrz moje zaktualizowane pytanie), choć zakładam, że strategia jest taka sama dla min i maks. Czy możesz rozwinąć strategię dynamicznego programowania?
Jonas,
@Jonas: zaktualizowano do maksimum. Mam dużo pracy, ale może uda mi się to później napisać.
Neil G,
2
@NeilG: Dzięki. Miałem nadzieję na podejście całkowicie analityczne, ale kod DP jest również dość pouczający.
Jonas
6

Szybkie i brudne oszacowanie Monte Carlo w R długości gry dla 1 gracza:

N = 1e5
sample_length = function(n) { # random game length
    x = numeric(0)
    while(length(unique(x)) < n) x[length(x)+1] = sample(1:n,1)
    return(length(x))
}
game_lengths = replicate(N, sample_length(6))

μ^=14.684σ^=6.24[14.645,14.722]

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

grouped_lengths = matrix(game_lengths, ncol=4)
min_lengths = apply(grouped_lengths, 1, min)

μ^=9.44σ^=2.26[9.411,9.468]

bnaul
źródło
1
Do bardzo podobnego wyniku doszłam z symulacją Matlaba, ale byłem ciekawy, jak rozwiązać to analitycznie. Ponadto, ponieważ bawię się z moimi dziećmi, one wszystkie chcą ukończyć grę, niezależnie od tego, kto wygra, więc chcę zapytać o maksimum.
Jonas
5

m

T1=6
Tm=1+6m6Tm+m6Tm1

m1

  • Tm6m6m6
  • Tm1mm6

14.7

ThePawn
źródło
Ti=Ti1+66i+1
1
Tak, przepraszam, popełniłem błąd, naprawiam go
ThePawn
Mam nadzieję, że nie masz nic przeciwko, że dodałem odpowiedź. 14.7 ma rację, ale relacja powtarzalności jest nadal wadliwa…
Neil G
Nie ma problemu, powinienem był uważać za pierwszym razem :). Twoja odpowiedź jest świetna.
ThePawn
5

Proste i intuicyjne wyjaśnienie pierwszego pytania:

Najpierw musisz rzucić dowolną liczbą. To łatwe, zawsze zajmie dokładnie 1 rzut.

5665

4664

3663

I tak dalej, aż pomyślnie zakończymy nasz 6. rzut:

66+65+64+63+62+61=14.7 rolls

Ta odpowiedź jest podobna do odpowiedzi Neila G., tylko bez łańcucha markowa.


źródło
1

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

MikeP
źródło
-4

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

Stef van Buuren
źródło
6
Odpowiadałoby to na pytanie „zagwarantować z absolutną pewnością, że każdy numer otrzyma przynajmniej raz”. Na zadane pytanie odpowiedź jest zmienną losową, której rozkład można dobrze oszacować.
Glen_b