Número esperado de calcetines individuales cuando se combinan los calcetines

Question

Cada vez que reviso la gran pila de calcetines que acaban de pasar por la lavandería y tengo que encontrar los pares iguales, suelo hacerlo como si fuera un simple autómata:

Elijo un calcetín al azar, y veo si coincide con alguno de los calcetines individuales que elegí antes y que aún no han encontrado una coincidencia. Si coincide, doblo los dos calcetines y los pongo en la pila de "hechos"; si no, añado el calcetín individual a la pila de calcetines individuales "que aún no coinciden", y elijo otro calcetín al azar.

Así que, mientras hacía esto anoche, empecé a pensar en esto, y me imaginé que lo siguiente sería cierto: Se puede esperar que la pila de "no coincide todavía" crezca lentamente, hasta algún punto en algún lugar en el "medio" del proceso, después de lo cual la pila se reducirá gradualmente, y eventualmente volverá a bajar a $0$ . De hecho, mi intuición es que el número esperado de calcetines sueltos en función del número de calcetines recogidos hasta el momento, es una función simétrica, siendo el máximo cuando he recogido la mitad de los calcetines.

Así que mis preguntas son:

Con $n$ pares de calcetines, ¿cuál es el número esperado de calcetines sueltos que están en mi pila de "no coinciden todavía" después de haber elegido $k$ ¿Calcetines?

¿Es cierto que esta función es una función simétrica, y que el máximo es para $k=n$ ? (si es así, me imagino que debe haber una forma conceptual de ver el problema que haga que esto inmediatamente claro, sin usar ninguna fórmula... ¿qué es esa forma? Es que se me ocurre invertir el proceso).

Por supuesto, todo esto es asumiendo que hay $n$ pares de calcetines en total, y que no hay calcetines sueltos en el montón original, y aunque esto es algo que nunca parece aplicarse a la pila de calcetines que pasan por mi lavandería real, supongamos en aras de la simplicidad matemática que realmente sólo hay $n$ pares de calcetines.

Answer 1

El número esperado puede calcularse mediante la linealidad de la expectativa. Sea $E[n,k]$ denota la respuesta y deja que $\{X_i\}_{i=1}^n$ denotan la variable indicadora del $i^{th}$ par. Así, $X_i=1$ si exactamente un miembro de la $i^{th}$ par ha sido elegido en su $k$ ensayos, y $X_i=0$ de lo contrario. Es fácil ver que $$E[X_i]=2\times \frac k{2n}\times \left(1-\frac {k-1}{2n-1}\right)$$ de lo que se deduce que $$E[n,k]=E\left[\sum X_i\right] =\sum E[X_i]= k\times \left(1-\frac {k-1}{2n-1}\right)$$

Comprobación de cordura: $k=1\implies E[n,1]=1$ como debería. También $k=2n\implies E[n,2n]=0$ como debería.

Observación: se ve fácilmente que esta función se maximiza con $k=n$ confirmando su intuición. También la expresión se puede escribir como $$E[n,k]=\frac {k(2n-k)}{2n-1}$$ que es simétrica bajo el intercambio de $k,2n - k$ también de acuerdo con sus expectativas.

Observación: más fuertemente, está claro que en cualquier momento el número de calcetines no emparejados en una pila es el mismo que el número en la otra pila (de hecho son exactamente los mismos pares de calcetines los que se reparten entre las pilas). Esto justifica claramente la simetría.

Answer 2

Podemos verificar la respuesta aceptada utilizando la metodología de este MSE enlace donde vemos que el problema es muy similar a un recolector de cupones sin sustitución y dos instancias de $n$ tipos de cupones. Supongamos que tenemos $j$ instancias. Comience preguntando por la probabilidad de obtener la siguiente distribución de cupones:

$$\prod_{q=1}^n C_q^{\alpha_a}$$

donde $\alpha_q$ dice que tenemos tantas instancias del tipo $q$ y es como máximo $j.$ Obtenemos de los primeros principios la probabilidad

$$\frac{(nj-\sum_{q=1}^n \alpha_q)!}{(nj)!} \prod_{q=1}^n \frac{j!}{(j-\alpha_q)!}.$$

Ahora bien, cuando multiplicamos una probabilidad por el número total de sucesos obtenemos los sucesos favorables. Por lo tanto, el FEAG para un tipo de cupón determinado es

$$\sum_{k=0}^j \frac{j!}{(j-k)!} \frac{z^k}{k!} = \sum_{k=0}^j {j\choose k} z^k = (1+z)^j.$$

Con $j=2$ y $n$ tipos de cupones que recibimos

$$m! [z^m] (1+z)^{2n}$$

y pidiendo el recuento total después de $m$ los cupones se han sorteado los rendimientos

$$m! \times {2n\choose m}.$$

Colocando un marcador en los singletons encontramos

$$m! [z^m] \left.\frac{\partial}{\partial u} (1+2uz+z^2)^n\right|_{u=1} \\ = m! [z^m] \; \left. n \times (1+2uz+z^2)^{n-1} \times 2z \right|_{u=1} \\ = m! [z^m ] 2nz (1+z)^{2n-2} \\ = m! \times 2n {2n-2\choose m-1}.$$

Dividir para obtener la expectativa

$$ {2n\choose m}^{-1} 2n {2n-2\choose m-1} = 2n \frac{m! \times (2n-m)!}{(2n)!} \frac{(2n-2)!}{(m-1)! \times (2n-m-1)!} \\ = 2n \times m \times (2n-m) \frac{1}{(2n)(2n-1)} \\ = \frac{m\times (2n-m)}{2n-1}.$$

Answer 3

Si dejas que tu función que da el número esperado de calcetines en tu pila de "no coincide todavía" tome $k$ y $2n-k$ como argumentos, es decir

$$f\,=\,f(k,\,2n-k),$$

será simétrico . La pila de "no coincide todavía" es sólo el subconjunto de todos los $k$ calcetines que han sido elegidos que tienen su calcetín a juego entre todos $2n-k$ calcetines que aún no han sido recogidos.

Por lo tanto, podemos hacer la siguiente reinterpretación de $f$ :

Fuera de $n$ pares de calcetines, $f(a,\,b)$ , donde $a+b=2n$ es el número esperado de pares de calcetines para los que los dos calcetines del par acaban en montones diferentes cuando todos $2n$ los calcetines se dividen aleatoriamente en dos montones de tallas $a$ y $b$ respectivamente.

Como las pilas no tienen ningún orden, el orden de los argumentos a $f$ que son sólo los tamaños de las pilas, no importa. Por lo tanto, $f$ es simétrica.