Distribución de probabilidades en el problema del cobrador de cupones

Question

Estoy intentando resolver el conocido Problema del Coleccionista de Cupones encontrando explícitamente la distribución de probabilidades (hasta ahora todos los métodos que he leído implican utilizar algún tipo de truco). Sin embargo, no estoy teniendo mucha suerte, ya que la combinatoria no es algo que se me dé especialmente bien.

El problema del coleccionista de cupones se plantea así:

Existen $m$ diferentes tipos de cupones para recoger en las cajas. Suponiendo que cada tipo de cupón tiene la misma probabilidad de encontrarse por caja, ¿cuál es la cantidad esperada de cajas que hay que comprar para recoger todos los tipos de cupones?

Lo que intento:

Sea $N$ sea la variable aleatoria asociada al número de cajas que hay que comprar para encontrar todos los cupones. Entonces $P(N=n)=\frac{|A_n|}{|\Omega _n|}$ donde $A_n$ es el conjunto de todos los resultados tales que todos los tipos de cupones se observan en $n$ compra, y $\Omega _n$ es el conjunto de todos los resultados posibles en $n$ compra. Creo que $|\Omega _n| = m^n$ pero ya ni siquiera estoy seguro de ello, ya que todos mis intentos hasta ahora han dado lugar a probabilidades basura que divergían o no sumaban 1.

Answer 1

Como Henry señaló en un comentario, la probabilidad se ha determinado en otro lugar como

$$ \def\stir#1#2{\left\{#1\atop#2\right\}} P(N=n)=\frac{m!}{m^n}\stir{n-1}{m-1}\;, $$

donde

$$\stir nk=\frac1{k!}\sum_{j=0}^k(-1)^{k-j}\binom kjj^n$$

es un Número de Stirling del segundo tipo y cuenta el número de particiones de un conjunto de $n$ objetos etiquetados en $k$ subconjuntos no etiquetados no vacíos.

Para obtener el valor esperado, es algo más cómodo trabajar con la probabilidad

$$ P(N\gt n)=1-\frac{m!}{m^n}\stir nm\;, $$

que puede derivarse de manera muy similar: Hay $m^n$ secuencias de longitud $n$ Elija una de las siguientes opciones $\stir nm$ particiones en $m$ subconjuntos no vacíos y uno de $m!$ asignaciones de los tipos de cupones a los subconjuntos.

Entonces

\begin{align} E[N]={}&\sum_{n=0}^\infty P(N\gt n)\\ ={}&\sum_{n=0}^\infty\left(1-\frac{m!}{m^n}\stir nm\right)\\ ={}&\sum_{n=0}^\infty\left(1-\frac{m!}{m^n}\frac1{m!}\sum_{j=0}^m(-1)^{m-j}\binom mjj^n\right)\\ ={}&\sum_{n=0}^\infty\frac1{m^n}\sum_{j=0}^{m-1}(-1)^{m-j+1}\binom mjj^n\\ ={}&\sum_{j=0}^{m-1}(-1)^{m-j+1}\binom mj\sum_{n=0}^\infty\frac{j^n}{m^n}\\ ={}&\sum_{j=1}^m(-1)^{j+1}\binom mj\sum_{n=0}^\infty\frac{(m-j)^n}{m^n}\\ ={}&\sum_{j=1}^m(-1)^{j+1}\binom mj\frac mj\\ ={}&-m\sum_{j=1}^m\int_0^{-1}\mathrm dq'\binom mjq'^{j-1}\\ ={}&-m\int_0^{-1}\mathrm dq'\sum_{j=1}^m\binom mjq'^{j-1}\\ ={}&-m\int_0^{-1}\mathrm dq'\frac{(1+q')^m-1}{q'}\\ ={}&-m\int_0^{-1}\mathrm dq'\frac{(1+q')^m-1}{(1+q')-1}\\ ={}&-m\int_0^{-1}\mathrm dq'\sum_{j=0}^{m-1}(-q')^j\\ ={}&-m\sum_{j=0}^{m-1}\int_0^{-1}\mathrm dq'(-q')^j\\ ={}&m\sum_{j=1}^m\frac1j\;. \end{align}

Le dejo a usted que decida si esto cuenta como "utilizar algún tipo de truco" :-)