Tuesday, December 30, 2014

Secret Santa Problems (Part II)

This post is in English now, since this is exactly the version of Secret Santa we played at our lab's Christmas party. I could not find the results of this post anywhere in the internet, but they probably appear somewhere. Possibly they are wrong.

This post is the second part to my previous post "Wichtel-Probleme".

Let's play Secret Santa again! Usually, at the beginning of the Christmas season all $n$ players would fix a derangement, which is a permutation of all players' names such that no player ends up with his or her own name. Naturally, this derangement is anonymous, i.e., a given player only knows which name he got assigned, and nothing else. The problem of finding a proper assignments is quite complicated, as the number of derangements is given by the sub-factorial

$$!n = n! \cdot \sum_{k=0}^n \frac{(-1)^k}{k!}$$

which for large $n$ quickly approaches a fraction of $1/e$ of all $n!$ permutations. Hence, only about 36% of all arrangements are proper, i.e., derangements. Typically, one would not want to play something like that in an office with 30 or more employees, since the process of drawing names can be quite time consuming (but see this blog post by Martin Eden about an algorithm ensuring a proper permutation).

Instead, let us play a different version of Secret Santa: Every player brings a wrapped gift and deposits it on a nicely decorated table. Then, the players take turns and draw exactly one gift. Let us assume that none of the players will choose his or her own gift -- that wouldn't be fun, would it? But what if a player has no choice? This brings us to the question of this post:

What is the probability that the last player has to take home his or her own gift?

Clearly, if there are just two players, this situation cannot occur: Either both players get their own gifts, or none does. Since the first option is ruled out, for $n=2$ this probability is zero. And for three players? Let's look at the following table listing all six possible permutations of gifts. Invalid permutations (those in which any of the first two players takes his or her own gift) are crossed out.:

1 2 3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Of all six permutations, only three follow the given rules, and of these only one (indicated in red) makes the last player draw his or her own gift. Hence, the probability is 1/3.

Let's generalize this:

How many permutations end up with the last player taking his or her own gift, given that none of the first $n-1$ players take their own gifts? And how many permutations are there such that the first $n-1$ players do not take their own gifts?

The ratio between the answers of these two questions is the desired probability.

The first question is easy to answer: Just fix the last gift to the last player and count the number of derangements for the first $n-1$ players; the result is $!(n-1)$. The second question is a bit more tricky, and I am not sure if the result is correct. Intuition tells me that the result can be obtained by complete induction or a different kind of recursion, but maybe also the following reasoning is correct: Essentially, there are just two options for the first $n-1$ players not to take their own gifts. Either all $n$ gifts are properly deranged, or the first $n-1$ gifts are deranged and the last gift is fixed. These two options are exclusive: If all $n$ names are deranged, the last gift has to be taken by any of the first $n-1$ players. Hence, we can add the possibilities of these two options; $!n$ for complete derangements and $!(n-1)$ for derangements with the last gift fixed. The probability that the last player has to take home his or her own gift is thus

$$ \frac{!(n-1)}{!(n-1)+!n} $$

The picture below shows that this probability decreases approximately by $1/n$ with the number of players. The more, the merrier!



By the way: The number of derangements with $k<n$ fixed points (i.e., exactly $k$ players take home their own gifts) is given by the Recontres numbers. However, given our rule, more than one fixed point cannot occur.

Wednesday, December 17, 2014

Wichtel-Probleme

This post is in German. There are already a few blog posts about this topic in English; see the list of references at the end of this post.

Lasst uns wichteln! Nehmen wir an, wir wären $n$ Freunde. Wir schreiben unsere Namen auf Kärtchen, werfen diese in einen Hut, und ziehen der Reihe nach jeweils eine Karte wieder heraus. Es kann natürlich passieren, dass jemand von uns seinen eigenen Namen zieht, worauf wir den Vorgang wiederholen müssten. Doch wie groß ist die Wahrscheinlichkeit, dass niemand von uns seinen eigenen Namen zieht?

Das Problem ist kombinatorischer Natur: Es gibt genausoviele Möglichkeiten, die Karten wieder unter uns aufzuteilen, wie es Permutationen der Karten gibt: Das wären $n!=1\cdot2\cdot 3\dots\cdot n$. Unter diesen möglichen Permutationen gibt es nur einige sogenannte fixpunktfreie Permutationen, also solche, bei denen niemand seine eigene Karte zieht. Die Anzahl der fixpunktfreien Permutationen ist

$$!n = n! \cdot \sum_{k=0}^n \frac{(-1)^k}{k!}$$

Sind wir nur zu zweit ($n=2$), gibt es natürlich nur zwei Permutationen, und nur eine davon ist fixpunktfrei. Die Wahrscheinlichkeit, dass wir beim ersten Ziehen bereits erfolgreich sind, liegt bei 50%. Spielen wir zu dritt, gibt es sechs Permutationen, wovon zwei fixpunktfrei sind (die zufälligerweise auch gleichzeitig Rotationen sind). Die Wahrscheinlichkeit sinkt also schnell auf ca. 33%. Interessant wird es, wenn wir $n$ wachsen lassen: Es zeigt sich, dass die Wahrscheinlichkeit sehr schnell gegen den Grenzwert $1/e$ konvergieren: Die Wahrscheinlichkeit, dass wir beim ersten Ziehen erfolgreich sind, liegt für vier oder mehr Spieler ungefähr bei 37%, und das unabhängig von der Anzahl der Spieler!


