February 2020

I had my Goethe-Zertifikat A1: Start Deutsch 1 exam about 3 weeks ago. The exam has four parts: listening, reading, writing and speaking. I was most nervous about the oral exam, but once it started, I felt more comfortable. The third part of the oral exam is about making and responding to requests. One of the other candidates took a card with a “no smoking” sign on it, but I think he forgot the word “smoking”. He was smart, though, and said, “Please do not give the children cigarettes”. I think my speaking skills were good enough, though unfortunately not as humorous.

Vor drei Woche habe ich meine Goethe-Zertifikat A1 Prüfung gemacht. Die Prüfung hat vier Teilen, nämlich Lesen, Hören, Schreiben und Sprechen. Ich war am nervösesten über die mundliche Prüfung, aber als sie angefangen hat, fühle ich mich besser. Das dritte Teil der mundlichen Prüfung ist über Bitten formulieren und reagieren. Ein anderer Kandidat hat eine Karte mit einem “Rauchen verboten” Schild genommen. Ich habe gedacht, dass er hat das Wort “rauchen” vergessen. Er war intelligent, und hat gesagt “Bitte geben Sie meinen Kindern keine Zigaretten”. Ich denke, dass ich habe gut genug gesprochen, aber ich war leider nicht so lustig.

Taboo is a game where one needs to communicate a word to one’s partner, without saying a list of “taboo” words. For example, for the word “Twister” one might have Tornado, Game, Colours, Legs and Arms as taboo words. If I still wanted to go for the party game approach (which I think is easier than the tornado approach as it’s very precise if done correctly), I might say something like “Something played at a party where a wheel is spun and players contort their limbs to place them on red, green, blue or yellow circles”.

I’ve found some similarities between playing Taboo and speaking in German (and even in Mandarin), in that I can’t always use the most direct approach of communicating something. The reason for this is different: in Taboo, it is the rules of the game, while with second and third languages it is typically because I lack vocabulary required to use the most direct approach. For example, if I wanted to communicate “I want a pair of chopsticks”, I could do this easily in English or Chinese (我要筷子), but I don’t know the word for that in German (Essstäbchen, it turns out). I might thus need to work around it via description, with something like “Könnten Sie mir chinesisches Besteck geben?”. There are a number of English words that have been adopted into German, so I could just take a shot in the dark with “Geben Sie mir ein Paar Chopsticks, bitte.” which would probably get the point across especially to a German speaker, though it’s wrong.

I’ve also tried playing Taboo myself in German. Even sticking to simple sentences (to avoid struggling with stringing together subclauses or neighbouring-sentences on the fly) not having a broad vocabulary makes it tricky. For example, I saw a card with goal word Biene or bee (banned: gelb or yellow, Stachel or sting, Summen or sum, Honig or honey, Blütenstaub or pollen). In English, this isn’t very hard: “there’s a queen, they make hexagonal structures, produce golden liquid good for coughs… you can say you have this in your bonnet, or if you’re in a rush you’re making a this-line for something”. I found this tricky in German. Even trying to translate what I’d say in English, I might begin “Es hat Königin”, but it goes downhill from there (turns out hexagon is just das Hexagon, and I could improvise liquid by just saying Wasser). I wouldn’t be able to give the idioms and I’m not sure they still work in German. Effectively, all of the missing vocabulary items are permanent Taboo words.

I think one of my strengths in English communication is being able to make statements fairly precisely (for example, “I don’t have a particularly strong opinion; while I agree with (specific parts of X), I’m not confident X is correct because I am not in a position to assess (other part of X)”, or “X is correct in principle but I’m not sure it’s appropriate to implement”). I’m not there in Chinese, and definitely not in German. This can be an issue with using possibly circumlocutory descriptions – if they accidentally indicate a preference that isn’t really there. For example, for the “chinesisches Besteck” example above, one can’t fault a server that brings a soup spoon (and depending on one’s point of view, the server could be justifiably annoyed if one rejects the soup spoon and continues to make this request without qualifying it further).

