Saltar al contenido principal

# 12.7: El problema del coleccionista de cupones

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$

( \newcommand{\kernel}{\mathrm{null}\,}\) $$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\id}{\mathrm{id}}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\kernel}{\mathrm{null}\,}$$

$$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$

$$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$

$$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\avec}{\mathbf a}$$ $$\newcommand{\bvec}{\mathbf b}$$ $$\newcommand{\cvec}{\mathbf c}$$ $$\newcommand{\dvec}{\mathbf d}$$ $$\newcommand{\dtil}{\widetilde{\mathbf d}}$$ $$\newcommand{\evec}{\mathbf e}$$ $$\newcommand{\fvec}{\mathbf f}$$ $$\newcommand{\nvec}{\mathbf n}$$ $$\newcommand{\pvec}{\mathbf p}$$ $$\newcommand{\qvec}{\mathbf q}$$ $$\newcommand{\svec}{\mathbf s}$$ $$\newcommand{\tvec}{\mathbf t}$$ $$\newcommand{\uvec}{\mathbf u}$$ $$\newcommand{\vvec}{\mathbf v}$$ $$\newcommand{\wvec}{\mathbf w}$$ $$\newcommand{\xvec}{\mathbf x}$$ $$\newcommand{\yvec}{\mathbf y}$$ $$\newcommand{\zvec}{\mathbf z}$$ $$\newcommand{\rvec}{\mathbf r}$$ $$\newcommand{\mvec}{\mathbf m}$$ $$\newcommand{\zerovec}{\mathbf 0}$$ $$\newcommand{\onevec}{\mathbf 1}$$ $$\newcommand{\real}{\mathbb R}$$ $$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$$ $$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$$ $$\newcommand{\bcal}{\cal B}$$ $$\newcommand{\ccal}{\cal C}$$ $$\newcommand{\scal}{\cal S}$$ $$\newcommand{\wcal}{\cal W}$$ $$\newcommand{\ecal}{\cal E}$$ $$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$$ $$\newcommand{\gray}[1]{\color{gray}{#1}}$$ $$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$$ $$\newcommand{\rank}{\operatorname{rank}}$$ $$\newcommand{\row}{\text{Row}}$$ $$\newcommand{\col}{\text{Col}}$$ $$\renewcommand{\row}{\text{Row}}$$ $$\newcommand{\nul}{\text{Nul}}$$ $$\newcommand{\var}{\text{Var}}$$ $$\newcommand{\corr}{\text{corr}}$$ $$\newcommand{\len}[1]{\left|#1\right|}$$ $$\newcommand{\bbar}{\overline{\bvec}}$$ $$\newcommand{\bhat}{\widehat{\bvec}}$$ $$\newcommand{\bperp}{\bvec^\perp}$$ $$\newcommand{\xhat}{\widehat{\xvec}}$$ $$\newcommand{\vhat}{\widehat{\vvec}}$$ $$\newcommand{\uhat}{\widehat{\uvec}}$$ $$\newcommand{\what}{\widehat{\wvec}}$$ $$\newcommand{\Sighat}{\widehat{\Sigma}}$$ $$\newcommand{\lt}{<}$$ $$\newcommand{\gt}{>}$$ $$\newcommand{\amp}{&}$$ $$\definecolor{fillinmathshade}{gray}{0.9}$$
$$\newcommand{\P}{\mathbb{P}}$$$$\newcommand{\E}{\mathbb{E}}$$$$\newcommand{\R}{\mathbb{R}}$$$$\newcommand{\N}{\mathbb{N}}$$$$\newcommand{\bs}{\boldsymbol}$$$$\newcommand{\var}{\text{var}}$$$$\newcommand{\cov}{\text{cov}}$$$$\newcommand{\cor}{\text{cor}}$$

## Teoría Básica

### Definiciones

En esta sección, nuestro experimento aleatorio consiste en muestrear repetidamente, con reemplazo, de la población$$D = \{1, 2, \ldots, m\}$$. Esto genera una secuencia de variables aleatorias independientes$$\bs{X} = (X_1, X_2, \ldots)$$, cada una distribuida uniformemente en$$D$$

A menudo interpretaremos el muestreo en términos de un coleccionista de cupones: cada vez que el coleccionista compra un determinado producto (chicle o Cracker Jack, por ejemplo) recibe un cupón (una tarjeta de béisbol o un juguete, por ejemplo) que es igualmente probable que sea cualquiera de los$$m$$ tipos. Así, en esta configuración,$$X_i \in D$$ se encuentra el tipo de cupón recibido en la compra$$i$$ th.

Dejar$$V_n$$ denotar el número de valores distintos en las primeras$$n$$ selecciones, para$$n \in \N_+$$. Esta es la variable aleatoria estudiada en la última sección sobre el Problema del Cumpleaños. Nuestro interés es en esta sección es el tamaño de muestra necesario para obtener un número específico de valores de muestra distintos

Para$$k \in \{1, 2, \ldots, m\}$$, deje que$W_k = \min\{n \in \N_+: V_n = k\}$ el tamaño de muestra necesario para obtener valores de muestra$$k$$ distintos.

En términos del recopilador de cupones, esta variable aleatoria da el número de productos requeridos para obtener$$k$$ distintos tipos de cupones. Tenga en cuenta que el conjunto de valores posibles de$$W_k$$ es$$\{k, k + 1, \ldots\}$$. Nos interesará particularmente$$W_m$$, el tamaño muestral necesario para obtener toda la población. En cuanto al recolector de cupones, esta es la cantidad de productos requeridos para obtener todo el conjunto de cupones.

En el experimento de colector de cupones, ejecute el experimento en modo de un solo paso varias veces para valores seleccionados de los parámetros.

Ahora encontremos la distribución de$$W_k$$. Los resultados de la sección anterior serán de gran ayuda

Para$$k \in \{1, 2, \ldots, m\}$$, la función de densidad de probabilidad de$$W_k$$ viene dada por$\P(W_k = n) = \binom{m-1}{k-1} \sum_{j=0}^{k-1} (-1)^j \binom{k - 1}{j} \left(\frac{k - j - 1}{m}\right)^{n-1}, \quad n \in \{k, k + 1, \ldots\}$

Prueba

Tenga en cuenta primero que$$W_k = n$$ si y solo si$$V_{n-1} = k - 1$$ y$$V_n = k$$. De ahí que el$\P(W_k = n) = \P(V_{n-1} = k - 1) \P(V_n = k \mid V_{n-1} = k - 1) = \frac{m - k + 1}{m} \P(V_{n-1} = k - 1)$ uso del PDF$$V_{n-1}$$ de la sección anterior da el resultado.

En el experimento de colector de cupones, varíe los parámetros y anote la forma y posición de la función de densidad de probabilidad. Para valores seleccionados de los parámetros, ejecute el experimento 1000 veces y compare la función de frecuencia relativa con la función de densidad de probabilidad.

Un enfoque alternativo a la función de densidad de probabilidad de$$W_k$$ es a través de una fórmula de recursión.

Para fijo$$m$$, vamos$$g_k$$ denotar la función de densidad de probabilidad de$$W_k$$. Entonces

1. $$g_k(n + 1) = \frac{k-1}{m} g_k(n) + \frac{m - k + 1}{m} g_{k-1}(n)$$
2. $$g_1(1) = 1$$

### La descomposición como una suma

Ahora mostraremos que se$$W_k$$ puede descomponer como una suma de variables aleatorias$$k$$ independientes, distribuidas geométricamente. Esto proporcionará una visión adicional de la naturaleza de la distribución y facilitará el cálculo de la media y la varianza.

Para$$i \in \{1, 2, \ldots, m\}$$, vamos a$$Z_i$$ denotar el número de muestras adicionales necesarias para pasar de valores$$i - 1$$ distintos a valores$$i$$ distintos. Entonces$$\bs{Z} = (Z_1, Z_2, \ldots, Z_m)$$ es una secuencia de variables aleatorias independientes, y$$Z_i$$ tiene la distribución geométrica on$$\N_+$$ con parámetro$$p_i = \frac{m - i + 1}{m}$$. Por otra parte,$W_k = \sum_{i=1}^k Z_i, \quad k \in \{1, 2, \ldots, m\}$

Este resultado muestra claramente que cada vez que se obtiene un nuevo cupón, se vuelve más difícil obtener el siguiente cupón nuevo.

En el experimento de colector de cupones, ejecute el experimento en modo de un solo paso varias veces para valores seleccionados de los parámetros. En particular, prueba esto con$$m$$ grande y$$k$$ cerca$$m$$.

### Momentos

La descomposición como suma de variables independientes proporciona una manera fácil de calcular la media y otros momentos de$$W_k$$.

La media y varianza del tamaño muestral necesario para obtener valores$$k$$ distintos son

1. $$\E(W_k) = \sum_{i=1}^k \frac{m}{m - i + 1}$$
2. $$\var(W_k) = \sum_{i=1}^k \frac{(i - 1)m}{(m - i + 1)^2}$$
Prueba

Estos resultados se derivan de la descomposición de$$W_k$$ como suma de variables independientes y resultados estándar para la distribución geométrica, ya que$$\E(W_k) = \sum_{i=1}^k \E(Z_i)$$ y$$\var(W_k) = \sum_{i=1}^k \var(Z_i)$$.

En el experimento del colector de cupones, varíe los parámetros y anote la forma y ubicación de la barra de desviación$$\pm$$ estándar media. Para valores seleccionados de los parámetros, ejecute el experimento 1000 veces y compare la media de la muestra y la desviación estándar con la media de distribución y la desviación estándar.

La función de generación de probabilidad de$$W_k$$ viene dada por$\E\left(t^{W_k}\right) = \prod_{i=1}^k \frac{m - i + 1}{m - (i - 1)t}, \quad \left|t\right| \lt \frac{m}{k - 1}$

Prueba

Esto se desprende de la descomposición de$$W_k$$ como suma de variables independientes y resultados estándar para la distribución geométrica en$$\N_+$$, ya que$$\E\left(t^{W_k}\right) = \prod_{i=1}^k \E\left(t^{Z_i}\right)$$.

## Ejemplos y Aplicaciones

Supongamos que las personas son muestreadas al azar hasta que se obtienen 40 cumpleaños distintos. Encuentra cada uno de los siguientes:

1. La función de densidad de probabilidad del tamaño de la muestra.
2. La media del tamaño de la muestra.
3. La varianza del tamaño de la muestra.
4. La función de generación de probabilidad del tamaño de la muestra.
Contestar

Dejar$$W$$ denotar el tamaño de la muestra.

1. $$\P(W = n) = \binom{364}{n} \sum_{j=0}^{30} (-1)^j \binom{39}{j} \left(\frac{39-j}{365}\right)^{n-1}$$para$$n \in \{40, 41, \ldots\}$$
2. $$\E(W) = 42.3049$$
3. $$\var(W) = 2.4878$$
4. $$\E\left(t^W\right) = \prod_{i=1}^{40} \frac{366-i}{365-(i-1)t}$$para$$|t| \lt \frac{365}{39}$$

Supongamos que se lanza un dado estándar, justo hasta que se hayan producido los 6 puntajes. Encuentra cada uno de los siguientes:

2. La media del número de lanzamientos.
3. La varianza del número de lanzamientos.
4. La probabilidad de que se requieran al menos 10 lanzamientos.
Contestar

Vamos a$$W$$ denotar el número de lanzamientos.

1. $$\P(W = n) = \sum_{j=0}^5 (-1)^j \binom{5}{j} \left(\frac{5 -j}{6}\right)^{n-1}$$para$$n \in \{6, 7, \ldots\}$$
2. $$\E(W) = 14.7$$
3. $$\var(W) = 38.99$$
4. $$\P(W \ge 10) = \frac{1051}{1296} \approx 0.81096$$

Una caja de cierta marca de cereal viene con un juguete especial. Hay 10 juguetes diferentes en total. Una coleccionista compra cajas de cereal hasta que tiene los 10 juguetes. Encuentra cada uno de los siguientes:

Dejar$$W$$ denotar el número de cajas compradas.
1. $$\P(W = n) = \sum_{j=0}^9 (-1)^j \binom{9}{j} \left(\frac{9-j}{10}\right)^{n-1}$$, para$$n \in \{10, 11, \ldots\}$$
2. $$\E(W) = 29.2897$$
3. $$\var(W) = 125.6871$$
4. $$\P(W \le 15) = 0.04595$$