Etwas schwieriger wird es, wenn eine Gruppe von Paaren sich entscheidet zu wichteln: Die Regeln verändern sich dahingehend, dass man nicht nur sich selbst nicht ziehen darf, sondern auch seinen Partner nicht -- das wäre ja zu einfach! Und genau diese Situation trat in unserer Familie auf: Wir schrieben Zettel, warfen sie in einen Hut, zogen, und erhielten eine ungültige Zuordnung. Auch der zweite Versuch schlug fehl. Erst beim dritten Mal klappte es. Ich hatte das dumpfe Gefühl, dass wir beim dritten Mal bereits außerordentliches Glück hatten und wollte der Sache auf den Grund gehen.

Wenn wir $n$ Paare betrachten (also $2n$ Personen), dann gibt es $(2n)!$ Permutationen, von denen $!(2n)$ fixpunktfrei sind. Allerdings sind nicht alle diese fixpunktfreien Permutationen gültig: Die Permutation, in der jede Person ihren Partner zieht ist zum Beispiel fixpunktfrei. Es gibt also höchstens $!(2n)$ gültige Permutationen. Eine gültige Permutation wäre zum Beispiel eine solche, in der jedes Paar ein anderes Paar zieht; innerhalb dieses Paares gibt es dann zwei mögliche Zuordnungen: Mann-Mann und Frau-Frau oder Mann-Frau und Frau-Mann. Davon gibt es natürlich $2\cdot !n$ mögliche Permutationen ($!n$ für die Auswahl der Paare, und $2$ für die Zuordnung innerhalb der Paare). Nachdem das nicht alle gültigen Permutationen sind ist das eine untere Grenze, so wie $!(2n)$ eine obere ist. Die obere Grenze für die Wahrscheinlichkeit einer gültigen Permutation ist also (wie oben) bei 37%, the untere Grenze1 ist eng mit dem quadrupel factorial verknüpft:

$$\frac{2 \cdot !n}{(2n)!}= \frac{2 \cdot n!}{(2n)!} \cdot \sum_{k=0}^n \frac{(-1)^k}{k!}$$

Bei zwei Paaren ($n=2$, vier Personen) gibt es also höchstens neun und mindestens zwei gültige Permutationen. In der Tat kann man zeigen, dass es genau vier gültige Permutationen bei zwei Paaren gibt. Bei drei Paaren, so wie in unserer Familie, gibt es bereits 720 mögliche Permutationen, von denen 265 fixpunktfrei sind, wovon wiederum nur 80 der Regel entsprechen, dass niemand den eigenen Partner ziehen darf! Die Wahrscheinlichkeit, bei drei Paaren gültig zu ziehen liegt also bei ca. 11%. Wenden wir nun noch die geometrische Verteilung an, welche die Wahrscheinlichkeit berechnet, den ersten Erfolg nach genau $k$ Zügen zu haben, stellt sich heraus dass man nur mit einer Wahrscheinlichkeit von ca. 30% innerhalb der ersten drei Versuche eine gültige Zuordnung bekommt. Wir hatten tatsächlich Glück!

Es geht aber noch ein wenig komplizierter: Nehmen wir an, wir haben $N$ Gruppen von Personen, und jede dieser Gruppen hat eine unterschiedliche Anzahl von Personen: Gruppe 1 hat $n_1$ Mitglieder, Gruppe 2 $n_2$, und so weiter. Wie groß ist die Wahrscheinlichkeit, dass bei der Auslosung niemand sich selbst oder ein Mitglied der eigenen Gruppe zieht? (Wichteln mit Paaren ist davon natürlich ein Sonderfall, und zwar mit $N=n$ und $n_1=n_2=\cdots=n_n=2$.) Die Fragestellung ist äußerst kompliziert, aber die Lösung existiert seit 19742. Sie ist über ein kompliziertes Integral über das Produkt mehrerer Laguerre-Polynome gegeben. Mehr will ich dazu jetzt nicht sagen.

Übrigens: Wenn die Anzahl $n$ der Pärchen wächst, erhält man als Grenzwert für die Wahrscheinlichkeit einer gültigen Zuordnung $1/e^2$! Für diesen Fall ist das oben genannte Integral nämlich relativ einfach lösbar.

Weiterführende Literatur/Further Reading:



1 Diese untere Grenze ist übrigens, für großes $n$, sehr schlecht: das quadrupel factorial wächst sehr schnell, weshalb die untere Grenze für die Wahrscheinlichkeit schnell gegen null geht.

2 Derangements and Laguerre polynomials, S. Even and J. Gillis (1976). Mathematical Proceedings of the Cambridge Philosophical Society, Volume 79, Issue 01, January 1976, pp 135-143.