Probabilidad de amigo secreto

Question

1. 26 personas colocaron su nombre en un sombrero.
2. Cada persona saca un nombre del sombrero para comprar un regalo.
3. Si una persona se saca a sí misma, vuelve a colocar el nombre en el sombrero.

¿Cuál es la probabilidad de que la última persona se saque a sí misma?

¡Solo pregunto esto porque acaba de suceder!

Answer 1

No tengo una respuesta exacta, pero un enfoque de Monte Carlo muestra que la probabilidad de que la última persona elija su propio nombre es aproximadamente 0.03351 (intervalo de confianza del 95% 0.03316 a 0.03386).

Sería un error simplemente contar las posibles secuencias de selecciones y dividir el número de casos en los que la última persona elige su propio nombre por el número total de secuencias, como en la solución propuesta por Arthur. La razón es que las secuencias no son igualmente probables. Por ejemplo, en el caso de tres personas, la primera persona puede elegir entre 2 o 3, cada uno con una probabilidad de 1/2. Si elige un 2, la segunda persona puede elegir un 1 o un 3, cada uno con una probabilidad de 1/2. Pero si la primera persona elige un 3, la segunda persona debe elegir un 1. Entonces, las secuencias (2,1,3) y (2,3,1) tienen cada una una probabilidad de 1/4, mientras que la secuencia (3,1,2) tiene una probabilidad de 1/2.

Aquí hay una función en Python que simula el proceso. Las personas están numeradas del 0 al npersons-1 para mayor comodidad en la programación. (La versión de Python utilizada fue la 2.7.1).

import random

def draw\_gifts(npersons, ntrials):
    "Simular el sorteo de regalos con npersonas, ntrials veces; devolver el número de fallos"
    nfail = 0
    for t in range(ntrials):
        hat = \[i for i in range(npersons)\]
        for i in range(npersons-1):
            # la persona i elige de la bolsa
            # hat\[0\]..hat\[i-1\] contienen números ya elegidos
            # hat\[i\]..hat\[npersons-1\] contienen números elegibles
            j = random.randint(i, npersons-1)
            # elegir de nuevo si es necesario
            while hat\[j\] == i:
                j = random.randint(i, npersons-1)
            temp = hat\[i\]
            hat\[i\] = hat\[j\]
            hat\[j\] = temp
        if hat\[npersons-1\] == npersons-1:
            nfail += 1
    return nfail    

Si la semilla del generador de números aleatorios se establece primero en 1234 a través de "random.seed(1234)" y la función anterior se invoca a través de "draw_gifts(26, 1000000)" (simulando 26 personas y 10^6 intentos), el número de fallos devuelto, es decir, los casos en los que la última persona elige su propio número, es 33508. Una fórmula estadística estándar para un intervalo de confianza sobre proporciones, basada en una aproximación normal, produce un intervalo de confianza del 95% de 0.03316 a 0.03386 para la probabilidad de fallo. Ver http://en.wikipedia.org/wiki/Binomial_proportion_confidence_interval.

Answer 2

Después de que las primeras $25$ personas hayan elegido nombres, hay dos posibilidades:

$\bullet$ Tenemos un desorden de los primeros $25$ nombres, en este caso la última persona elige su propio nombre.
$\bullet$ La última persona elige el nombre de otra persona, y luego obtenemos un desorden de todos los nombres.

El número de desordenes de $n$ objetos es igual a $\left[ \frac{n!}{e}\right]$ (ver enlace), por lo que la probabilidad de que la última persona elija su propio nombre es igual a $$\frac{\left[ \frac{25!}{e}\right]}{\left[ \frac{25!}{e}\right] + \left[ \frac{26!}{e}\right]} = \frac{5706255282633466762357224}{154068892631103602583645049} \approx \frac{1}{27} - 2.4 \cdot 10^{-28}$$