Prawdopodobieństwo, że ustawienie Sekretnego Świętego Mikołaja doprowadzi do idealnych par

Więc mieliśmy Tajnego Świętego Mikołaja w pracy.

Jesteśmy 8 osobami. Każdy z nas na zmianę wyciągał z miski kawałek papieru z nazwą. Jedyna zasada: jeśli wyciągniesz swoje imię, musisz włożyć kawałek papieru z powrotem do miski i spróbować ponownie.

Nazwijmy ludzi A, B, C, D, E, F, G, H, w takiej kolejności, w jakiej wybrali kawałek papieru.

Ostatniej nocy dokonaliśmy wymiany prezentów.

A był sekretnym Mikołajem F.
B był sekretnym Mikołajem E.
C był sekretnym Mikołajem D.
D był tajemniczym Mikołajem C.
E był sekretnym Mikołajem B.
F był sekretnym Mikołajem A.
G był tajemniczym Mikołajem Świętego Mikołaja.
H był sekretnym Mikołajem G.

Widzisz co się stało? Zrobiliśmy pary.

A i F były dla siebie sekretnym Mikołajem.
B i E byli dla siebie sekretnym Mikołajem.
C i D byli dla siebie sekretnym Mikołajem.
G i H byli dla siebie sekretnym Mikołajem.

Jakie jest prawdopodobieństwo takiego zdarzenia i jak go obliczyć?

combinatorics odds

— hermann
źródło

„Jeśli wyciągniesz swoje imię, musisz włożyć kawałek papieru z powrotem do miski i spróbować ponownie.” Co się stanie, jeśli jako ostatni wybierzesz i wyciągniesz swoje imię?

— Juho Kokkala,

Jeśli osoba A rysuje etykietę C (powiedzmy), a następnie osoba B rysuje etykietę B, to czy osoba A również wkłada etykietę C z powrotem do kapelusza i rysuje ponownie? Wydaje się, że sugerują to odpowiedzi, ale rozumiem sformułowanie, które oznacza, że A utrzymuje przerysowanie etykiety C i B od kapelusza zawierającego etykiety (A, B, D, E, F, G, H).

— Juho Kokkala,

Odpowiedzi:

Łączna liczba zadań wśród osób, do których nikt nie jest przypisany, wynosi (Są to tak zwane odstępstwa ). Wartość jest bardzo zbliżona do $2n$

d (2 n) = (2 n)! (1 / 2 - 1 / 6 + \dots + (- 1)^{k} / k! + \dots + 1 / (2 n)!) .

$d(2n) = (2n)!(1/2 - 1/6 + \cdots + (-1)^k/k! + \cdots + 1/(2n)!).$

(2 n)! / e

$(2n)! / e$

Jeśli odpowiadają idealnym parom, to są wynikiem rozłącznych transpozycji . Oznacza to, że ich struktura cyklu ma formę

(a_{11} a_{12}) (a_{21} a_{22}) \dots (a_{n 1} a_{n 2}) .

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

$2n$ $n!$ $2^n n!$

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

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

takie pary.

Ponieważ wszystkie takie idealne parowania są odstępstwami, a wszystkie odstępstwa są jednakowo prawdopodobne, szansa jest równa

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

$\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!}.$

$2n=8$ $15/2119 \approx 0.00707881$ $e/(2^4\, 4!) \approx 0.00707886$

Aby to sprawdzić, ta Rsymulacja rysuje milion losowych permutacji ośmiu obiektów, zachowuje tylko te, które są wykroczeniami, i zlicza te, które są idealnymi parami. Wyprowadza swoje oszacowanie, błąd standardowy oszacowania i wynik Z, aby porównać go z wartością teoretyczną. Jego wydajność to

       p.hat           se            Z 
 0.006981031  0.000137385 -0.711721705

$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))

— Whuber
źródło

+1 za głupią twarz szopa pracza i okulary ... Podszedłem do skrótu koncepcji „elementu stabilizującego”, ponieważ nie wiem, od czego zacząć, ale to ma sens, nawet biorąc to pod uwagę intuicyjnie.

— Antoni Parellada,

@Antoni Zobacz na przykład en.wikipedia.org/wiki/Burnside's_lemma .

— whuber

@Amoeba Myślałem o tym, ale postanowiłem skupić się na obecnym problemie, ponieważ odstępstwa są tak dobrze znane. Artykuł w Wikipedii, do którego odsyłam, zawiera kilka metod uzyskania tej formuły. Najbardziej oczywista metoda wykorzystuje zasadę włączenia-wykluczenia, co jest widoczne w wyrażeniu przemiennej sumy.

— whuber

Czy zakładasz, że rysowanie etykiet rozpoczyna się od zera, jeśli ktoś narysuje własną etykietę (patrz moje komentarze do pytania). W przeciwnym razie nie sądzę, aby wszystkie odstępstwa były jednakowo prawdopodobne.

— Juho Kokkala,

@Juho To dobre pytanie, warte dalszych przemyśleń. Odpowiedziałem na podstawie domniemanej intencji procedury rysowania, która polegałaby na utworzeniu wszystkich odchyleń z jednakowym prawdopodobieństwem, ale nie jest jasne, jaka procedura została zastosowana lub czy wygenerowałoby to odchylenia o jednolitym rozkładzie (lub czy jest to gwarantowany nawet sukces w tworzeniu wykroczenia!).

— whuber

Byłem pod wrażeniem elegancji w odpowiedzi na @whuber. Szczerze mówiąc musiałem dużo zapoznać się z nowymi koncepcjami, aby podążać za krokami w jego rozwiązaniu. Po spędzeniu dużo czasu postanowiłem opublikować to, co dostałem. Poniżej znajduje się egzegetyczna notatka do jego już zaakceptowanej odpowiedzi. W ten sposób nie ma próby oryginalności, a moim jedynym celem jest zapewnienie dodatkowych punktów zakotwiczenia, które pozwolą wykonać niektóre z tych czynności.

No i proszę…

$2n$

2. Czy możemy wyprowadzić wzór na odstępstwa?

$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)$

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

Zauważając teraz paralelność między LHS tego równania i częścią RHS w nawiasach, możemy kontynuować rekurencyjnie:

$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)$

$d(n) = n\,d(n-1)+(-1)^n$

Praca wstecz:

$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)$

Więc ogólnie

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

$e^x$ $x=-1$

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

${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})$

$4$

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

Do Rsymulacji:

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

x[x] $8$ Paul -> 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. Czyk.paired <- sum(i.good & i.paired) istnieje wykluczenie sparowanych permutacji, takich jak powyższe na schemacie, które nie są odstępstwami:

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.

— Antoni Parellada
źródło

e

$e$

\approx

$\approx$

=

$=$

1

$1$

- 1

$-1$

@whuber Dziękuję. Naprawdę wygłupiałem się. Nie jestem dobry w powtarzalnych, indeksowanych zadaniach ... Wiedziałem, że coś jest nie tak. Teraz powinno to zostać naprawione.

— Antoni Parellada,