Probabilidad que arreglo secreto Santa resultará en perfecto maridaje

Question

Así, tuvimos Santa Secreto en el trabajo.

Somos 8 personas. Cada uno de nosotros tomó vueltas y sacó un pequeño trozo de papel de un recipiente con un nombre. La única regla : Si usted tira de su nombre, usted tiene que poner el pedazo de papel de nuevo en el bol y volver a intentarlo.

Vamos a llamar a la gente a, B, C, D, E, F, G, H, que es también el orden en el que se recogen sus pedazo de papel.

Hicimos el intercambio de regalos de la noche anterior.

Una fue F s secret santa.
B E s secret santa.
C fue D s secret santa.
D C s secret santa.
E fue de B s secret santa.
F fue Un secret santa.
G H s secret santa.
H G s secret santa.

A ver lo que sucedió? Hemos hecho las parejas.

A y F eran del otro secreto de la santa.
B y E eran del otro secreto de la santa.
C y D fueron unos de otros s secret santa.
G y H fueron unos de otros s secret santa.

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

Answer 1

Es el número total de asignaciones entre $2n$ pueblo, donde nadie se asigna a sí mismos, $$d(2n) = (2n)!(1/2 - 1/6 + \cdots + (-1)^k/k! + \cdots + 1/(2n)!).$$ (These are called derangements.) The value is very close to $ (2n)! / e $.

If they correspond to perfect pairings, then they are a product of disjoint transpositions. This implies their cycle structure is of the form

$$(a_{11}a_{12})(a_{21}a_{22})\cdots(a_{n1}a_{n2}).$$

The number of distinct such patterns is the order of the group of all permutations of the $ 2n $ names divided by the order of the stabilizer of the pattern. A stabilizing element may swap any number of the pairs and it may also permute the $n #! $ pairs, whence there are $2 ^ n n!$ stabilizing elements. Therefore there are

$$p(2n) = \frac{(2n)!}{2^n n!}$$

such pairings.

Since all such perfect pairings are derangements, and all derangements are equally likely, the chance equals

$$\frac{p(2n)}{d(2n)} = \frac{1}{2^n n!(1 - 1/2 + 1/6 - \cdots + (-1)^k/k! + \cdots + 1/(2n)!)} \approx \frac{e}{2^n n!}.$$

For $2n=8$ people the exact answer therefore is $15/2119 \approx 0.00707881$ while the approximation is $e/(2^4\, 4!) \approx 0.00707886 $: they agree to five significant figures.

---

To check, this R simulation draws a million random permutations of eight objects, retains only those that are derangements, and counts those that are perfect pairings. It outputs its estimate, the standard error of the estimate, and a Z-score to compare it to the theoretical value. Its output is

       p.hat           se            Z 
 0.006981031  0.000137385 -0.711721705

The small Z-score is consistent with the theoretical value. (These results would be consistent with any theoretical value between $ 0.0066 $ and $ 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))

Answer 2

Yo estaba muy impresionado por la elegancia en @whuber respuesta. Para ser honesto, tuve que hacer un montón de familiarizar a mí mismo con nuevos conceptos para seguir los pasos de su solución. Después de pasar un montón de tiempo, me he decidido a publicar lo que tengo. Entonces lo que sigue es una nota exegética a su ya aceptado la respuesta. 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$? También ésta puede ser una forma muy básica: tenemos un número par de personas para jugar el juego.

2. Podemos obtener la fórmula para alteraciones?

Tras la entrada de la Wikipedia con el ejemplo basado en la coincidencia de las personas y los sombreros, $n$ sombreros para ser precisos, tenemos que las opciones para la primera persona a recoger un sombrero se muestra aquí como sigue:

$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 puede ser reorganizado como:

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

Ahora a notar el paralelismo entre el lado izquierdo de esta ecuación y la parte de la RHS, entre corchetes, podemos continuar de forma recursiva:

$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 hacia atrá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)$

Así que 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 de Taylor de $e^x$ evaluado en $x=-1$:

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

3. La desunión de transposición: El concepto de transposición, es fácil acceder desde el enlace proporcionado en la respuesta original, pero "separe" fue un poco menos clara. Mira un ejemplo, desde el ${a,b,c,d,e,f}$, la permutación ${b,d,a,c,f,e}$ puede ser expresado como un ciclo, como: a -> b -> d -> c after which it returns to a, pero e -> f forma un bucle sobre sí mismo - un ciclo discontinuo. O, poner estos dos ciclos juntos, la permutación se puede expresar como el producto de $(\text {a b d c})(\text{e f})$.

En el barrio de Santa Claus pregunta (ocho empleados sucediendo han elaborado los nombres perfectamente pares: Anna da a Marta un regalo, mientras que Marta ha atraído a Anna nombre) no se $4$ bucles cerrados.

4. Para encontrar el número de dos elementos bucles tenemos que dividir todas las posibles permutaciones $(2n)!$ del conjunto de los ocho ($2n$) de las personas por el total de número posible de swaps de dos elementos $2^n$ y el número total de permutaciones de estos pares $n!$: $p(2n) = \frac{(2n)!}{2^n n!}$.

---

Para el R simulación:

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

Esta función se reduce a la comprensión de x[x]: se pretende evaluar un $8$ elemento del vector que representa el presente de las asignaciones, y determinar si es compuesto de 2 elementos de bucles, como en el de Santa Claus problema. Mientras las permutaciones corresponden a la transposición de elementos, de forma que si Pablo se suponía que era para hacer un regalo a María (Paul -> Maria y viceversa, Maria -> Paul) y Max a Juan (Max -> John / John -> Max) inicialmente, el resultado de la transposición sólo los resultados en el nuevo maridaje perfecto (Max -> Maria / Maria -> Max y Paul -> John / John -> Paul), el cumplimiento de la condición inicial de maridaje perfecto:

En otras palabras, si volvemos al ejemplo de los sombreros de Wikipedia persona i siempre lleva sombrero de $1$.

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

Esta función evalúa si se trata de un trastorno mediante la comparación de los vectores $x$ elemento sabio el que el vector de $(1,2,3,4,5,6,7,8)$, y asegurarse de que no hay ninguna coincidencia.

3. k.paired <- sum(i.good & i.paired) es no excluir emparejado permutaciones como la de arriba 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.