Czy istnieje wzór na ogólną formę problemu z kolektorem kuponów?

Natknąłem się na problem kolektorów kuponów i próbowałem wypracować formułę na uogólnienie.

Jeśli istnieje różnych obiektów i chcesz zebrać co najmniej kopii każdego z nich (gdzie ), jakie jest oczekiwanie na liczbę losowych obiektów? Normalny problem z kolektorem kuponów ma i . $N$ $k$ $m$ $m \le N$ $m = N$ $k = 1$

W kolekcji znajduje się 12 różnych figurek LEGO. Chcę zebrać 3 kopie każdej z 10 (dowolnych 10) figurek. Mogę je kupić losowo pojedynczo. Ile powinienem kupić, zanim będę miał 3 kopie każdego z 10 z nich?

probability binomial expected-value coupon-collector-problem nickponline
źródło

Nie przypominam sobie, że widziałem formułę tego szczególnego uogólnienia, ale w przypadku takiego jednorazowego konkretnego pytania, zwykle używam symulacji.

Glen_b

Nie jest to łatwe do obliczenia, ale można to zrobić, pod warunkiem że $\binom{m+k}{k}$ nie jest zbyt duży. (Liczba ta uwzględnia możliwe stany, które należy śledzić podczas zbierania kuponów).

Zacznijmy od symulacji, aby uzyskać odpowiedź na pytanie. Tutaj zebrałem figurki LEGO milion razy. Czarna linia na tym wykresie śledzi częstotliwości liczby zakupów potrzebnych do zebrania co najmniej trzech z dziesięciu różnych liczb.

Szare pasmo jest przybliżonym dwustronnym 95% przedziałem ufności dla każdej liczby. Pod tym wszystkim znajduje się czerwona krzywa: to jest prawdziwa wartość.

Aby uzyskać prawdziwe wartości, weź pod uwagę stan rzeczy podczas zbierania liczb, których jest możliwych typów i chcesz zebrać co najmniej z różnych typów. Jedyne informacje, które musisz śledzić, to ile liczb nie widziałeś, ile widziałeś tylko raz, ile widziałeś dwa razy i ile widziałeś trzy lub więcej razy. Możemy to wygodnie przedstawić jako gdzie to powiązane liczby, indeksy od do . Ogólnie używalibyśmy monomialów formy $n=12$ $k=3$ $m=10$ $x_0^{i_0} x_1^{i_1} x_2^{i_2} x_3^{i_3}$ $i_j$ $k=0$ $k=t$ $\prod_{j=0}^k x_j^{i_j}$ .

Po zebraniu nowego obiektu losowego będzie to jeden z niewidocznych obiektów z prawdopodobieństwem , jeden z obiektów widzianych tylko raz z prawdopodobieństwem i tak dalej. Wynik można wyrazić jako liniową kombinację monomialów, $i_0$ $i_0/n$ $i_1/n$

x_{0}^{{ja}_{0}} x_{1}^{{ja}_{1}} x_{2)}^{{ja}_{2)}} x_{3)}^{{ja}_{3)}} \to \frac{1}{n} ({ja}_{0} x_{0}^{{ja}_{0} - 1} x_{1}^{{ja}_{1} + 1} x_{2)}^{{ja}_{2)}} x_{3)}^{{ja}_{3)}} + \dots + {ja}_{3)} x_{0}^{{ja}_{0}} x_{1}^{{ja}_{1}} x_{2)}^{{ja}_{2)} - 1} x_{3)}^{{ja}_{3)}}) .

$x_0^{i_0} x_1^{i_1} x_2^{i_2} x_3^{i_3}\to \frac{1}{n}\left(i_0 x_0^{i_0-1}x_1^{i_1+1}x_2^{i_2}x_3^{i_3} + \cdots + i_3 x_0^{i_0}x_1^{i_1}x_2^{i_2-1}x_3^{i_3}\right).$

Jest to wynik zastosowania liniowego operatora różnicowego do monomialu. Oczywiście powtarzane aplikacje do stanu początkowego dadzą wielomian , mający co najwyżej , gdzie współczynnik to szansa na bycie w stanie wskazanym przez jego wykładniki. Mamy tylko trzeba skupić się na warunkach w z : suma ich współczynników będzie szansa po zakończeniu zbierania kuponów. Całe obliczenie wymaga zatem do $(x_1 D_{x_0} + x_2 D_{x_1} + x_3 D_{x_2} + x_3 D_{x_3})/n$ $x_0^{12}=x_0^n$ $p$ $\binom{n+k}{k}$ $\prod_{j=0}^k x_j^{i_j}$ $p$ $i_3 \ge t$ $(m+1)\binom{n+k}{k}$ łatwe obliczenia na każdym etapie, powtarzane tyle razy, ile jest to konieczne, aby mieć pewność, że kolekcja się powiedzie.

Wyrażenie tego procesu w ten sposób umożliwia wykorzystanie wydajności systemów algebry komputerowej. Oto, na przykład, ogólne rozwiązanie Mathematica do obliczania szans aż do losowań. To pomija pewne możliwości, ale ich całkowite szanse są mniejsze niż , co daje nam prawie pełny obraz rozkładu. $6nk=216$ $10^{-17}$

n = 12;
threshold = 10;
k = 3;

(* Draw one object randomly from an urn with `n` of them *)
draw[p_] := 
  Expand[Sum[Subscript[x, i] D[#, Subscript[x, i - 1]], {i, 1, k}] + 
      Subscript[x, k] D[#, Subscript[x, k]] & @ p];

(* Find the chance that we have collected at least `k` each of `threshold` objects *)
f[p_] := Sum[
  Coefficient[p, Subscript[x, k]^t] /. 
   Table[Subscript[x, i] -> 1, {i, 0, k - 1}], {t, threshold, n}]

(* Compute the chances for a long series of draws *)
q = f /@ NestList[draw[#]/n &, Subscript[x, 0]^n, 6 n k];

Wynik, którego obliczenie zajmuje około dwóch sekund (szybciej niż symulacja!), To tablica prawdopodobieństw zindeksowana liczbą losowań. Oto wykres różnic, które są prawdopodobieństwem zakończenia zakupów w zależności od liczby:

Są to dokładnie liczby użyte do narysowania czerwonej krzywej tła na pierwszym rysunku. (Test chi-kwadrat wskazuje, że symulacja nie różni się znacząco od tego obliczenia.)

Oszacowaną liczbę losowań możemy oszacować, sumując ; wynik powinien być dobry do 14-15 miejsc po przecinku. Otrzymuję (co jest poprawne w każdej cyfrze, co wynika z dłuższych obliczeń). $1-q$ $50.7619549386733$

Whuber
źródło

Czy istnieje wzór na ogólną formę problemu z kolektorem kuponów?

Odpowiedzi: