Tanya Khovanova's Math Blog

I am trying to make a point that, mathematically, the Sleeping Beauty problem is resolved, and the Wikipedia article about it should stop assuming that there is an ongoing debate.

The Sleeping Beauty problem. Sleeping Beauty participates in the following experiment. On Sunday, she is put to sleep, and a fair coin is flipped. Regardless of the result of the coin flip, she is awakened on Monday and asked whether she thinks the coin was heads or tails. Regardless of her answer, if the coin was heads, the experiment ends. However, if the coin was tails, she is put back to sleep with her memory erased and awakened again on Tuesday and asked the same question. In this case, the experiment stops on Tuesday. She knows the protocol. She is awakened one morning. From her point of view, what is the probability that the coin was heads?

Here is the solution. If it is Monday, then the probability that the coin is heads is one half. So the probability of Monday/heads is the same as Monday/tails. If the coin is tails, Sleeping Beauty can’t distinguish between Monday and Tuesday. So the probability of Monday/tails is the same as Tuesday/tails. Thus, the three cases Monday/heads, Monday/tails, and Tuesday/tails are equally probable. It follows that when she is awakened, the probability of heads is one third.

However, there are still people — called halfers — who think that the probability of heads is one half.

But suppose we ask a different question.

Different question. She is awakened one morning. From her point of view, what is the probability that the day is Tuesday?

As I explained before, when she is awakened, the probability of it being Tuesday is one third. Let us calculate what the halfers think. Suppose they think that the probability of the day being Tuesday is x, then the probability of Monday is 1 − x. Let’s calculate the probability of the coin being heads from here. The probability of heads, if today is Tuesday, is zero. The probability of heads, if today is Monday, is 1/2. Therefore, the probability of heads equals 0 · x + (1 − x)/2 = (1 − x)/2. In halfers’ view, the resulting calculation equals 1/2. In other words, (1 − x)/2 = 1/2. It follows that x is zero. Doesn’t make much sense that the probability of the day being Tuesday is zero, does it?

Halfers are wrong. Wikipedia should update the article.

The Sleeping Beauty problem. Sleeping Beauty participates in the following experiment. On Sunday, she is put to sleep, and a fair coin is flipped. Regardless of the result of the coin flip, she is awakened on Monday and asked whether she thinks the coin was heads or tails. Regardless of her answer, if the coin was heads, the experiment ends. However, if the coin was tails, she is put back to sleep with her memory erased and awakened again on Tuesday and asked the same question. In this case, the experiment stops on Tuesday. She knows the protocol. She is awakened one morning. From her point of view, what is the probability that the coin was heads?

This problem is considered controversial. Some people, called halfers, think that when she is awakened, the probability that the coin was heads is one half. Other people, called thirders, think that when she is awakened, the probability that the coin was heads is one third.

I am a thirder, so let me explain my thinking. If it is Monday, then the probability that the coin is heads is one half. So the probability of Monday/heads is the same as Monday/tails. If the coin is tails, Sleeping Beauty can’t distinguish between Monday and Tuesday. So the probability of Monday/tails is the same as Tuesday/tails. Thus, the three cases Monday/heads, Monday/tails, and Tuesday/tails are equally probable, and the answer follows.

This problem is similar to the Monty Hall problem in some ways. The main difference is that The Monty Hall problem stopped being controversial, while Sleeping Beauty problem continues to be. The best argument that helped intuition and led to the resolution of the Monty Hall problem was increasing the number of doors. Similarly, for the Sleeping Beauty problem, we can increase the number of days she is put back to sleep when the coin is tails. Forgive me for the cruelty of this theoretical experiment.

The Sleeping Beauty Variation. Sleeping Beauty participates in the following experiment. On Sunday, she is put to sleep, and a fair coin is flipped. Regardless of the result of the coin flip, she is awakened on Monday and asked whether she thinks the coin was heads or tails. Regardless of her answer, if the coin was heads, the experiment ends. However, if the coin was tails, the experiment continues for 99 more days. Each day, she is put back to sleep with her memory erased and awakened the next day and asked the same question. She knows the protocol. She is awakened one morning. From her point of view, what is the probability that the coin was heads?

