Presentamos un problema inspirado en los trabajos de este MSE enlace . En En particular, consideramos un escenario de recaudación de cupones con $n$ cupones donde un número entero $1\le j\le n-1$ está dada. Introducimos dos variables aleatorias variables aleatorias, a saber $T$ y $Q$ donde $T$ representa el número de sorteos hasta que se hayan recogido todos los cupones y $Q$ el número de diferentes cupones que aparecieron en el primer $j$ sorteos. La siguiente conjetura se somete a su consideración.
$$\mathrm{E}\left[{T\choose Q}\right] = \sum_{k=1}^j \frac{n!}{n^{n-k-1+j}} \times {j\brace k} \sum_{r=0}^k {n+j-k\choose k-r} \\ \times \sum_{p=0}^{n-k-1} \frac{(-1)^{n-k-1-p}}{p! (n-k-1-p)!} \frac{(k+p)^{n-k-1+r}}{(n-k-p)^{r+1}}.$$
Tengo lo que creo que es una prueba, pero es bastante complicada. Nosotros proponemos la siguiente lista de preguntas sobre la identidad anterior:
-
¿se cumple realmente y tiene acaso una prueba directa usando métodos probabilísticos y hay una simplificación estructural
-
cuáles son las asintóticas, ¿hay estimaciones efectivas de estos términos que coincidan con los valores numéricos exactos de la fórmula sin tener que recurrir a una suma triple.
Se invita al lector a comparar las asíntotas potencialmente relevantes con los datos de la identidad.
Existe el siguiente programa en C, extremadamente básico (no es un juego de palabras), que incluyo aquí para ayudar a aclarar qué interpretación del problema se está utilizando. Compilado con GCC 4.3.2 y el std=gnu99 opción.
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <time.h>
#include <string.h>
long choose(long n, long k)
{
long num = 1, denom = 1;
while(k > 0){
num \*= n;
denom \*= k;
n--; k--;
}
return num/denom;
}
int main(int argc, char \*\*argv)
{
int n = 6 , j = 3, trials = 1000;
if(argc >= 2){
n = atoi(argv\[1\]);
}
if(argc >= 3){
j = atoi(argv\[2\]);
}
if(argc >= 4){
trials = atoi(argv\[3\]);
}
assert(1 <= n);
assert(1 <= j && j < n);
assert(1 <= trials);
srand48(time(NULL));
long long data = 0;
long genstats\[n\];
memset(genstats, 0, n\*sizeof(long));
for(int tind = 0; tind < trials; tind++){
int seen = 0; int steps = 0;
int dist\[n\], startseg\[n\];
for(int cind = 0; cind < n; cind++){
dist\[cind\] = 0; startseg\[cind\] = 0;
}
while(seen < n){
int coupon = drand48() \* (double)n;
genstats\[coupon\]++;
steps++;
if(steps <= j)
startseg\[coupon\]++;
if(dist\[coupon\] == 0)
seen++;
dist\[coupon\]++;
}
int stseen = 0;
for(int stcoup = 0; stcoup < n; stcoup++)
if(startseg\[stcoup\] > 0)
stseen++;
data += choose(steps, stseen);
}
long double expt = (long double)data/(long double)trials;
printf("\[n = %d, j = %d, trials = %d\]: %Le\\n",
n, j, trials, expt);
long long gentotal = 0;
for(int cind = 0; cind < n; cind++){
gentotal += genstats\[cind\];
}
for(int cind = 0; cind < n; cind++){
printf("%02d: %.8Le\\n", cind,
(long double)genstats\[cind\]
/(long double)gentotal);
}
exit(0);
}Adenda. Como comprobación de cordura cuando $j=1$ la fórmula debe producir $n H_n$ para $n\ge 2.$ De hecho, obtenemos
$$\frac{n!}{n^{n-1}} \left(n\times \sum_{p=0}^{n-2} \frac{(-1)^{n-2-p}}{p! (n-2-p)!} \frac{(1+p)^{n-2}}{n-1-p} + \sum_{p=0}^{n-2} \frac{(-1)^{n-2-p}}{p! (n-2-p)!} \frac{(1+p)^{n-1}}{(n-1-p)^2}\right).$$
Para la primera suma introducimos
$$f(z) = \frac{(1+z)^{n-2}}{n-1-z} \prod_{q=0}^{n-2} \frac{1}{z-q}$$
de modo que la suma viene dada por (los residuos suman cero)
$$\sum_{q=0}^{n-2} \mathrm{Res}_{z=q} f(z) = -\mathrm{Res}_{z=n-1} f(z) - \mathrm{Res}_{z=\infty} f(z).$$
La contribución del primer término es $$\frac{n^{n-2}}{(n-1)!}$$ y del segundo
$$\mathrm{Res}_{z=0} \frac{1}{z^2} \frac{(1+1/z)^{n-2}}{n-1-1/z} \prod_{q=0}^{n-2} \frac{1}{1/z-q} = \mathrm{Res}_{z=0} \frac{1}{z^n} \frac{(1+z)^{n-2}}{n-1-1/z} \prod_{q=0}^{n-2} \frac{z}{1-qz} \\ = \mathrm{Res}_{z=0} \frac{1}{z} \frac{(1+z)^{n-2}}{n-1-1/z} \prod_{q=0}^{n-2} \frac{1}{1-qz} = \mathrm{Res}_{z=0} \frac{(1+z)^{n-2}}{z(n-1)-1} \prod_{q=0}^{n-2} \frac{1}{1-qz} = 0.$$
Por lo tanto, la primera suma contribuye
$$\frac{n!}{n^{n-1}} \times n \frac{n^{n-2}}{(n-1)!} = n.$$
Para la segunda suma utilizamos
$$g(z) = \frac{(1+z)^{n-1}}{(n-1-z)^2} \prod_{q=0}^{n-2} \frac{1}{z-q} = \frac{(1+z)^{n-1}}{(z-(n-1))^2} \prod_{q=0}^{n-2} \frac{1}{z-q}.$$
Obtenemos para el negativo del residuo en $n-1$ el valor
$$-\left((1+z)^{n-1} \prod_{q=0}^{n-2} \frac{1}{z-q} \right)' _{z=n-1} \\ = -\left((n-1)(1+z)^{n-2} \prod_{q=0}^{n-2} \frac{1}{z-q} - (1+z)^{n-1} \prod_{q=0}^{n-2} \frac{1}{z-q} \sum_{q=0}^{n-2} \frac{1}{z-q}\right)_{z=n-1} \\ = - \left((n-1)n^{n-2} \frac{1}{(n-1)!} - n^{n-1} \frac{1}{(n-1)!} H_{n-1}\right).$$
Multiplicar por $n!/n^{n-1}$ para conseguir
$$n H_{n-1} - (n-1)n^{n-2} \frac{1}{(n-1)!} \frac{n!}{n^{n-1}} \\ = n H_{n-1} - (n-1)\frac{n}{n} = n H_{n-1} - (n-1).$$
Para el negativo del residuo en el infinito obtenemos
$$\mathrm{Res}_{z=0} \frac{1}{z^2} \frac{(1+1/z)^{n-1}}{(n-1-1/z)^2} \prod_{q=0}^{n-2} \frac{1}{1/z-q} = \mathrm{Res}_{z=0} \frac{1}{z^{n+1}} \frac{(1+z)^{n-1}}{(n-1-1/z)^2} \prod_{q=0}^{n-2} \frac{z}{1-qz} \\ = \mathrm{Res}_{z=0} \frac{1}{z^2} \frac{(1+z)^{n-1}}{(n-1-1/z)^2} \prod_{q=0}^{n-2} \frac{1}{1-qz} \\ = \mathrm{Res}_{z=0} \frac{(1+z)^{n-1}}{(z(n-1)-1)^2} \prod_{q=0}^{n-2} \frac{1}{1-qz} = 0.$$
Recogiendo todo lo que conseguimos
$$n H_{n-1} - (n-1) + n = n H_{n-1} + n \frac{1}{n}$$
o bien
$$\bbox[5px,border:2px solid #00A000]{n H_n}$$
y la comprobación de la cordura pasa. Obsérvese que evidentemente necesitamos algo más sofisticado para demostrar la identidad conjeturada, por ejemplo cuando $j=n-1.$ (Observación. No necesitamos aplicar realmente la fórmula para los residuos en el infinito, es suficiente cuando se trabaja con funciones racionales observar que tanto $f(z)$ y $g(z)$ tienen la diferencia entre el grado del denominador y del numerador igual a dos).
