Wahrscheinlichkeit, dass die Anordnung des geheimen Weihnachtsmanns zu perfekten Paarungen führt

Also hatten wir Secret Santa bei der Arbeit.

Wir sind 8 Leute. Wir wechselten uns ab und zogen ein kleines Stück Papier aus einer Schüssel mit einem Namen darauf. Einzige Regel: Wenn Sie Ihren Namen ziehen, müssen Sie das Stück Papier wieder in die Schüssel legen und es erneut versuchen.

Nennen wir die Leute A, B, C, D, E, F, G, H, was auch die Reihenfolge ist, in der sie ihr Stück Papier ausgewählt haben.

Wir haben gestern Abend den Geschenkaustausch gemacht.

A war Fs geheimer Weihnachtsmann.
B war E's geheimer Weihnachtsmann.
C war Ds heimlicher Weihnachtsmann.
D war Cs geheimer Weihnachtsmann.
E war B's geheimer Weihnachtsmann.
F war A's geheimer Weihnachtsmann.
G war Hs geheimer Weihnachtsmann.
H war Gs geheimer Weihnachtsmann.

Sehen Sie, was passiert ist? Wir haben Paare gemacht.

A und F waren die geheimen Weihnachtsmänner des anderen.
B und E waren die geheimen Weihnachtsmänner des anderen.
C und D waren die geheimen Weihnachtsmänner des anderen.
G und H waren die geheimen Weihnachtsmänner des anderen.

Wie hoch ist die Wahrscheinlichkeit dafür und wie berechnen Sie sie?

combinatorics odds hermann
quelle

"Wenn Sie Ihren Namen ziehen, müssen Sie das Stück Papier wieder in die Schüssel legen und es erneut versuchen." Was passiert, wenn Sie der letzte sind, der Ihren eigenen Namen auswählt?

Juho Kokkala

Wenn Person A Etikett C zeichnet (sagen wir) und Person B Etikett B zeichnet, setzt Person A dann auch Etikett C wieder in den Hut und zeichnet erneut? Dies ist, was die Antworten zu implizieren scheinen, aber ich verstehe den Wortlaut so, dass A das Etikett C behält und B aus dem Hut, der Etiketten enthält (A, B, D, E, F, G, H), neu zeichnet.

Juho Kokkala

Antworten:

Die Gesamtzahl der Aufgaben unter Personen, denen niemand zugewiesen ist, beträgt (Diese werden als Störungen bezeichnet .) Der Wert liegt sehr nahe bei $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$

Wenn sie perfekten Paarungen entsprechen, sind sie ein Produkt disjunkter Transpositionen . Dies impliziert, dass ihre Zyklusstruktur die Form hat

(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}).$

Die Anzahl unterschiedlicher solcher Muster ist die Reihenfolge der Gruppe aller Permutationen der Namen geteilt durch die Reihenfolge des Stabilisators des Musters. Ein stabilisierendes Element kann eine beliebige Anzahl von Paaren tauschen und es kann auch das permutieren Paare, woher gibt es stabilisierende Elemente. Deshalb gibt es $2n$ $n!$ $2^n n!$

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

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

solche Paarungen.

Da alle diese perfekten Paarungen Störungen sind und alle Störungen gleich wahrscheinlich sind, ist die Chance gleich

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

Für Personen daher die genaue Antwort ist während die Näherung $2n=8$ $15/2119 \approx 0.00707881$ : Sie stimmen mit fünf signifikanten Zahlen überein. $e/(2^4\, 4!) \approx 0.00707886$

Zur Überprüfung zeichnet diese RSimulation eine Million zufälliger Permutationen von acht Objekten, behält nur diejenigen bei, die Störungen sind, und zählt diejenigen, die perfekte Paarungen sind. Es gibt seine Schätzung, den Standardfehler der Schätzung und einen Z-Score aus, um sie mit dem theoretischen Wert zu vergleichen. Seine Ausgabe ist

       p.hat           se            Z 
 0.006981031  0.000137385 -0.711721705

Der kleine Z-Score stimmt mit dem theoretischen Wert überein. (Diese Ergebnisse stimmen mit jedem theoretischen Wert zwischen und .) $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
quelle

+1 für das alberne Waschbärengesicht und die Brille ... Ich habe eine Abkürzung zum Konzept "Stabilisierendes Element" gewählt, weil ich nicht weiß, wo ich anfangen soll, danach zu suchen, aber es macht sehr viel Sinn, auch nur dieses bisschen zu nehmen intuitiv.

