Coleccionista de cupones Problema con varias copias y X cantidad de cupones ya recogidos

Question

Tengo una variante del problema del recolector de cupones en la que hay $n$ cupones diferentes, que se sortean con igual probabilidad y con reemplazo, pero se necesitan 2 copias de cada cupón. Supongamos que tengo un total de $X$ número de cupones pertinentes recogidos del $2n$ número total de cupones para un juego completo, y quiere saber cuántos cupones extra innecesarios debe tener. ¿Cuál sería una ecuación para eso? He encontrado en Wikipedia una ecuación para el número de sorteos necesarios para obtener un juego completo de uno de cada cupón, y el número de sorteos necesarios para obtener un juego completo de múltiples copias de cada cupón.

$E(T) = n\log{n} + n + {\frac{1}{2}} + O({\frac{1}{n}})$ donde $\gamma \approx 0.5772156649$

$E(Tm) = n\log{n} + (m-1)n\log\log{n} + O(n)$ como $n$

Dónde $m$ es el número de ejemplares de cada cupón que hay que recoger, por tanto 2 en este caso, y $Tm$ es la primera vez $m$ copias de cada cupón.

También encontré esto en una pregunta anterior. Problema del coleccionista de cupones con X cantidad de cupones ya reunidos.

La probabilidad $p_i$ de seleccionar un nuevo cupón es igual a $\frac{n-i+1}{n}$ y el número esperado de extracciones necesarias para extraer un nuevo cupón es igual a $\frac{1}{p_i} = \frac{n}{n-i+1}$ . Por lo tanto, el valor esperado del tiempo necesario para extraer todos los $n$ los cupones pueden calcularse como:

$$E[T] = \frac{n}{n} + \frac{n}{n-1} + \ldots + \frac{n}{1} = n \sum_{k=1}^{n}{\frac{1}{k}}$$

En este caso, sin embargo, ya hemos extraído $X$ cupones únicos. Por ello, el número estimado de sorteos necesarios para encontrar todos los $n$ los cupones son iguales:

$$E[T] = E[t_{X+1}] + E[t_{X+2}] + \ldots + E[t_n] = n \sum_{k=1}^{n-X} \frac{1}{k}$$

Por tanto, para hallar el número total de cupones extraídos al recoger el $X^{th}$ cupón único, la ecuación sería $$n \sum_{k=1}^{n}{\frac{1}{k}}-n \sum_{k=1}^{n-X} \frac{1}{k} $$

El número total de cupones duplicados sólo innecesarios sería de $$n \sum_{k=1}^{n}{\frac{1}{k}}- n \sum_{k=1}^{n-X} \frac{1}{k} - X $$

No estoy seguro de cómo combinar estas dos ecuaciones, $E(Tm) = n\log{n} + (m-1)n\log\log{n} + O(n)$ como $n$ y $n \sum_{k=1}^{n}{\frac{1}{k}}-n \sum_{k=1}^{n-X} \frac{1}{k}$ , para obtener el número total de cupones sorteados al tener X número de cupones relevantes reunidos hacia una colección completa de 2 de cada cupón. A continuación, con esa ecuación sólo hay que restar X (el número de cupones relevantes recogidos) del número total para obtener el total de cupones innecesarios. Admitiré que no tengo una profesión matemática ni he hecho matemáticas de nivel superior últimamente, pero si he entendido bien la primera ecuación es más una aproximación del valor, mientras que la segunda ecuación es más exacta. Así que no estoy seguro de cómo combinarlas o si se pueden combinar fácilmente.

También entiendo un poco $O(n)$ y su uso, no estoy seguro de cómo introducirlo con el resto de la ecuación en wolframalpha o incluso Excel, el objetivo final de donde quiero usar esta ecuación. El número máximo de cupones sería de unos 100 si eso ayuda. Si sería más fácil, el número total de cupones que tienen sólo 1 copia y el número de cupones que tienen 2 copias recogidas podría ser utilizado como una entrada en lugar del número total de cupones pertinentes recogidos.