The birthday paradox is a fairly well-known but unintuitive observation that although there are normally 365 days in a year (for simplicity, ignoring leap years and assuming a uniform distribution for birthdays), with as few as 23 people it is more likely than not that two of them will share a birthday. One of my teammates proposed an inverse of this problem: what is the minimum number of people are needed so that it is more likely than not that it is someone’s birthday every day?

Modelling A Specific Instance

There’s a lot to take in here, so let’s try to solve a simpler problem first. We could attempt to solve: given a specific number of people, how would we calculate the probability that it is someone’s birthday every day? If we have this method, we can reconstruct the answer to the original problem via a search algorithm.

The more general problem here would be: suppose we have $N \geq 1$ people. Each person draws one of $K \geq 1$ events with replacement – these are equally probable and independent. What is the probability that all events occur at least once? The more general introductory problem has $K = 365$ , but of course that’s tricky to work with right off the bat, so let’s examine a couple of the smaller cases.

Algorithmic Ideation

Base Case Analysis

If $K = 1$ , since we said that we always have at least one person, the one possible event will happen and the probability is $1$ . Moving on to $K = 2$ , here $N = 1$ is a special case with probability of $0$ . For larger $N$ , there are two specific situations we want to avoid, where every person draws the same event (remember that there were two events). Each of these happens with probability $2^{-N}$ so the probability of everything occurring once would be $1 - 2 \times 2^{-N} = 1 - 2^{-N + 1}$ .

We can now analyze $K = 3$ – if $N \leq 2$ we definitively have probability $0$ . For $N = 3$ , the first person will receive a novel outcome with certainty, but the second and third person also need novel outcomes, and this happens with probability $\frac{2}{3} \times \frac{1}{3} = \frac{2}{9}$ . It gets a little trickier with $N = 4$ :

The first person to draw an event will get a novel event. This leaves 3 people to draw events, and 2 out of 3 events undrawn. We can call this state $(3, 2, 3)$ .
The second person to draw an event will get a novel event with probability 2/3, putting us in the state $(2, 1, 3)$ . Alternatively, he/she will draw the same event as the first person with probability 1/3, getting us in the state $(2, 2, 3)$ .
If we’re in $(2, 1, 3)$ , there’s a 1/3 probability that the third person draws the last event (in which case we are done), and a 2/3 probability he doesn’t, putting us in $(1, 1, 3)$ .
If we’re in $(1, 1, 3)$ we have one person who needs to draw the last event with probability 1/3.
If we’re in $(2, 2, 3)$ , the third person will get a novel event with probability 2/3, putting us in $(1, 1, 3)$ . He might draw the same event as the first two people, in which case we definitely failed.

More generally, we can model the problem using a state machine (a technique which I discussed two and a half years ago). The states of this machine can be written as 3-tuples $(p, q, r)$ which means we have $p$ people to draw events, there are $r$ events of which $q$ still need to be drawn. Notice that $q \leq r$ , and that for our problem, we have $r = K$ and we generally want to find the probability of success for the state $(N, K, K)$ .

For $K = 3, N = 4$ we can draw this as follows.

Recurrence Relations

We can define $V(p, q, r)$ as the probability that transitions from the state $(p, q, r)$ will eventually end up in a SUCCESS state, defined as $(p, 0, r)$ for all values of $p$ and $r$ (as that means all events were drawn). We make some observations on simple cases:

$V(p, 0, r) = 1$ . We are already in a success state by definition.
$V(0, q \geq 1, r) = 0$ . If everyone has drawn an event and there are still events that haven’t occurred, there is no chance for us to draw those events.

That’s all we need, and we can look at the recursive case. In the state $(p, q, r)$ , there is a $\frac{q}{r}$ probability that we draw a new outcome, putting us in the state $(p-1, q-1, r)$ . There is also a $1 - \frac{q}{r}$ probability that that doesn’t happen – in that case we’re in the state $(p-1, q, r)$ . It thus follows that

$V(p, q, r) = \dfrac{q}{r} \times V(p-1, q-1, r) + \left( 1 - \dfrac{q}{r} \right) \times V(p-1, q, r)$

