Вероятность того, что расположение Secret Santa приведет к идеальному сочетанию

11

Итак, у нас был Секретный Санта на работе.

Нас 8 человек. Каждый из нас по очереди вытащил маленький кусочек бумаги из миски с именем на нем. Единственное правило: если вы вытягиваете свое имя, вы должны положить лист бумаги обратно в чашу и попробуйте снова.

Давайте назовем людей A, B, C, D, E, F, G, H, что также является порядком, в котором они выбрали свой лист бумаги.

Мы обменялись подарками прошлой ночью.

А был секретом Ф. Санта.
Б был секретом Е, Санта.
С был секретным сыном Д.
Д был секретным С Санта.
Е был тайным секретом Санты.
F был секретным Санта Клаусом.
Г был секретным Х. Санта.
H был секретным секретом G

Видишь что случилось? Мы сделали пары.

А и Ф были друг для друга секретом Санты.
B и E были секретом друг друга Санта.
C и D были секретом друг друга Санта.
G и H были секретом друг друга Санта.

Какова вероятность этого и как вы рассчитываете это?

Герман
источник
1
«Если вы вытянете свое имя, вы должны положить лист бумаги обратно в миску и попробовать еще раз». Что произойдет, если вы будете последним, кто выберет свое имя?
Юхо Коккала
Если человек A рисует этикетку C (скажем), а затем человек B рисует этикетку B, будет ли человек A также возвращать этикетку C обратно в шляпу и снова рисовать? Это то, что, по-видимому, подразумевают ответы, но я понимаю, что формулировка означает, что A сохраняет метку C, а B перерисовывает заголовок, содержащий метки (A, B, D, E, F, G, H).
Юхо Коккала

Ответы:

14

Общее количество назначений среди человек, для которых никто не назначен, составляет (Они называются расстройствами .) Значение очень близко к .d ( 2 n ) = ( 2 n ) ! ( 1 / 2 - 1 / 6 + + ( - 1 ) к / к ! + + 1 / ( 2 л ) ! ) . ( 2 н ) ! / е2n

d(2n)=(2n)!(1/21/6++(1)k/k!++1/(2n)!).
(2n)!/e

Если они соответствуют идеальным спариваниям, то они являются продуктом непересекающихся транспозиций . Это подразумевает, что их структура цикла имеет вид

(a11a12)(a21a22)(an1an2).

Число различных таких шаблонов - это порядок группы всех перестановок имен, деленный на порядок стабилизатора шаблона. Стабилизирующий элемент может поменять любое количество пар, а также переставитьпары, откудастабилизирующие элементы. Поэтому естьn ! 2 n n !2nn!2nn!

п(2N)знак равно(2N)!2NN!

такие пары.

Поскольку все такие идеальные пары - это нарушения, и все нарушения одинаково вероятны, шанс равен

п(2N)d(2N)знак равно12NN!(1-1/2+1/6-+(-1)К/К!++1/(2N)!)е2NN!,

