Número esperado de auto-bucles.

Question

Usted tiene 100 cadena en una bolsa y al azar tire de un extremo de una cadena. De forma aleatoria sacar otro final y atarlos juntos. Hacer esto hasta que usted no tenga más extremos.

El número esperado de ciclos se $\sum_{i=1}^{n} \frac{1}{2n-1}$.

¿Cuál es el número esperado de auto bucles? (Las cadenas que están ligados a su propio fin.)

Mi opinión: La probabilidad de tener un auto loop con la primera cadena es 1/199. Por la linealidad de la expectativa, cada cadena tiene 1/199 probabilidad de formación de un auto loop, por lo que el número esperado de auto bucles es $100/199$.

Es esto correcto? Parece un número bajo, pero, de nuevo, usted tiene muchas cadenas y no es probable para tirar de su propio final.

Answer 1

Ok, creo que eres ahora.

Identificar el procedimiento mediante el etiquetado de cada extremo de la cuerda de 1 a 200. Digamos (1,2) identifica cadena 1, (3,4) identifica cadena 2, etc, (2k-1,2 k) identifica la cadena de k.

Podemos pensar en este procedimiento como la generación de una permutación de más de 200 elementos, y el emparejamiento de números. Específicamente, generar un ordenamiento al azar de los números del 1 al 200, y el procesamiento de la orden de izquierda a derecha, par los números juntos, lo que indica que los extremos están atados juntos.

Para calcular la probabilidad de que la cadena 1 es que va a terminar como una auto-loop, tenemos la probabilidad de que en la permutación, (1,2) está emparejado juntos.

Así, contar el número de maneras en (1,2) presenta de la siguiente manera: En primer lugar, 1 puede aparecer en una de las 200 máquinas tragaperras. Dada la ubicación de la 1, la 2 tiene que estar en la posición correcta (sólo 1 posibilidad) para la configuración para indicar que los extremos están atados juntos. Después de esto, las otras ranuras no importa, y hay 198! maneras de generar los. A continuación, la respuesta es 200*198! / 200! = 1/199.

Alternativamente, se puede seguir el proceso de generación de una permutación aleatoria, donde tenemos el primer lugar de 1 en uno de los 200 espacios y, a continuación, coloque 2 en uno de los restantes 199 ranuras, y el resto del proceso puede ser ignorado. La probabilidad de que 2 de las tierras en el lugar correcto para indicar los extremos 1 y 2 están atados juntos es 1/199.

El mismo razonamiento sirve para cualquier otra cadena $(2k-1,2k)$.

Answer 2

Si usted mira la probabilidad de la 2ª a la par de los extremos de la formación de una auto-loop, la probabilidad es $1/198$ si el primer par de extremos hecho un auto-loop (que había probabilidad de $1/199$), de lo contrario, si primero atado con dos cadenas (la probabilidad de $198/199$) entonces usted tiene que elegir uno de los $197/199$ extremos que no son parte de las dos cadenas atadas, y entonces usted tiene un $1/198$ oportunidad de hacer una auto-loop. Por lo que la probabilidad de la 2ª a la par de la formación de una auto-loop es

$$(1/199)(1/198) + (198/199)(197/199)(1/198) = (1/199)(1/198 + 197/199)$$

que es un poco más pequeño que el $1/199$. En general, teniendo en cuenta todos los casos posibles para el $k$th par de extremos formando un auto-lazo para $k > 2$ parece difícil de hacer con una fórmula, pero tal vez sea posible. Pero no, la expectativa general es no $100/199$, al menos no por argumentando a través de la linealidad de las expectativas.