Notice that these states are well-formed, since we handled the $p=0$ and $q=0$ base cases earlier. It is possible to optimise this by adding some more sophisticated base cases, but this still gives us a clear enough method for working out the probability. For example,

$V(2, 1, 3) =\frac{1}{3} \times V(1, 0, 3) + \frac{2}{3} \times V(1, 1, 3) = \frac{1}{3} \times 1 + \frac{2}{3} \times \frac{1}{3} = \frac{1}{3} + \frac{2}{9} = \frac{5}{9}$
$V(2, 2, 3) =\frac{2}{3} \times V(1, 1, 3) + \frac{2}{3} \times V(1, 2, 3) = \frac{2}{3} \times \frac{1}{3} + \frac{1}{3} \times 0 = \frac{2}{9}$
$V(4, 3, 3) = V(3, 2, 3) = \frac{2}{3} \times V(2, 1, 3) + \frac{2}{3} \times V(2, 2, 3) = \frac{4}{9}$

Solving The Specific Instance

The answer to our original problem, for a given number of people $N$ is then $V(N, 365, 365)$ . Working this out by hand is likely to be painful, so we should avoid that. It’s easy to code something simple up that is based on the recurrence relation above:

private static double findSuccessProbability(long remainingPeople, long remainingEvents, long totalEvents) {
    if (remainingEvents == 0) {
        return 1.0;
    }
    if (remainingPeople == 0) {
        return 0.0;
    }

    double probabilityOfNewEvent = ((double) remainingEvents) / totalEvents;
    double successProbabilityOnNewEvent = findSuccessProbability(remainingPeople - 1, remainingEvents - 1, totalEvents);
    double successProbabilityOnOldEvent = findSuccessProbability(remainingPeople - 1, remainingEvents, totalEvents);

    return probabilityOfNewEvent * successProbabilityOnNewEvent
            + (1 - probabilityOfNewEvent) * successProbabilityOnOldEvent;
}

We can test this and verify that indeed $V(4, 3, 3) = \frac{4}{9}$ . However, if we try to call this with, say $(500, 365, 365)$ the program doesn’t seem to give the answer quickly.

One solution here is to use memoisation. The naive version written above ends up computing the answer for the same state potentially exponentially many times, but we can cache the results of previous computations and use them. This could be done with a map with the 3-tuple as a cache key; alternatively, a bottom-up dynamic programming solution can be written, since there’s a clear order in which we process the subproblems. In any case, these methods should get the runtime down from exponential to $O(NK)$ .

Reconstructing The General Solution

We want to find the smallest $N$ such that $V(N, 365, 365) > 0.5$ . We could start from $N = 365$ and then keep trying larger values of $N$ : since $K$ is constant this is actually not that bad as we can reuse the results of computations from previous attempts when trying new values of $N$ .

public static void main(String[] args) {
    long numPeople = 365;
    double successProbability = findSuccessProbability(numPeople, 365, 365);
    while (successProbability <= 0.5) {
        numPeople++;
        successProbability = findSuccessProbability(numPeople, 365, 365);
    }
    System.out.println(numPeople);
}

This gives us our answer: 2287. We have $V(2286, 365, 365) = 0.499414 \ldots$ while $V(2287, 365, 365) = 0.500371 \ldots$ .

This approach looks a bit primitive – and normally we’d use a modified binary search where we first search for an upper bound via something that grows exponentially, and then binary search up to our bound. This works, since $V(p, q, r)$ increases as $p$ increases for constant $q, r$ .

However, for this specific problem and more generally for recurrences where we end up reducing parameters by 1, we still need to burn through almost all of the smaller subproblems we skip over by isolating the bound, so it won’t actually give us that much here.

Usually when working with recurrences it is nice to find a closed-form solution for our expression (i.e. we have a general expression for $V(p, q, r)$ that doesn’t itself reference $V$ ), though I didn’t really see how to make progress with this one.

Learning German 5: Do Not Give The Children Cigarettes

Is It Someone’s Birthday Everyday? Solving the Inverse Birthday Problem