In this variation, when she is awakened, she should be almost sure that the coin was tails. I hope it will help halfers feel that, in this case, the probability of heads can’t be one half. For me, the argument is the same as before, making the probability that the coin was heads is 1 over 101.

After I wrote this essay, I discovered that Nick Bostrom made the same argument. Though, for tails, he put Sleeping Beauty to sleep one million and one times, which is about 2,740 years. He increased my one hundred days by several orders of magnitude, amplifying our point. Surely, when Sleeping Beauty awakens, she should be almost certain that the coin was tails. After Sleeping Beauty agrees to so much torture, why is the problem still controversial?

by Tanya Khovanova and Alexey Radul

We already blogged about the Sleeping beauty problem three times: The Sleeping Beauty Problem, Sleeping Beauty Meets Monty Hall, and Sleeping Beauty and Mondays. The posts were more than ten years ago, but the mathematical community seems to continue being stuck on this problem. So we come back to it.

Problem. Sleeping Beauty participates in the following experiment. On Sunday, she is put to sleep, and a fair coin is flipped. Regardless of the result of the coin flip, she is awakened on Monday and asked whether she thinks the coin was heads or not. If the coin was tails, however, she is put back to sleep with her memory erased, awakened on Tuesday and asked the same question again. She knows the protocol. She is awakened one morning: What is her probability that the coin was heads?

Let’s raise the stakes a little bit. Suppose a prize of $1K is set aside for her correct guess of a flip. What should be her strategy?

The problem is ambiguous. We didn’t tell you how the prizes are awarded. We see several reasonable scenarios:

1. Sleeping Beauty gets the prize if she is right on Monday.
2. Sleeping Beauty gets the prize if she is right on Tuesday.
3. Sleeping Beauty gets the prize for every correct answer.
4. Sleeping Beauty gets the prize if she guesses correctly all the questions she is asked.
5. Sleeping Beauty gets the prize if she is right at least once.
6. Sleeping Beauty gets the prize if she is right for a randomly chosen answer. This means, if the coin is heads, she get the prize if she is right on Monday. If the coin is tails, then one of her two answers is chosen randomly, and she gets the prize if she is correct.

Because of selective amnesia, she can’t distinguish between her awakenings, thus her strategy has to be the same at every awakening. That is, she should say heads with probability p. The exact number depends on the scenario:

1. First scenario: It doesn’t matter what value of p she chooses. With a probability 1/2, she wins one grand.
2. Second scenario: She should choose p = 0. Her best strategy is to always say tails. With a probability 1/2 (when the coin is tails), she wins one grand.
3. Third scenario: She should choose p = 0. Her best strategy is to always say tails. With a probability 1/2, she wins two grand.
4. Fourth scenario: p = 0 or p = 1. Her best strategy is to stick with the same answer all the time; and it doesn’t matter what answer she chooses. With probability 1/2, she wins one grand.
5. Fifth scenario: She should choose p = 1/2. Her best strategy is to flip a coin herself each time and say tails with probability of 1/2. This way, her chances to win one grand are 5/8.
6. Sixth scenario: It doesn’t matter what value of p she chooses. With a probability 1/2, she wins one grand.

We see that though she is asked to guess the outcome of the coin flip and is rewarded for guessing correctly, her strategy is not to try to maximize the probability of guessing correctly each time. The strategy depends on the reward protocol.

We see that in the first and the sixth scenario, she gets one guess per coin flip. Not surprisingly, it doesn’t matter what she chooses to do. The classic Sleeping Beauty problem corresponds to the third scenario. If she wants to improve her chances per guess, she should favor tails.

Let’s look at the following variation.

Problem. Suppose Sleeping Beauty’s goal is to guess right once, but if she guesses right on Monday, she wins and is not put back to sleep. If she guesses wrong on Monday and the coin was tails, she is put back to sleep with he memory erased. That is, she is given a second chance. What’s the right strategy in this case?

