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

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 $\sum_{n=1}^\infty n\frac{1}{6}(\frac{5}{6})^{n-1}=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)

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) = \frac{p}{1-(1-p)z}.$$

Dlatego pgf dla sumy tych sześciu zmiennych wynosi

$$g(z) = \prod_{i=1}^6 f(z, i/6) = 6^{-z-4} \left(-5\ 2^{z+5}+10\ 3^{z+4}-5\ 4^{z+4}+5^{z+4}+5\right).$$

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

$g$$z$

$$F(z) = 6^{-z-4} \left(-(1)\ 1^{z+4} + (5)\ 2^{z+4}-(10)\ 3^{z+4}+(10)\ 4^{z+4}-(5)\ 5^{z+4}+(1)\ 6^{z+4}\right).$$

(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

$$\mathbb{E}(6+X) = 6+\sum_{i=1}^\infty \left(1-F(i)\right) = \frac{147}{10}.$$

$m$$X$$F(z)^m$$m=4$

$$6+\sum_{i=1}^\infty \left(1-F(i)^4\right) \approx 21.4820363\ldots.$$

$6.77108\ldots.$$6$

$18$$50$$0.3\%$

$\{0, \dotsc, 6\}$$i$$\frac{i}{6}$$i$$i+1$$\frac{6-i}{6}$

$$\begin{align} \sum_{i=0}^5 \frac{6}{6-i} = 14.7 \end{align}$$

$(6,6,6,6)$$j$$i$$T_i$$i$$j$$p_ip_{ij}$$i$$j$. 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])

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

$\hat{\mu}=14.684$$\hat{\sigma} = 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)

$\hat{\mu}=9.44$$\hat{\sigma} = 2.26$$[9.411,9.468]$

$m$

$$T_{1} = 6$$ $$T_{m} = 1 + \frac{6 - m}{6}T_{m} + \frac{m}{6}T_{m-1}$$

$m$$1$

• $T_{m}$$6 - m$$\frac{6 - m}{6}$
• $T_{m-1}$$m$$\frac{m}{6}$

$14.7$

Proste i intuicyjne wyjaśnienie pierwszego pytania:

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

$\frac{5}{6}$$\frac{6}{5}$

$\frac{4}{6}$$\frac{6}{4}$

$\frac{3}{6}$$\frac{6}{3}$

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

$\frac{6}{6} + \frac{6}{5} + \frac{6}{4} + \frac{6}{3} + \frac{6}{2} + \frac{6}{1} = 14.7\ rolls$

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

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

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