Probabilidad de que el arreglo de Secret Santa resulte en emparejamientos perfectos

Entonces, teníamos a Secret Santa en el trabajo.

Somos 8 personas Cada uno se turnaba y sacaba un pequeño trozo de papel de un tazón con un nombre. La única regla: si sacas tu nombre, debes volver a poner el papel en el tazón e intentarlo de nuevo.

Llamemos a las personas A, B, C, D, E, F, G, H, que también es el orden en que eligieron su hoja de papel.

Hicimos el intercambio de regalos anoche.

A era el secreto de santa de F.
B era el secreto de E, santa.
C era el secreto de D, santa.
D era el secreto de santa de C.
E era el secreto de B santa.
F era el secreto de santa.
G era el secreto de H santa.
H era el secreto de santa de G.

¿Ves lo que pasó? Hicimos parejas.

A y F eran el secreto de santa de cada uno.
B y E eran el secreto santa del otro.
C y D eran la santa secreta del otro.
G y H eran el secreto de Santa.

¿Cuál es la probabilidad de que esto ocurra y cómo se calcula?

El número total de asignaciones entre personas, donde nadie se asigna a sí mismos, es (Estos se denominan trastornos ). ¡El valor está muy cerca de .$2n$

Si corresponden a emparejamientos perfectos, entonces son producto de transposiciones disjuntas . Esto implica que su estructura de ciclo es de la forma

El número de patrones distintos es el orden del grupo de todas las permutaciones de los nombres dividido por el orden del estabilizador del patrón. Un elemento estabilizador puede intercambiar cualquier número de pares y también puede permutar elpares, de donde hayElementos estabilizadores. Por lo tanto hay$2n$$n!$$2^n n!$

tales parejas.

Como todos estos emparejamientos perfectos son alteraciones, y todas las alteraciones son igualmente probables, la probabilidad es igual

Para personas, la respuesta exacta es, por lo tanto, mientras que la aproximación es : están de acuerdo con cinco cifras significativas.$2n=8$$15/2119 \approx 0.00707881$$e/(2^4\, 4!) \approx 0.00707886$

Para verificar, esta Rsimulación dibuja un millón de permutaciones aleatorias de ocho objetos, retiene solo aquellos que son trastornos y cuenta los que son emparejamientos perfectos. Produce su estimación, el error estándar de la estimación y una puntuación Z para compararlo con el valor teórico. Su salida es

       p.hat           se            Z 
 0.006981031  0.000137385 -0.711721705

La pequeña puntuación Z es consistente con el valor teórico. (Estos resultados serían consistentes con cualquier valor teórico entre y ).$0.0066$$0.0073$

paired <- function(x) crossprod(x[x] - 1:length(x))==0
good <- function(x) sum(x==1:length(x)) == 0

n <- 8
set.seed(17)
x <- replicate(1e6, sample(1:n, n))
i.good <- apply(x, 2, good)
i.paired <- apply(x, 2, paired)

n.deranged <- sum(i.good)
k.paired <- sum(i.good & i.paired)
p.hat <- k.paired / n.deranged
se <- sqrt(p.hat * (1-p.hat) / n.deranged)
(c(p.hat=p.hat, se=se, Z=(p.hat - 15/2119)/se))

Me impresionó bastante la elegancia en la respuesta de @whuber. Para ser sincero, tuve que familiarizarme mucho con los nuevos conceptos para seguir los pasos de su solución. Después de pasar mucho tiempo en ello, decidí publicar lo que obtuve. Entonces, lo que sigue es una nota exegética a su respuesta ya aceptada. De esta manera, no hay ningún intento de originalidad, y mi único objetivo es proporcionar algunos puntos de anclaje adicionales para seguir algunos de los pasos involucrados.

Así que aquí va ...

1. ¿Por qué ? $2n$Bueno, este puede ser demasiado básico: necesitamos un número par de personas para jugar.

2. ¿Podemos derivar la fórmula para los trastornos?

Siguiendo la entrada de Wikipedia con el ejemplo basado en la coincidencia de personas y sombreros , sombreros para ser precisos, tenemos que las opciones para la primera persona que recoge un sombrero se muestran aquí de la siguiente manera:$n$

$d(n)=(n-1)[d(n-2) + d(n-1)]=$

$=n\,d(n-2)-d(n-2)+n\,d(n-1)-d(n-1)$ , que se puede reorganizar como:

$d(n) - n\,d(n-1) = -[d(n-1)-(n-1)\,d(n-2)]$ .