As her memory is erased, the only strategy is to do the same thing each time she is awakened. That is to guess heads with probability p. Thus, she guesses correctly at least once with probability p/2 + (1–p)/2 + p(1–p)/2. We see that whatever strategy she chooses, she guesses with probability one half on Monday. She gets an additional chance of p(1–p)/2 to get a correct guess on Tuesday. Her worst strategy is to always guess tails or heads. Her best strategy is to flip a fair coin each time. This way, she has an additional probability of 1/8 to win on Tuesday.

Here is a question to our readers, for the best strategy above, what is her probability on waking that the coin is actually heads? Here is the problem more formally.

Problem. Sleeping Beauty participates in the following experiment. On Sunday, she is put to sleep, and a fair coin is flipped. Regardless of the result of the coin flip, she is awakened on Monday and asked whether she thought the coin was heads or not. Sleeping Beauty answers by flipping a fair coin. If she guesses correctly, or if the Sunday coin was heads, the experiment ends. If the Sunday coin was tails and different from her guess, she is put back to sleep with her memory erased, awakened on Tuesday, and asked the same question again. She knows the protocol. She is awakened one morning: What is her probability that the Sunday coin was heads?

I love Toblerone, but I never paid attention to its logo.

This Swiss chocolate was created in Bern (Berne) more than a hundred years ago. A legend says that Berne’s founder loved hunting and vowed to name the city after the first animal he met on his hunt. The animal happened to be a bear, and so the town was named Berne. The bear became a big deal for the town; you even can find the bear on the town’s flag and coat of arms.

Theodor Tobler, the creator of Toblerone, put the famous local mountain, Matterhorn, in the logo of Toblerone and hid a bear in the image. He obviously loved his country and town.

Tobler was clearly a wordsmith and invented a fascinating name for his chocolate. As Wikipedia explains, the name Toblerone is a portmanteau combining Tobler’s name with the Italian word torrone, which is a type of nougat used in his chocolate. However, Wikipedia doesn’t explain that the word Toblerone also contains a secret: the word BERNE (bear).

After writing this, I couldn’t resist and bought some dark Toblerone chocolate. Now it brings me pleasure in more ways than one.

There are many cute math problems that use the trivial fact announced in the title. For example, I recently posted the following problem from the 43rd Tournament of Towns.

Problem. Find the largest number n such that for any prime number p greater than 2 and less than n, the difference n − p is also a prime number.

Solution. Prime numbers 3, 5, and 7 have different remainders modulo 3. Thus, for any n, one of the numbers n − 3, n − 5, or n − 7 is divisible by 3. If n > 10, that number that is divisible by 3 is also greater than 3, thus, making it composite. Therefore, the answer to this problem is not greater than 10. Number 10 works, thus, the answer is 10.

Here is another problem using the fact that 3, 5, and 7 have different remainders when divided by 3.

Problem. Find the maximum integer n, such that for any prime p, where p < n, the number n + 2p is prime.

Here is the current picture of my coauthor, Joel Lewis. I remember him from many years ago when he was a graduate student at MIT. I am glad he kept his big smile.

Back to the subject matter. Joel Lewis made a comment on my recent post, thinking-outside-the-box ideas. He mentioned his two theorems:

The Big Point Theorem. Any three lines intersect at a point, provided that the point is big enough.

The Thick Line Theorem. Any three points lie on the same line, provided that the line is thick enough.

I grew up a purist. Mathematics was about mathematics, not about gender. I personally would never have competed in a math competition exclusively for girls. I would have felt diminished somehow. Furthermore, suppose there were separate math competitions for boys, where girls were not allowed. I would have felt outraged. By symmetry, I should have been outraged by math competitions exclusively for girls.

When I first heard about math competitions for girls, I was uncomfortable. I also noticed that my Eastern European friends shared my feelings, while my other friends did not.

There was a stage in my life when I lived in Princeton for seven years and became friends with Ingrid Daubechies, who is NOT Eastern European. She didn’t share my extreme views, and we argued a lot. Every spring, there was a big conference for Women-in-Mathematics at the Institute for Advanced Study in Princeton. But I was stubborn and completely ignored it. With one exception: when Ingrid gave a lecture there, I went just to hear her talk.

In 2008, I was living in Boston, worrying about money, as I had just resigned from my industry work to return to mathematics. Out of the blue, Ingrid called to offer me a job at that very same Women-in-Mathematics conference. I admire Ingrid and got excited about working with her. More importantly, I needed the money. So I decided to put aside my prejudice and take the job.