Таким образом, для человек точный ответ равен а приблизительное значение : они согласны с пятью значимыми цифрами.15 / 2119 0,00707881 е / ( 2 42Nзнак равно815/21190.00707881е/(244!)0.00707886


Чтобы проверить, это Rмоделирование рисует миллион случайных перестановок из восьми объектов, сохраняет только те, которые являются нарушениями, и подсчитывает те, которые являются идеальными парами. Он выводит свою оценку, стандартную ошибку оценки и Z-оценку, чтобы сравнить ее с теоретическим значением. Его вывод

       p.hat           se            Z 
 0.006981031  0.000137385 -0.711721705

Небольшой Z-показатель соответствует теоретическому значению. (Эти результаты будут соответствовать любому теоретическому значению между и .)0,00730,00660,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))
Whuber
источник
+1 за глупое лицо енота и очки ... Я немного сократил концепцию "стабилизирующего элемента", потому что я не знаю, с чего начать, но это имеет большой смысл, даже принимая этот бит интуитивно.
Антони Пареллада
@Antoni См. Например, en.wikipedia.org/wiki/Burnside's_lemma .
whuber
1
@Amoeba Я думал об этом, но решил сосредоточиться на текущей проблеме, так как расстройства так хорошо известны. Статья в Википедии, на которую я ссылаюсь, предоставляет несколько методов получения этой формулы. Наиболее очевидный метод использует принцип включения-исключения, что очевидно из выражения чередующейся суммы.
whuber
1
Предполагаете ли вы, что рисование ярлыков начинается с нуля, если кто-то рисует собственный ярлык (см. Мои комментарии к вопросу). В противном случае, я не думаю, что все нарушения одинаково вероятны.
Юхо Коккала
1
@Juho Это хороший вопрос, достойный дальнейших размышлений. Я ответил на основании неявного намерения процедуры рисования, которая будет заключаться в том, чтобы создать все нарушения с равной вероятностью, но не ясно, какая именно процедура использовалась или будет ли она генерировать нарушения с равномерным распределением (или это даже гарантированно удастся вызвать расстройство!).
whuber
7

Я был очень впечатлен элегантностью в ответе @whuber. Честно говоря, мне пришлось много знакомиться с новыми концепциями, чтобы следовать этапам его решения. Потратив на это много времени, я решил опубликовать то, что получил. Таким образом, то, что следует, является exegetical примечанием к его уже принятому ответу. Таким образом, нет никакой попытки создать оригинальность, и моя единственная цель - предоставить дополнительные точки привязки, чтобы выполнить некоторые из шагов.

Так что вот так ...

2N

2. Можем ли мы вывести формулу для расстройств?

N

d(N)знак равно(N-1)[d(N-2)+d(N-1)]знак равно

знак равноNd(N-2)-d(N-2)+Nd(N-1)-d(N-1)

d(N)-Nd(N-1)знак равно-[d(N-1)-(N-1)d(N-2)]

Теперь, заметив параллельность между LHS этого уравнения и частью RHS в скобках, мы можем продолжить рекурсивно:

d(N)-Nd(N-1)знак равно-[d(N-1)-(N-1)d(N-2)]знак равно

знак равно(-1)2[d(N-2)-(N-2)d(N-3)]знак равнознак равно(-1)N-2d(2)-2d(1)

d(N)знак равноNd(N-1)+(-1)N

Работа в обратном направлении:

d(2)знак равно1

d(3)знак равно3d(2)-1знак равно3*1-1

d(4)знак равно4d(3)+1знак равно4*3*1-4+1

d(5)знак равно5d(4)-1знак равно5*4*3*1-5*4+5-1

d(6)знак равно6d(5)+1знак равно6*5*4*3*1-6*5*4+6*5-6+1знак равно

знак равно6!(12-13*2+14*3*2-15*4*3*2+16!)знак равно

знак равно6!(16!-15!+14!-13!+12!-11!+1)

Так в общем,

d(N)знак равноN!(1-1+12!-13!+14!++1N!)

еИксИксзнак равно-1

d(N)N!е

a,б,с,d,е,еб,d,a,с,е,еa -> b -> d -> c after which it returns to ae -> f(ABDC)(эф)

4

(2N)!2N2NN!п(2N)=(2n)!2nn!


Для Rсимуляции:

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

x[x]8Paul -> MariaMaria -> PaulMax -> JohnJohn -> MaxMax -> MariaMaria -> MaxPaul -> JohnJohn -> Paulвведите описание изображения здесь

i 1

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

x(1,2,3,4,5,6,7,8)

3.k.paired <- sum(i.good & i.paired) есть ли исключить парные перестановки, подобные приведенной выше на диаграмме, которые не являются отклонениями:

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.
Антони Пареллада
источник
1
езнак равно
1
1-1
@whuber Спасибо. Я действительно дурак там. Я не очень хорош в повторяющихся индексированных задачах ... Я знал, что что-то не так. Теперь это должно быть исправлено.
Антони Пареллада