Antoni Parellada

@Antoni Siehe zum Beispiel en.wikipedia.org/wiki/Burnside's_lemma .

whuber

@Amoeba Ich hatte darüber nachgedacht, mich aber entschlossen, mich auf das gegenwärtige Problem zu konzentrieren, da Störungen so bekannt sind. Der Wikipedia-Artikel, auf den ich verlinkt habe, bietet verschiedene Methoden zum Ableiten dieser Formel. Die offensichtlichste Methode verwendet das Prinzip des Einschluss-Ausschlusses, wie aus dem alternierenden Summenausdruck hervorgeht.

whuber

Gehen Sie davon aus, dass das Zeichnen von Etiketten von vorne begonnen wird, wenn jemand sein eigenes Etikett zeichnet (siehe meine Kommentare zur Frage). Ansonsten denke ich nicht, dass alle Störungen gleich wahrscheinlich sind.

Juho Kokkala

@Juho Das ist eine gute Frage, die weitere Überlegungen wert ist. Ich habe auf der Grundlage der impliziten Absicht des Zeichenverfahrens geantwortet , alle Störungen mit gleicher Wahrscheinlichkeit zu erzeugen, aber es ist nicht klar, welches Verfahren genau befolgt wurde oder ob es Störungen mit einer gleichmäßigen Verteilung erzeugen würde (oder ob dies der Fall ist) sogar garantiert, um eine Störung zu produzieren!).

whuber

Ich war ziemlich beeindruckt von der Eleganz in @whuber Antwort. Um ehrlich zu sein, musste ich mich viel mit neuen Konzepten vertraut machen, um den Schritten in seiner Lösung zu folgen. Nachdem ich viel Zeit damit verbracht habe, habe ich beschlossen, das zu posten, was ich habe. Was folgt, ist eine exegetische Anmerkung zu seiner bereits akzeptierten Antwort. Auf diese Weise gibt es keinen Versuch der Originalität, und mein einziges Ziel ist es, einige zusätzliche Verankerungspunkte bereitzustellen, um einige der Schritte zu befolgen.

Also los geht's ...

$2n$

2. Können wir die Formel für Störungen ableiten?

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

Wenn wir nun die Parallelität zwischen der LHS dieser Gleichung und dem Teil auf der RHS in Klammern bemerken, können wir rekursiv fortfahren:

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

Rückwärts arbeiten:

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

Also im Allgemeinen

$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)!$ of the set of eight ( $2n$ ) people by the total possible number of swaps of two elements $2^n$ and the total number of permutations of these pairs $n!$ : $p(2n) = \frac{(2n)!}{2^n n!}$ .

For the R simulation:

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

This function boils down to understanding x[x]: It is meant to evaluate an $8$ element vector representing the present assignments, and determine whether it is composed of 2-element loops, as in the Santa Claus problem. As long as the permutations correspond to transposing elements so that if Paul was supposed to give a present to Maria (Paul -> Maria and vice versa, Maria -> Paul) and Max to John (Max -> John / John -> Max) initially, the resultant transposition just results in new perfect pairing (Max -> Maria / Maria -> Max and Paul -> John / John -> Paul) we are fulfilling the initial condition of perfect pairing:

In other words, if we go back to the example of the hats in Wikipedia person i always takes back hat $1$ .

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

This function evaluates whether we are dealing with a derangement by comparing the vector $x$ element wise to the the vector $(1,2,3,4,5,6,7,8)$ , and making sure there is no coincidence.

3. k.paired <- sum(i.good & i.paired) is there to exclude paired permutations like the one above in the diagram, which are not derangements:

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
quelle

+1, but the formula for derangements with

e

$e$ should be only approximate, i.e. with

\approx

$\approx$ not

=

$=$ .

amoeba says Reinstate Monica

+1, because this is a worthy and useful effort to understand and explain a solution. The explanation of the cross product looks incorrect: it merely computes the sum of squares of entries. In particular,

1

$1$ and

- 1

$-1$ cannot possibly "cancel." The use of the cross product is inessential; it merely was the first, reasonably efficient way that came to mind for checking equality of two numerical vectors, which is its logical role in the algorithm. Don't confuse implementation with explanation!

whuber

@whuber Thank you. I really goofed off there. I'm not good at repetitive, indexed tasks... I knew there was something not right. Now it should be fixed.

Antoni Parellada