Imagine that one Sunday, your friend tells you that some evening before next Friday night, they will be throwing you a surprise party. You are delighted: your friend never lies about parties, and you know that they are perfectly logical and will try to surprise you as much as they can. But you (as your friend knows) are the curious sort of person who likes to treat everything (even surprise parties!) as puzzles to be solved. Your friend must have told you about the surprise to test you…
So, you get to thinking about when this party might be. Surely, it can’t be on Friday, because if by Friday morning there hasn’t been a party yet, you’ll know for sure that it will be that Friday evening, so you won’t be surprised. Hmm, but if you know that it can’t be on a Friday, then if by Thursday morning there hasn’t been a party yet, you’ll know for sure that it will be that Thursday evening, so you won’t be surprised then either. So, it can’t be on Thursday or Friday. But this logic repeats, ruling out Wednesday, Tuesday, and finally even Monday. Your friend can’t be throwing you a surprise party after all. You are a bit dejected by this, until come Wednesday evening you find your house adorned with balloons and banners — to your great surprise!
Where did your logic go wrong?
This paradox is an old classic, going all the way back to the second world war, with one story going that the Swedish mathematician Lennart Ekbom first noticed it when thinking about an announced surprise civil defence drill. The philosopher Daniel O’Connor published the first analysis of it in Mind in 1948, and it rose to popularity in 1963 when, like so many great mathematical curiosities, it featured in Martin Gardner’s wonderful Mathematical Games column. Since then the puzzle has fascinated philosophers and logicians, as on the one hand, surely we throw surprise parties, exams and drills all the time, and yet on the other hand, the logic seems flawless.
Now, to claim to solve a philosophical paradox might be to invite hubris, but let us see if a little magic from information theory and game theory can make this paradox give up some of its secrets…
The maths of surprise
What does it mean for the party to be a surprise? When philosophers talk about this paradox, they tend to mean that you will not know when the party will be until it happens. But this leads down a deep philosophical rabbit hole. What is knowledge? Is knowing something enough to know that you know it? Is knowledge closed under deduction? Tricky. So, we will try a different tack.
Our big idea can be summed up in three words: surprise is information.
This flows from the insight of the great Claude Shannon, the founder of information theory. Shannon realised that the amount of information I communicate by telling you that something has happened is all to do with how probable you thought that event was. If I flip a (fair) coin and tell you it landed heads — with a probability of $1/2$ — I’ve communicated one bit of information. A bit is the amount of information that you can describe with one binary digit, and you can describe the result of a fair coin toss with either 0 (tails) or 1 (heads). But if I tell you I flipped 10 coins and they all landed heads — with a probability of $2^{-10}$ — I’ve communicated far more: 10 times more, in fact, as you need 10 bits (10 binary digits: 1111111111) to describe this event. In general, if an event has probability $ q = 2^{-\alpha}$, then you need $\alpha$ bits to describe this event occurring.
Claude Shannon in the 1950s
The physicist Edward Samson then realised that what Shannon was measuring was exactly how surprising the event was. In general, if you come to learn that an event which had probability $q$ has happened, then Samson defined your amount of surprise (which he called your surprisal) to be
\begin{align*} \text{surprise}&= \begin{array}{l}\text{amount of information} \\ \text{(in bits) needed to describe}\\\text{the probability $q$ event} \\\end{array}\\ &= – \log_2 q. \end{align*} When $q = 1/2$, this gives a surprise of $1$, whilst $q=2^{-10}$ gives a surprise of 10. And indeed, flipping 10 heads is a lot more surprising than flipping one!
Why the logarithm? Well, if I tell you that I’ve flipped heads on a coin and rolled three on a die, the total information I’ll communicate will naturally be the sum of the information about the coin and about the die. But the probability of two independent events both happening is the product of the probabilities of those events, so we need the logarithm to turn this product into a sum.
OK, so a surprise party must be a party that surprises you a non-negligible amount. But hang on, what does the probability $q$ mean now? Even if your friend decides on the day of the party using something random like dice or coins, you’d have no idea how they did so, so how could you calculate your surprise?
For this, we need the idea of a subjective probability. Take any event, whether that is your favourite team winning the FA Cup, that it will be sunny on your birthday, or that the party will be on Wednesday. It turns out that we can describe how confident you are that this event will happen (or has happened) as a probability. If that probability is 0 you’re certain it won’t happen, if it is 1 you’re certain that it will, and everything in between is a different degree of not being sure. If the party were to happen on Wednesday evening, then the more confident you were on Wednesday morning that the party would be that evening, the less surprised you would be when it happens; this ‘how confident are you?’ probability is thus what we will feed into the definition of surprise.
Surprise party game theory
Armed with this definition of ‘surprise’, we can formulate throwing a surprise party (for a puzzle-solver who likes to logic their way out of surprises) as a game played between you and your friend. Your friend must choose the probabilities, let’s call these $p_i$, that they will throw the party on day $i$. You must choose the subjective probabilities, let’s call these $q_i$, describing how sure you are that the party will be on each day. Your friend is trying to maximise your expected surprise, and you are trying to minimise it.
What is your expected surprise? If the party is on Monday, which will happen with probability $p_1$, your surprise will be \[ -\log_2 q_1. \] But if the party is on Tuesday, which will happen with probability $p_2$, we need to take into account that you now know that the party wasn’t on Monday. This new information updates your probability that it’ll be on Tuesday. Your new subjective probability becomes a conditional probability:
\begin{align*} q’_2 &= \mathbb{P}(\text{on Tuesday}\,|\,\text{not on Monday})\\ &= \frac{\mathbb{P}(\text{on Tuesday \& not on Monday})}{\mathbb{P}(\text{not on Monday})} \\ &= \frac{\mathbb{P}(\text{on Tuesday})}{\mathbb{P}(\text{not on Monday})} \\ &= \frac{q_2}{1-q_1}, \end{align*}
and so your surprise will be $-\log_2 q’_2$. In general, your subjective probability that the party will be on day $i$ after seeing that it wasn’t on any previous days will be
\begin{align*} q_i’ &= \mathbb{P}(\text{on day $i$}\,|\,\text{not on day $j$ for $j < i$})\\ &=\frac{\mathbb{P}(\text{on day $i$})}{\mathbb{P}(\text{not on day $j$ for $j < i$})}\\ &= \frac{q_i}{1- \sum_{j < i} q_j}, \end{align*} and adding this all up, weighted by the $p_i$, your overall expected surprise will therefore be \[ S =\sum_i p_i \times -\log_2 q'_i. \]
Paradox vindicated?!
Remember that in the paradox, you could logic your way to never being surprised. In our new language, this would mean that you could make your expected surprise $S$ extremely small, regardless of what your friend does. How could you do this? Well, all you would need to do is make $q’_i\approx1$ for all the days. Can you do this? Yes, by choosing your probabilities in a clever way!
Suppose you decide to be 75% sure it’ll be on Monday, so $q_1 = 0.75$. Within that 25% probability of it not being on Monday, you put 75% of that 25% probability on it being on Tuesday, so $q_2 = 0.1875$. You repeat this pattern until you get to Friday, so your probabilities would look something like the chart on the next page.
This ensures that on every day except for Friday (on which you can be certain the party will be on Friday), your belief that the party will be that day has probability $q’_i = 0.75$: after ruling out the earlier days, 75% of the remaining probability is on the party being the current day.
But 75% was only an example! You could use 99%, or 99.9%, or 99.9999999%, or… By taking enough 9s, you can make your surprise as low as you want, no matter what day the party ends up being on.
This in fact closely mirrors the original paradoxical logic. On Friday morning, you will be certain the party will be on Friday evening, and so aren’t surprised when it is. On Thursday morning, based on your reasoning, you talk yourself into being (near) certain that it will be on Thursday evening, and so aren’t surprised if it is — and if it isn’t, you shift to being certain it will be on Friday. And so on: you are never surprised because you are always near certain the party will be the coming evening, whatever the day.
Surprise hide-and-seek
But this has to be cheating, right? You can’t just avoid being surprised by being certain something will happen and then, when it doesn’t, jumping to being certain the next thing will happen! Let’s have a closer look at what is going on.
Suppose the party is on Wednesday, then when your friend jumps out with confetti on Wednesday evening you’ll get a surprise of magnitude
\begin{align*} -\log_2 q’_3 &= -\log_2 \frac{q_3}{1-q_1-q_2} \\ &= -\log_2 q_3 – \left(-\log_2 (1-q_1-q_2)\right). \end{align*} Wait a second. That $-\log_2 q_3$ is how much it would have surprised you to learn on Sunday that the party would be on Wednesday. But your surprise on Wednesday evening is able to be so low because another surprise is being subtracted from this. What is this other surprise? It is the surprise from learning (as you did over Monday and Tuesday) that the party was neither on Monday nor Tuesday. The maths has found what the paradox was hiding up its sleeve: we’ve been ignoring your surprise when you thought there’d be a party but there wasn’t!
If you really were near certain there’d be a party on Monday, then when there wasn’t that should have massively surprised you, and we should be counting that. Specifically, you’d have received a surprise of magnitude \[ -\log_2 (1-q_1). \] And then on Tuesday, when there again wasn’t a party, you’d have received an extra surprise of magnitude
\begin{align*} -\log_2 (1-q’_2) &= -\log_2 \left(1-\frac{q_2}{1-q_1}\right)\\ &= -\log_2 \frac{1-q_1-q_2}{1-q_1}. \end{align*} Adding these up, we get $-\log_2 (1-q_1-q_2)$, exactly what was being subtracted to make the paradox work.
Conceptually, coming to learn day-by-day that the party isn’t on Monday, isn’t on Tuesday, and is on Wednesday conveys the same information as being told on Sunday that it would be on Wednesday, so both produce the same total surprise. This holds for all the other days too — even if the party is on Friday, your surprise at this is just felt when it doesn’t happen on Monday through Thursday. So, putting the missing surprise back in, we get that your total surprise if the party is on day $i$ is $-\log_2 q_i$, giving the new expected surprise \[ S_\text{new} = \sum_i p_i \times – \log_2 q_i. \]
Cross-entropy
This quantity has a name: it is the cross-entropy of $q$ relative to $p$. Cross-entropy plays a major role in machine learning, for exactly this reason. If you want a model to predict, say, the next word in a sentence, and your model thinks word $i$ will occur with probability $q_i$ but it actually occurs with probability $p_i$, then the cross-entropy measures how surprised your model will be on average. You can then use this metric to train your model to find the probabilities $q$ that mean it will be least surprised, and so find the model that best predicts the next word. But enough about large language models, we’re nearly at our cake!
The best surprise parties are not paradoxical
Finally, what does this tell us about the ‘best’ choice of $p$ and $q$? Remember, you want your surprise to be small, whilst your friend wants it to be big — just like the present they got you. The best strategies $q$ for you and $p$ for your friend will form what is called a Nash equilibrium: your choice of confidences $q$ must minimise your expected surprise in the event that your friend chooses the party day according to probabilities $p$; simultaneously, your friend’s choice of probabilities $p$ must maximise your expected surprise in the event that you have confidences $q$ regarding the day of the party. Which $p$ and $q$ achieve this?
We can answer this using the indifference principle: the optimal strategies will simultaneously make you indifferent to what day the party will be on and make your friend indifferent to which day you are most confident (ie, least surprised). This is only possible if you choose confidences $q$ so that you are equally surprised on every day (and so indifferent to which day is chosen) and your friend chooses probabilities $p$ so that each day is equally likely to have the party.
Thus, the optimal strategies for you and your friend are for your friend to choose a day uniformly at random, and for you to believe that each day is equally as likely as any other. Furthermore, if your friend decides to tell you their probabilities $p$, a little bit of calculus shows that — whatever $p$ is — you always minimise your surprise by picking $q=p$, that is, by believing your friend’s probabilities.
And you know what? That makes sense! Of course your friend should pick a day at random. Of course you should believe your friend who never lies. With a little bit of mathematics, we have revealed the paradox’s trick. Its logic looked valid, but only because it was cheating by hiding the rest of your surprise up its sleeve. Once we add this missing piece back in everything simplifies, and instead of a paradox we get back common sense.
Sometimes, mathematics shows us deep and shocking facts about the world, like there being different sizes of infinity. But here, we have seen the other great power of mathematics: to take something confusing, and transform it into something which makes sense. Just like your friend’s piñata, when we hit this paradox with the right stick, it turned out to be full of sweets. Mathematics is all about finding the right stick.
More from Chalkdust
In conversation with Alex Bellos
Ashleigh Ratcliffe and Sophie Maclean talk to this year's Zeeman medal winner about writing, football and donkeys
The domestication of prehistoric wolves
Alice Henman teaches us to sit..., stay..., wait...wait...no, come back! Fenton!
Can you turn a beach ball into a rubber ring?
Alba Sendón Blanco mixes scissors and beach inflatables to great effect.
Oπnions: How I became a Fields medal killjoy
Michael J Barany doesn’t want one
On the cover: crochet, community and cellular automata
Laura Taalman crafts algorithmically.
Naively adding fractions
Wayne Voo asks: what if ½ + ⅔ was ⅗?