Answer 1

Lo que sigue es una contribución computacional en la que derivamos una forma cerrada (en lugar de una serie infinita) del número esperado de sorteos necesarios para ver todos los cupones al menos dos veces cuando un número $n'$ de cupones del $n$ tipos en los que $n' < n$ ya se han recogido en dos instancias. Observamos entonces que la expectativa no simplifica. Parece un reto gratificante calcular la asintóticas para estas expectativas utilizando métodos probabilísticos y compararlos con la forma cerrada que se presenta a continuación.

Utilizando la notación de este MSE enlace tenemos de primeros principios que

$$P[T = m] = \frac{1}{n^m}\times {n-n'\choose 1}\times (m-1)! [z^{m-1}] \exp(n'z) \left(\exp(z) - 1 - z\right)^{n-n'-1} \frac{z}{1}.$$

Nosotros verificar que se trata de una distribución de probabilidad . Obtenemos

$$\sum_{m\ge 2} P[T=m] \\ = (n-n') \sum_{m\ge 2} \frac{1}{n^m} (m-1)! [z^{m-2}] \exp(n'z) \left(\exp(z) - 1 - z\right)^{n-n'-1} \\ = (n-n') \frac{1}{n^2} \sum_{m\ge 0} \frac{1}{n^m} (m+1)! [z^{m}] \exp(n'z) \left(\exp(z) - 1 - z\right)^{n-n'-1} \\ = (n-n') \frac{1}{n^2} \sum_{m\ge 0} \frac{1}{n^m} (m+1)! [z^{m}] \exp(n'z) \\ \times \sum_{p=0}^{n-n'-1} {n-n'-1\choose p} \exp((n-n'-1-p)z) (-1)^{p} (1+z)^p \\ = (n-n') \frac{1}{n^2} \sum_{m\ge 0} \frac{1}{n^m} (m+1)! \\ \times [z^{m}] \sum_{p=0}^{n-n'-1} {n-n'-1\choose p} \exp((n-1-p)z) (-1)^{p} (1+z)^p \\ = (n-n') \frac{1}{n^2} \sum_{m\ge 0} \frac{1}{n^m} (m+1)! \\ \times \sum_{p=0}^{n-n'-1} {n-n'-1\choose p} \sum_{q=0}^{m} [z^{m-q}] \exp((n-1-p)z) (-1)^{p} [z^q] (1+z)^p \\ = (n-n') \frac{1}{n^2} \sum_{m\ge 0} \frac{1}{n^m} (m+1)! \\ \times \sum_{p=0}^{n-n'-1} {n-n'-1\choose p} \sum_{q=0}^{m} \frac{(n-1-p)^{m-q}}{(m-q)!} (-1)^{p} {p\choose q}.$$

Reorganizando el orden de las sumas se obtiene ahora

$$(n-n') \frac{1}{n^2} \sum_{p=0}^{n-n'-1} {n-n'-1\choose p} \\ \times \sum_{m\ge 0} \frac{1}{n^m} (m+1)! \sum_{q=0}^{m} \frac{(n-1-p)^{m-q}}{(m-q)!} (-1)^{p} {p\choose q} \\ = (n-n') \frac{1}{n^2} \sum_{p=0}^{n-n'-1} {n-n'-1\choose p} \\ \times \sum_{q\ge 0} (-1)^{p} {p\choose q} \sum_{m\ge q} \frac{1}{n^m} (m+1)! \frac{(n-1-p)^{m-q}}{(m-q)!}.$$

Simplificando la suma interna obtenemos

$$\frac{1}{n^q} \sum_{m\ge 0} \frac{1}{n^m} (m+q+1)! \frac{(n-1-p)^{m}}{m!} \\ = \frac{(q+1)!}{n^q} \sum_{m\ge 0} \frac{1}{n^m} {m+q+1\choose q+1} (n-1-p)^m \\ = \frac{(q+1)!}{n^q} \frac{1}{(1-(n-1-p)/n)^{q+2}} = (q+1)! n^2 \frac{1}{(p+1)^{q+2}}.$$

Obtenemos así para la suma de las probabilidades

$$\sum_{m\ge 2} P[T=m] = (n-n') \sum_{p=0}^{n-n'-1} {n-n'-1\choose p} (-1)^{p} \sum_{q=0}^p {p\choose q} (q+1)! \frac{1}{(p+1)^{q+2}}.$$

Repita para obtener instantáneamente para la expectativa

$$\bbox[5px,border:2px solid #00A000]{ E[T] = n (n-n') \sum_{p=0}^{n-n'-1} {n-n'-1\choose p} (-1)^{p} \sum_{q=0}^p {p\choose q} \frac{(q+2)!}{(p+1)^{q+3}}.}$$

Ahora para simplificarlos empezamos con la suma interna a partir de la probablidad utilizando el hecho de que

$$\sum_{q=0}^p {p\choose q} (q+1)! \frac{1}{(p+1)^{q+1}} = 1$$

que se demostró con residuos en el enlace citado de la introducción. Obtenemos entonces

$$(n-n') \sum_{p=0}^{n-n'-1} {n-n'-1\choose p} \frac{(-1)^{p}}{p+1} \\ = \sum_{p=0}^{n-n'-1} {n-n'\choose p+1} (-1)^p = - \sum_{p=1}^{n-n'} {n-n'\choose p} (-1)^p \\ = 1 - \sum_{p=0}^{n-n'} {n-n'\choose p} (-1)^p = 1 - (1-1)^{n-n'} = 1$$

lo que confirma que se trata de una distribución de probabilidad. No intentaremos esta manipulación con la expectativa, ya que el cálculo real de la va cálculo de los valores indica que no se simplifica como anunciado anteriormente. Por ejemplo, estas son las expectativas para los pares $(2n', n'):$

$$4,11,{\frac {347}{18}},{\frac {12259}{432}}, {\frac {41129339}{1080000}},{\frac {390968681}{8100000}}, {\frac {336486120012803}{5717741400000}}, \ldots$$

y para los pares $(3n', n'):$

$${\frac {33}{4}},{\frac {12259}{576}},{\frac {390968681}{10800000}}, {\frac {2859481756726972261}{54646360473600000}}, \ldots$$

El lector que busque pruebas numéricas que confirmen la forma cerrada o aclaración adicional de la definición del problema utilizada se le pide que que consulte el siguiente programa sencillo en C cuya salida coincide con la en todos los casos examinados.

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <time.h>

int main(int argc, char \*\*argv)
{
  int n = 6 , np = 3, j = 3, trials = 1000; 

  if(argc >= 2){
    n = atoi(argv\[1\]);
  }

  if(argc >= 3){
    np = atoi(argv\[2\]);
  }

  if(argc >= 4){
    j = atoi(argv\[3\]);
  }

  if(argc >= 5){
    trials = atoi(argv\[4\]);
  }

  assert(1 <= n);
  assert(1 <= np && np < n);  
  assert(1 <= j);
  assert(1 <= trials);

  srand48(time(NULL));
  long long data = 0;

  for(int tind = 0; tind < trials; tind++){
    int seen = np; int steps = 0; 
    int dist\[n\];

    for(int cind = 0; cind < n; cind++){
      if(cind < np) 
        dist\[cind\] = j;
      else
        dist\[cind\] = 0;
    }

    while(seen < n){
      int coupon = drand48() \* (double)n;

      steps++;

      if(dist\[coupon\] == j-1)
        seen++;
      dist\[coupon\]++;
    }

    data += steps;
  }

  long double expt = (long double)data/(long double)trials;
  printf("\[n = %d, np = %d, j = %d, trials = %d\]: %Le\\n", 
         n, np, j, trials, expt);

  exit(0);
}