Data Science 101: Radar Charts

I actually wanted to write down what I don't like about radar charts, but then I found out that this already has been done. So I won't. But, adding to "Misreading 1: Area" in Ghosts on the Radar , I was thinking of the following puzzles:

Suppose you have $n$ real-valued, non-negative measurements $x_1$ through $x_n$. You are a super-smart data scientist and you want to use a radar chart to trick your customer to believe that the measurement result is "good" or "bad" -- i.e., the area under the polygon obtained by connecting points corresponding to these measurements should be large/small. Since the angle between the axes is fixed to $360/(n-1)$, you can influence the size of the polygonal area only by selecting the order in which you plot the measurements to the axes. What is the optimal assignment of measurement values to axes such that the area under the polygon is maximized/minimized?

Edit on July 12th, 2018: Here is the solution to the problem of maxizing the area.

Candy Crush Codes

Candy Crush Saga is a game in which... no, I don't think I have to tell you! But I bet you didn't know yet that the game is actually NP-hard! The original proof can be found on arXiv (or, again, on arXiv; these authors claim to prove a little more general result), but there are also plenty of pop-sci articles around. (Now, that is quite interesting: Walsh posted his paper on March 8th, 2014, and the press wrote articles about it only five days later.) Anyways, that's not really what I wanted to tell you.

A typical game field of Candy Crush Saga (copyright with King Inc., taken from Wikipedia)

If you look at above picture, you will see no three candies in a row or in a column having the same flavor. Why? Because they would disappear immediately (that's more-less the only game rule). But this game rule more-less immediately leads to the following question:

If and $n\times m$ field, filled with candies of $k$ different flavors that are randomly, independently and uniformly chosen, what is the probability that there is at least one horizontal or vertical triple of the same flavor?

In other words, what is the probability that, starting a new level, something happens without you actually touching the screen. The question is obviously combinatorial and interesting in itself. But there is even more to it.

If we look at $n\times m$ fields filled with candies of $k$ different flavors, there are in total $k^{nm}$ possible arrangements. The rules of Candy Crush Saga, however, allow only a subset of these, namely,  $k^{nm}$ minus the answer to above question. For example, if we take just one row with three columns and two flavors, there are eight possible arrangements, of which two are excluded. Taking two rows allows 36 out of  64 arrangements, and three rows permit 102 out of 512. (At least that's what my first calculations show.) In other words, the set of all possible fields allows for a redundancy: If we want to transmit messages by sending pictures of Candy Crush fields, a $3\times 3$ field allows you transmit only up to 102 different messages, although there are 512 different possible arrangements. If now, during the transmission, an error occurs -- the flavor of a candy changes -- you might end up with an invalid field! Candy Crush Saga can be used as a nonlinear block code! Super-exciting, right?

At that, in turn, allows us to ask several questions:

• How should we encode a message efficiently? Is there anything better than just keeping a table of , say,102 fields? (There is.)
• How should we decode the message efficiently? That's a more difficult question if you don't want to store a table of all allowed arrangements. Maybe belief propagation can help here, as it does for Sudoku codes.
• What are the basic properties of an $(n,m,k)$ Candy Crush Code? What is the maximally possible rate given the game rule, i.e., what is the ratio between the number of possible and allowed arrangements? What is the minimum Hamming distance, etc.? How can we improve our encoder in order to guarantee a positive Hamming distance?
• Given that we change the flavor of every candy with a given probability $p \ll 1$ (and choose the new flavor uniformly among the remaining ones), what is the error probability? I.e., what is the probability that the changed arrangement is not detected as erroneous, because it also satisfies the game rules?
• What about error propagation of this code? I.e., if a given candy changes its flavor, how many "information bits" are effected? Can we still reconstruct part of the information, or is the whole block destroyed? (I guess the answer is no.)
• Connecting to the last question: What happens if we let one dimension of the field go to infinity? We would need sequential encoding and decoding techniques, such as they are usual for convolutional codes.
• What happens to all of these topics if we span the field on a cylinder (such that the rules extend over one side of the field: two candies of a given flavor on one side rule out a single candy of the same flavor on the other side) or on a torus?

Most probably, the code thus constructed is crappy. But it is nevertheless a nice topic for a research internship, I guess. And it makes learning nonlinear codes for symmetric channels as fun as Sudoku codes do for erasure channels!

The 9 Balls Problem (still open)

Recently, my lab mate Patrick came to my office and proposed to give the following question for an exam in information theory: Explain why exactly two weightings on a standard balance scale suffice to determine which out of nine balls is heavier than the other eight (which have all the same weight).

Everybody knows the puzzle, and most know the solution: Split the nine balls in groups of three and weigh them. The heavier triple must contain the heavy ball, so you can weigh two balls of the heavier triple. If they balance, the third ball must be the heavy one. Similarly, if the first two triples have the same weight, the heavy ball must be in the third triple that you did not weigh in the first step.

In fact, it turns out that in this case two weightings are not only the minimal number of weightings necessary, but also the optimal number: Each weighting gives us three results (right heavy, left heavy, balanced), so two weightings give us nine results. And, there are exactly nine balls, one of which we have to determine. Hence, if we want to put it in terms of information theory, the number of bits needed to encode the position of the heavy ball is equal to the number of bits obtained from the scale in two weightings:

$$ H(balls) = \log 9 = 2 \log 3 = 2 H(scale) $$

Things get a bit more difficult if we do not know whether the odd ball is heavier or lighter than the rest. Assume that the ball is in one of the first two triples which we weigh. Then, the scale does not immediately tell us in which of these triples it is: If the odd ball is lighter, then it is in the triple going up, if the odd ball is heavier it is in the triple going down. But there is a very nice scheme which allows us to determine the position of the odd ball and whether it is heavier or lighter in three weightings. And again, information theory tells us how to interpret this. Given that there are two possibilities for the weight, $H(weight)=\log 2$, we have

$$ H(balls,weight) = \log 9 + \log 2 = \log 18 < \log 27 = 3\log 3 = 3H(scale) $$

So, three weightings give us more than enough information about whether the odd ball is heavier or lighter, and where it is. I don't want to reproduce the algorithm to find the odd ball here, just let me tell you that three weightings are sufficient for more than nine balls, too. We only have to guarantee that $H(balls,weight)\le 3H(scale)$. The solution to find the odd ball out of twelve is given in the Wikipedia article about the Twelve-Coin-Problem.

It turns out that if we are not interested in the weight of the odd ball, but just in its position, an ordinary balance scale might not be the right type of measurement device. Although thirteen balls would still satisfy above equation, giving

$$ H(balls,weight) = \log 26 < \log 27 = 3H(scale) $$

three weightings tell us the odd ball, but not whether it is heavier or lighter (see Manish's comment to this blog entry or this website). But why is that so? Raj on Quora wrote that with $n$ weightings you can find the odd one of at most $(3^n-1)/2$ balls and the odd one and its weight from at most $(3^n-3)/2$ balls. For $n=3$ this evaluates to 12 and 13, respectively, so the result seems to be correct.

Still, I'm not totally happy with it. If it's true, then there should be a sequence of results expressing this also in terms of entropy, or in terms of conditional entropy of, say, the position given the results of the first two weightings. There is some work to do to improve intuition about this problem, although Raj already did a very good job. Let me know when you're done!

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.

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 Grenze¹ 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 1974². 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:

• Herleitung des Grenzwerts $1/e^2$ für Paare
• Blog post by Michael J. Swart about Secret Santa for couples, including an algorithm
• Blog post by Martin Eden about an algorithm ensuring a proper permutation

---

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.^↩