Being part of the conference was a revelation. Although most of the two-week conference was spent on mathematics, there were some women-and-math seminars. There, women discussed bullying by advisers and colleagues, impostor syndrome, workplace bias, the two-body problem, and other issues. And guess what? I went through all of that too. I just never realized it and never talked about it.

My biggest regret was that I hadn’t attended the conference earlier. Plus, the conference didn’t feel unfair towards men: all lectures and math seminars were open to the public, and some courageous guys sat in.

What about my symmetry test? What happens if we swap genders? Should there be separate math conferences for men, open to the public? The idea makes me laugh. Women are in the minority in math, and many conferences already feel like conferences for men open to the public. My symmetry test doesn’t quite work.

But, while I saw how helpful the support was for female mathematicians and for me, something still bugs me. Where is the fine line between minority support and unfairness? Let’s look at math clubs for girls. On the surface, there are so many math clubs, so why not have the occasional math club for girls? I can imagine a girl, not me, who would prefer to attend such a club. However, girls’ clubs often have sponsors and are much cheaper to attend than regular clubs. This is unfair to boys whose parents can’t afford a regular club. It also becomes counterproductive for girls. What if some girls go to such a club, not because they need a special environment but because it is a cheaper club? They are missing out on the fun of learning math together with boys. (Trust me, I know!) So, I am not sure where that line is.

I am older and wiser now. I do not run away from events organized for women in math. I think lunches and dinners for women in math are great. They help female mathematicians find mentors, build networks, and stay in mathematics.

What about my original question: Should there be separate math competitions for girls? In a truly equal society, math competitions should be for everyone. And, though I do not actively oppose girls’ competitions anymore, I hope the need for them will die out in my lifetime.

Recently, I stumbled upon three lovely logic puzzles, while scrolling Facebook for news from the Russia-Ukraine war. I will start with an easy puzzle.

Puzzle. A traveler got to an island, where each resident either always tells the truth or always lies. A hundred islanders stood in a circle facing the center, and each told the traveler whether their neighbor to the right was a truth-teller. Based on these statements, the traveler was able to clearly determine how many times he had been lied to. Can you do the same?

In the next puzzle, there is another island where people are either truth-tellers or normal. There are three questions that increase in difficulty.

Puzzle. You are on an island with 65 inhabitants. You know that 63 inhabitants are truth-tellers who always tell the truth, and the other 2 are normal, who can either lie or tell the truth. You are allowed one type of question, “Are all the people on this list truth-tellers?” This question requires a list, which you can create yourself. Moreover, you can have as many different lists as you want. You can pose this question to any islander any number of times. Your goal is to find the two normal people. The easy task is to do it in 30 questions. The medium task is to do it in 14 questions. The hard task is to figure out whether it is possible to do it in fewer than 14 questions.

Here is the last puzzle.

Puzzle. You got to an island with 999 inhabitants. The island’s governor tells you, “Each of us is either a truth-teller who always tells the truth, or a liar who always lies. ” You go around the island asking each person the same question, “How many liars are on the island?” You get the following replies.
First person, the governor: “There is at least one liar on the island.”
The second person: “There are at least two liars on the island.”
This continues progressively until the 999th person says: “There are at least 999 liars on the island.”
What can you tell about the number of liars and truth-tellers on this island?

I recently wrote an essay, Thinking Inside and Outside the Box, which starts with a famous nine-dots puzzle that kicked off the expression: thinking outside the box. Here is another puzzle with the same nine-dots setup.

Puzzle. What is the smallest number of squares needed to ensure that each dot is in its own region?

Usually, people who try to solve this puzzle come up with the following four-squares solution.

As with the classic nine-dots puzzle, they imagine that the dots are on a grid and try to build squares with sides parallel to the grid lines. What would be the outside-the-box idea? The sides of the squares would not need to be parallel to the grid. This way, we can solve the puzzle with three squares.

One of my MathRoots students offered a different and awesome solution also using three squares.

Problem. Find the largest number n such that for any prime number p greater than 2 and less than n, the difference n − p is also a prime number.