Existe uma fórmula para uma forma geral do problema do coletor de cupons?

Eu me deparei com o problema dos coletores de cupons e estava tentando descobrir uma fórmula para uma generalização.

Se houver $N$ objetos distintos e que pretende coletar pelo menos $k$ cópias de cada de qualquer $m$ deles (onde $m \le N$ ), qual é a expectativa de quantos objetos aleatórios que você deve comprar ?. O problema normais colector cupão tem $m = N$ e $k = 1$ .

Existem 12 figuras LEGO diferentes em uma coleção. Quero coletar 3 cópias de cada uma das 10 (dez) figuras. Eu posso comprá-los aleatoriamente, um de cada vez. Quantos devo esperar comprar antes de ter 3 cópias de cada um deles?

Isso não é fácil de calcular, mas pode ser feito, desde que não é muito grande. (Esse número conta os possíveis estados que você precisa acompanhar ao coletar cupons.)$\binom{m+k}{k}$

Vamos começar com uma simulação para entender melhor a resposta. Aqui, coletei figuras de LEGO um milhão de vezes. A linha preta neste gráfico rastreia as frequências do número de compras necessárias para coletar pelo menos três dos dez números diferentes.

A faixa cinza é um intervalo de confiança aproximado de 95% nos dois lados para cada contagem. Por baixo de tudo, há uma curva vermelha: esse é o verdadeiro valor.

$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}$

$i_0$$i_0/n$$i_1/n$

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

$(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}$

$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];

O resultado, que leva cerca de dois segundos para calcular (mais rápido que a simulação!), É um conjunto de probabilidades indexadas pelo número de empates. Aqui está um gráfico de suas diferenças, que são as probabilidades de encerrar suas compras em função da contagem:

Esses são precisamente os números usados ​​para desenhar a curva de fundo vermelha na primeira figura. (Um teste qui-quadrado indica que a simulação não é significativamente diferente deste cálculo.)

$1-q$$50.7619549386733$