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

11

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ć?

hermann
źródło
1
„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:

14

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

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

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

(a11a12)(a21a22)(an1an2).

2nn!2nn!

p(2n)=(2n)!2nn!

takie pary.

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

p(2n)d(2n)=12nn!(11/2+1/6+(1)k/k!++1/(2n)!)e2nn!.

2n=815/21190.00707881e/(244!)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.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
ź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
1
@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
1
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,
1
@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
7

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)=(n1)[d(n2)+d(n1)]=

=nd(n2)d(n2)+nd(n1)d(n1)

d(n)nd(n1)=[d(n1)(n1)d(n2)]

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

d(n)nd(n1)=[d(n1)(n1)d(n2)]=

=(1)2[d(n2)(n2)d(n3)]==(1)n2d(2)2d(1)

d(n)=nd(n1)+(1)n

Praca wstecz:

d(2)=1

d(3)=3d(2)1=311

d(4)=4d(3)+1=4314+1

d(5)=5d(4)1=543154+51

d(6)=6d(5)+1=65431654+656+1=

=6!(12132+143215432+16!)=

=6!(16!15!+14!13!+12!11!+1)

Więc ogólnie

d(n)=n!(11+12!13!+14!++1n!)

exx=1

d(n)n!e

a,b,c,d,e,fb,d,a,c,f,ea -> b -> d -> c after which it returns to ae -> f(a b d c)(e f)

4

(2n)!2n2nn!p(2n)=(2n)!2nn!


Do Rsymulacji:

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

x[x]8Paul -> MariaMaria -> PaulMax -> JohnJohn -> MaxMax -> MariaMaria -> MaxPaul -> JohnJohn -> Paulwprowadź opis zdjęcia tutaj

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
1
e=
1
11
@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,