Observación preliminar. Esta respuesta fue escrito originalmente para el tratamiento de
el caso de ver la primera repetido valor cuando dibujo sin
la sustitución de una baraja de cartas que se propone en este MSE
enlace. Respuestas
el correspondiente caso de $n$ pares de calcetines, así como, sin embargo, consultar
al final del documento para esto.
Podemos resolver el problema en el que han $j$ instancias de cada uno de $n$ tipos de
de los cupones y dibujar sin sustitución, hasta que hemos visto $2$ cupones
de algún tipo. De una baraja de naipes tenemos $13$ tipos de cupones y
$4$ instancias de cada tipo. Usando la notación de la siguiente
MSE enlace que te pusey
MSE vínculo IInos
introducir el marcado de generación de función
$$\left(1 + j w z\right)^n.$$
El coeficiente de $[z^m]$ aquí representa la distribución de las secuencias de
de $m$ sorteos de la $n$ tipos de acuerdo a la probabilidad, donde la
que se producen una vez se han marcado. Cada uno de éstos podrá ser
aumentada a un par de color, donde el peso es $j-1$ porque
un cupón ya ha sido dibujada. Como sólo necesitamos el conteo nos
diferenciar con respecto a $w$ y establezca $w=1$, al pasar
$$n\times \left(1 + jz\right)^{n-1}
\times j z.$$
Con el método de los enlaces de los posts de este modo, obtener la
probabilidad
$$P[T = m] = \frac{1}{m.} {nj\elegir m}^{-1}
(m-1)! \times (j-1) \times [z^{m-1}] n j z (1 + jz)^{n-1}
\\ = \frac{nj}{m} {nj\elegir m}^{-1} \times (j-1) \times
[z^{m-2}] (1 + jz)^{n-1}
\\ = \frac{nj}{m} {nj\elegir m}^{-1} \times (j-1) \times
{n-1\elegir m-2} j^{m-2}
\\ = (j-1) \times {nj-1\elegir m-1}^{-1}
{n-1\elegir m-2} j^{m-2}.$$
A continuación podemos comprobar que esta es una distribución de probabilidad.El
el proceso puede detenerse después de dos pasos en los primeros y $n+1$ en el
más reciente y obtenemos
$$\sum_{m=2}^{n+1} P[T=m] =
(j-1) \sum_{m=2}^{n+1} {nj-1\elegir m-1}^{-1}
{n-1\elegir m-2} j^{m-2}
\\ = (j-1) \sum_{m=2}^{n+1} {nj-1\elegir m-1}^{-1} \frac{m-1}{n}
{n\elegir m-1} j^{m-2}
\\ = \frac{j-1}{n} \sum_{m=2}^{n+1} {nj-1\elegir m-1}^{-1}
{n\elegir m-1} (m-1) j^{m-2}.$$
Tenemos
$${nj-1\elegir m-1}^{-1}
{n\elegir m-1} = \frac{n!\veces (nj-m)!}{(nj-1)!\veces (n-(m-1))!}
\\ = {nj-1\elegir n}^{-1} {nj-m\elegir n-(m-1)}.$$
Aquí hemos utilizado el hecho de que para el escenario para dar sentido debemos
ha $j\ge 2.$ Continuar encontramos
$$\frac{j-1}{n} {nj-1\elegir n}^{-1}
\sum_{m=2}^{n+1} {nj-m\elegir n-(m-1)} (m-1) j^{m-2}$$
La suma plazo de los rendimientos de
$$\sum_{m=1}^{n} {nj-1-m\elegir n-m} m j^{m-1}
= \sum_{m\ge 1} [w^{n-m}] (1+w)^{nj-1-m} m j^{m-1}
\\ = [w^n] (1+w)^{nj-1}
\sum_{m\ge 1} w^m (1+w)^{m} m j^{m-1}
\\ = [w^n] (1+w)^{nj-1} \frac{w}{(1+w)}
\sum_{m\ge 1} w^{m-1} (1+w)^{-(m-1)} m j^{m-1}
\\ = [w^n] (1+w)^{nj-1} \frac{w}{(1+w)} \frac{1}{(1-wj/(1+w))^2}
\\ = [w^{n-1}] (1+w)^{nj} \frac{1}{(1+w-wj)^2}
= [w^{n-1}] (1+w)^{nj} \frac{1}{(1-(j-1)w)^2}.$$
La extracción de los coeficientes encontramos
$$\sum_{q=0}^{n-1} {nj\elegir n-1-p} (q+1) (j-1)^q
= \sum_{q=0}^{n-1} {nj\elegir nj-n+p+1} (q+1) (j-1)^q
\\ = nj \sum_{q=0}^{n-1} {nj-1\elegir nj-n+p} (j-1)^q
- n(j-1) \sum_{q=0}^{n-1} {nj\elegir nj-n+p+1} (j-1)^q
\\ = n \sum_{q=0}^{n-1} {nj-1\elegir nj-n+p} (j-1)^{q+1}
n + \sum_{q=0}^{n-1} {nj-1\elegir nj-n+p} (j-1)^q
\\ - n \sum_{q=0}^{n-1} {nj\elegir nj-n+p+1} (j-1)^{q+1}
\\ = n \sum_{q=0}^{n-1} {nj-1\elegir nj-n+p} (j-1)^{q+1}
n + \sum_{q=-1}^{n-2} {nj-1\elegir nj-n+p+1} (j-1)^{q+1}
\\ - n \sum_{q=0}^{n-1} {nj\elegir nj-n+p+1} (j-1)^{q+1}
\\ = n \sum_{q=0}^{n-1} {nj-1\elegir nj-n+p} (j-1)^{q+1}
n + \sum_{q=0}^{n-1} {nj-1\elegir nj-n+p+1} (j-1)^{q+1}
\\ + n {nj-1\elegir nj-n}
- n \sum_{q=0}^{n-1} {nj\elegir nj-n+p+1} (j-1)^{q+1}
= n {nj-1\elegir nj-n}.$$
La recopilación de todo lo que obtenemos
$$\frac{j-1}{n} {nj-1\elegir n}^{-1}
\n \times {nj-1\elegir n-1}
\\ = \frac{j-1}{n} {nj-1\elegir n}^{-1}
\n \times {nj-1\elegir n} \frac{n}{nj-n}
= 1$$
y nos han confirmado que tenemos una distribución de probabilidad.
El siguiente paso es calcular la expectativa. Recapitulación de las anteriores
el cálculo nos encontramos con que
$$E[T] = \sum_{m=2}^{n+1} m P[T=m]
= \frac{j-1}{n} {nj-1\elegir n}^{-1}
\sum_{m=1}^{n} {nj-1-m\elegir n-m} (m+1) m j^{m-1}$$
o
$$\bbox[5px,border:2px solid #00A000]{
E[T] = \frac{2(j-1)}{n} {nj-1\elegir n}^{-1}
[w^{n-1}] (1+w)^{nj+1} \frac{1}{(1-(j-1)w)^3}.}$$
La extracción de los coeficientes obtenemos la forma cerrada
$$\bbox[5px,border:2px solid #00A000]{
E[T] = \frac{(j-1)}{n} {nj-1\elegir n}^{-1}
\sum_{q=0}^{n-1} {nj+1\elegir n-1-p} (q+2)(p+1) (j-1)^q.}$$
Observe que para una baraja de cartas tenemos
$$E[T] = {\frac {226087256246}{39688347475}} \approx 5.696565129.$$
Además de esta forma se simplifica al $j=2$ (pares de
calcetines). Crear instancias de $j$ $2$va a producir
$$\frac{2}{n} {2n-1\elegir n}^{-1}
[w^{n-1}] (1+w)^{2n+1} \frac{1}{(1-w)^3}.$$
El coeficiente es
$$\mathrm{Res}_{w=0} \frac{1}{w^n} (1+w)^{2n+1} \frac{1}{(1-w)^3}.$$
Tenga en cuenta que el residuo en el infinito está dada por
$$- \mathrm{Res}_{w=0} \frac{1}{w^2} w^n \frac{(1+w)^{2n+1}}{w^{2n+1}}
\frac{1}{(1-1/w)^3}
= - \mathrm{Res}_{w=0} \frac{1}{w^2} \frac{(1+w)^{2n+1}}{w^{n+1}}
\frac{w^3}{(w-1)^3}
\\ = \mathrm{Res}_{w=0} \frac{(1+w)^{2n+1}}{w^{n}}
\frac{1}{(1-w)^3}.$$
Por lo tanto el valor es menos de la mitad de los residuos en $w=1$. Nos encontramos
con $(1-w)^3 = - (w-1)^3$
$$\frac{1}{2} \times \frac{1}{2} \left.\frac{1}{w^n} (1+w)^{2n+1}
\left(\frac{n(n+1)}{w^2} - \frac{2n(2n+1)}{w (1+w)}
+ \frac{(2n+1)(2n)}{(1+w)^2}\right)\right|_{w=1}
\\ = 2^{2n-1} \left(n^2+n - 2n^2-n + n^2 + \frac{1}{2} n\right)
= \frac{1}{4} n 4^n.$$
Ahora observar que
$${2n-1\elegir n}^{-1} = {2n\elegir n}^{-1} \times 2n \times
\frac{1}{n} = 2 {2n\elegir n}^{-1}
\sim 2 \times \frac{\sqrt{\pi n}}{4^n}$$
Así tenemos que la forma cerrada para $j=2$
$$\bbox[5px,border:2px solid #00A000]{
E[T] = {2n-1\elegir n}^{-1} \frac{1}{2} 4^n
= {2n\elegir n}^{-1} 4^n.}$$
y nos llevamos la agradable asintótica
$$\bbox[5px,border:2px solid #00A000]{
E[T] \sim \sqrt{\pi n}.}$$
También hay una muy básica programa en C que confirmó que la forma cerrada
de las expectativas para todas las combinaciones de $n$ $j$ que se
examinado. Por ejemplo, con $j=5$ tenemos las expectativas
$$2,{\frac {23}{9}},{\frac {272}{91}},{\frac {3253}{969}},
{\frac {6522}{1771}},{\frac {94477}{23751}},
{\frac {714436}{168113}},{\frac {69263329}{15380937}},\ldots$$
con los valores de
$$2, 2.555555556, 2.989010989, 3.357069143, 3.682665161,
\\ 3.977811461, 4.249736784, 4.503193076,\ldots $$
Ejecutando el programa en $10^8$ ensayos a continuación, coincide con estos valores
alrededor de cinco dígitos decimales de precisión.
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <time.h>
#include <string.h>
int main(int argc, char **argv)
{
int n = 6 , j = 3, ensayos = 1000;
if(argc >= 2){
n = atoi(argv[1]);
}
if(argc >= 3){
j = atoi(argv[2]);
}
if(argc >= 4){
ensayos = atoi(argv[3]);
}
assert(1 <= n);
assert(2 <= j);
assert(1 <= ensayos);
funciones srand48(time(NULL));
largo de larga data = 0;
for(int tind = 0; tind < ensayos; tind++){
int src[n*j];
for(int cind = 0; cind < n*j; cind++)
src[cind] = cind/j;
int hecho = 0; int pasos = 0;
int dist[n];
for(int cind = 0; cind < n; cind++)
dist[cind] = 0;
while(!done){
int cpidx = drand48() * (doble)(n*j-pasos);
int cupón = src[cpidx];
for(int cind=cpidx; cind < n*j-pasos-1; cind++)
src[cind] = src[cind+1];
pasos++;
dist[cupón]++;
si(dist[cupón] == 2)
hecho = 1;
}
datos += pasos;
}
long double expt = (long double)datos/(long double)los juicios;
printf ("n = %d, j = %d, ensayos = %d]: %Archivo\n",
n, j, ensayos, expt);
exit(0);
}