Ahora notando el paralelismo entre el LHS de esta ecuación y la parte del RHS entre paréntesis, podemos continuar recursivamente:

$d(n) - n\,d(n-1)=-[d(n-1)-(n-1)\,d(n-2)] =$

$=(-1)^2\,[d(n-2)-(n-2)\,d(n-3)]=\cdots=(-1)^{n-2}\,d(2)-2\,d(1)$

Esto implica que .$d(n) = n\,d(n-1)+(-1)^n$

Trabajando al revés:

$d(2)=1$

$d(3)= 3\,d(2)-1 =3*1\,-1$

$d(4)= 4\,d(3)+1 =4*3*1\,-4\,\,+1$

$d(5)= 5\,d(4)-1 =5*4*3*1\,-5*4\,+5\,\,-1$

$d(6)= 6\,d(5)+1 = 6*5*4*3*1\,-6*5*4\,+6*5\,-6\,+1=$

$=6!\left(\frac{1}{2}- \frac{1}{3*2}+\frac{1}{4*3*2}-\frac{1}{5*4*3*2}+\frac{1}{6!}\right)=$

$=6!\left(\frac{1}{6!}-\frac{1}{5!}+\frac{1}{4!}-\frac{1}{3!}+\frac{1}{2!}-\frac{1}{1!}+1\right)$

Entonces en general,

$d(n)=n!\left(1-1+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}+\cdots+\frac{1}{n!}\right)$

Y recordando la serie Taylor de evaluada en :$e^x$$x=-1$

$d(n)\approx\frac{n!}{e}$

3. Transposición disjunta : El concepto de transposición es fácil de obtener desde el enlace proporcionado en la respuesta original , pero "disjunto" fue un poco menos claro. Mirando un ejemplo, del conjunto , la permutación se puede expresar como un ciclo como:, pero forma un bucle sobre sí mismo - un ciclo disjunto. O, juntando estos dos ciclos, la permutación se puede expresar como el producto .${a,b,c,d,e,f}$${b,d,a,c,f,e}$a -> b -> d -> c after which it returns to ae -> f$(\text {a b d c})(\text{e f})$

En la pregunta de Santa Claus (ocho empleados tienen nombres dibujados en pares perfectamente combinados: Anna le da un regalo a Martha, mientras que Martha ha dibujado el nombre de Anna) habrá circuitos cerrados.$4$

4. Para encontrar el número de bucles de dos elementos , necesitamos dividir todas las permutaciones posiblesdel conjunto de ocho ( ) personas por el número total posible de intercambios de dos elementos el número total de permutaciones de estos pares: .$(2n)!$$2n$$2^n$$n!$$p(2n) = \frac{(2n)!}{2^n n!}$

Para la Rsimulación:

1) paired <- function(x) crossprod(x[x] - 1:length(x))==0

Esta función se reduce a la comprensión x[x]: está destinada a evaluar un vector de elementos que representa las asignaciones actuales y determinar si está compuesto de bucles de 2 elementos, como en el problema de Santa Claus. Siempre que las permutaciones correspondan a elementos de transposición, de modo que si se suponía que Paul debía darle un regalo a Maria ( y viceversa ) y Max a John ( / ) inicialmente, la transposición resultante solo da como resultado un nuevo emparejamiento perfecto ( / y / ) Estamos cumpliendo la condición inicial de emparejamiento perfecto: $8$Paul -> MariaMaria -> PaulMax -> JohnJohn -> MaxMax -> MariaMaria -> MaxPaul -> JohnJohn -> Paul

En otras palabras, si volvemos al ejemplo de los sombreros en Wikipedia, la persona i siempre recupera el sombrero .$1$

2) good <- function(x) sum(x==1:length(x)) == 0

Esta función evalúa si estamos lidiando con un trastorno comparando el elemento del vector con el vector , 2, 3, 4, 5, , 7, 8 y asegurándose de que no haya coincidencia.( 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 $x$$(1,2,3,4,5,6,7,8)$

3.k.paired <- sum(i.good & i.paired) está ahí para excluir permutaciones emparejadas como la anterior en el diagrama, que no son alteraciones:

v <- c(1,2,3,4,5,6,7,8)
w <- c(1,2,3,5,4,6,7,8)

(c("is v paired?" = paired(v), "is w paired?" = paired(w),
   "is v a derang?" = good(w), "is w a derang?" = good(w)))

# not all paired permutations are derangements.