Last year I wrote on a couple of occasions about the Sleeping Beauty problem. The problem raises some tricky questions and I did promise to attempt to answer the questions, which I am yet to do. Only last week, I was discussing the problem again with my friend Giulio, whose paper on the subject I published here. That discussion prompted me to go back to the inspiration for the original post: a series of posts on the Bob Walter’s blog. I re-read all of his posts, including his fourth post on the topic, which began:

I have been waiting to see some conclusions coming from discussions of the problem at the Stubborn Mule blog, however the discussion seems to have petered out without a final statement.

Sadly, even if I do get to my conclusions, I will not be able to get Bob’s reaction, because last week he died and the world has lost a great, inspirational mathematician.

Bob was my supervisor in the Honours year of my degree in mathematics and he also supervised Giulio for his PhD. Exchanging emails with Giulio this week, we both have vivid memories of an early experience of Bob’s inspirational approach to mathematics. This story may not resonate for everyone, but I can assure you that there are not many lectures from over 25 years ago that I can still recall.

The scene was a 3rd year lecture on Categories in Computer Science. Bob started talking about stacks, a very basic data structure used in computing. You should think of a stack of plates: you can put a plate on the top of the stack, or you can take one off. Importantly, you only push on or pop off plates from the top of the stack (unless you want your stack to crash to the floor). And how should a mathematician think about a stack? As Bob explained it, from the perspective of a category theorist, the key to understanding stacks is to think about pushing and popping as inverse functions. Bear with me, and I will take you through his explanation.

Rather than being a stack of plates, we will work with a stack of a particular type of data and I will denote by X the set of possible data elements (X could denote integers, strings, Booleans, or whatever data type you like). Stacks of type X will then be denoted by S. Our two key operations are push and pop.

The push operation takes an element of X and a stack and returns a new stack, which is just the old stack with the element of X added on the top. So, it’s a function push: X × S  → S. Conversely, pop is a function S  → X × S  which takes a stack and returns the top element and a stack, which is everything that’s left after you pop the top.

So far, so good, but there are some edge cases to worry about. We should be able to deal with an empty stack, but what if we try to pop an element from the empty stack? That doesn’t work, but we can deal with this by returning an error state. This means that we should really think of pop as a function pop: S  → X × S + I, where I is a single element set, say {ERR}. Here the + is a (disjoint) union of sets, which means that the pop function will either return a pair (an element of X and a stack) or an error state. This might be a bit confusing, so to make it concrete, imagine I have a stack s = (x₁, x₂, x₃) then

pop((x₁, x₂, x₃)) = (x₁, (x₂, x₃))

and this ordered pair of data element x₁ and (shorter) stack (x₂, x₃) is an element of X × S. Now if I want to pop an empty stack (), I have

pop(()) = ERR

which is in I. So pop will always either return an element of X × S or an element of I (in fact, the only element there is).

This should prompt us to revisit push as well, which should really be considered as a function push: X × S + I → S which, given an element of X and a stack will combine them, but given the single element of I will return an empty stack, so push(ERR) = ().

The key insight now is that pop and push are inverses of each other. If I push an element onto a stack and pop it again, I get back my element and the original stack. If I pop an element from a stack and push it back on, I get back my original stack. Extending these functions X × S + I ensures that this holds true even for the edge cases.

But if push and pop are inverses then X × S + I  and S must essentially be the same—mathematically they are isomorphic. This is where the magic begins. As Bob said in is lecture, “let’s be bold like Gauss“, and he proceeded with the following calculation:

X × S + I = S

I = S – X × S = S × (I – X)

S = I / (I – X)

and so

S = I + X + X² + X³ + …

The last couple of steps are the bold ones, but actually make sense. The last equation basically says that a stack is either an empty stack, a single element of X, an ordered pair of elements of X, an ordered triple of elements of X and so on.

I’d known since high school that 1/(1-x) could be expanded to 1 + x  + x² + x³ + …, but applying this to a data structure like stacks was uncharted territory. I was hooked, and the following year I had the privilege of working with Bob on my honours thesis and that work ultimately made it into a couple of joint papers with Bob.

I haven’t seen Bob face to face for many years now, but we have occasionally kept in touch through topics of mutual interest on our blogs. While I have not kept up with his academic work, I have always considered him more than just a brilliant mathematician. He was a creative, inspirational, radical thinker who had an enormous influence on me and, I know, many others.

RFC Walters, rest in peace.

If you read the last post on the Sleeping Beauty problem, you may recall I did not pledge allegiance to either the “halfer” or the “thirder” camp, because I was still thinking my position through. More than a month later, I still can’t say I am satisfied. Mathematically, the thirder position seems to be the most coherent, but intuitively, it doesn’t seem quite right.

Mathematically the thirder position works well because it is the same as a simpler problem. Imagine the director of the research lab drops in to see how things are going. The director knows all of the details of the Sleeping Beauty experiment, but does not know whether today is day one or two of the experiment. Looking in, she sees Sleeping Beauty awake. To what degree should she believe that the coin toss was Heads? Here there is no memory-wiping and the problem fits neatly into standard applications of probability and the answer is 1/3.

My intuitive difficulty with the thirder is better expressed with a more extreme version of the Sleeping Beauty problem. Instead of flipping the coin once, the experimenters flip the coin 19 times. If there are 19 tails in a row (which has a probability of 1 in 524,288), Sleeping Beauty will be woken 1 million times. Otherwise (i.e. if there was at least one Heads tossed), she will only be woken once. Following the standard argument of the thirders, when Sleeping Beauty is awoken and asked for her degree of belief that the coin tosses turned up at least one Heads, she should say approximately 1/3 (or more precisely, 524287/1524287). Intuitively, this doesn’t seem right. Notwithstanding the potential for 1 million awakenings, I would find it hard to bet against something that started off as a 524287/524288 chance. Surely when Sleeping Beauty wakes up, she would be quite confident that at least one Heads came up and she is in the single awakening scenario.

Despite the concerns my intuition throws up, the typical thirder argues that Sleeping Beauty should assign 1/3 to Heads on the basis that she and the director have identical information. For example, here is an excerpt from a comment by RSM on the original post:

I want to know if halfers believe that two people with identical information about a problem, and with an identical set of priors, should assign identical probabilities to a hypothesis. I see the following possibilities:

1. The answer is no -> could be a halfer (but not necessarily).
2. The answer is yes, but the person holds that conditionalization is not a valid procedure –> could be a halfer.
3. The answer is yes and the person accepts conditionalization, but does not accept that the priors for the four possibilities in the Sleeping Beauty puzzle should be equal –> could be a halfer.
4. Otherwise, must be a thirder.

My intuition suggests, in a way I struggle to make precise, that Sleeping Beauty and the director do not in fact have identical information. All I can say is that Sleeping Beauty knows she will be awake on Monday (even if she subsequently forgets the experience), but the director may not observe Sleeping Beauty on Monday at all.

Nevertheless, option 2 raises interesting possibilities, on that have been explored in a number of papers. For example in D.J. Bradley’s “Self-location is no problem for conditionalization“, Synthese 182, 393–411 (2011), it is argued that learning about temporal information involves “belief mutation”, which requires a different approach to updating beliefs than “discovery” of non-temporal information, which makes use of conditionalisation.

All of this serves as a somewhat lengthy introduction to an interesting approach to the problem developed by Giulio Katis, who first introduced me to the problem. The Stubborn Mule may not be a well-known mathematical imprint, but I am pleased to be able to publish his paper, Sleeping Beauty, the probability of an experiment being in a state, and composing experiments, here on this site. In this post I will include excerpts from the paper, but encourage those interested in a mathematical framing of a halfer’s approach to the problem. I am sure that Giulio will welcome comments on the paper.

Giulio begins:

The view taken in this note is that the contention between halfers and thirders over the Sleeping Beauty (SB) problem arises primarily for two reasons. The first reason relates to exactly what experiment or frame of reference is being considered: the perspective of SB inside the experiment, or the perspective of an external observer who chooses to randomly inspect the state of the experiment. The second reason is that confusion persists because most thirders and halfers have not explicitly described their approach in terms of generally defining a concept such as “the probability of an experiment being in a state satisfying a property P conditional on the state satisfying property C”.

Here Giulio harks back to Bob Walters’ distinction between experiments and states. In the context of the Sleeping Beauty problem, the “experiment” is a full run from coin toss, through Monday and Tuesday, states are a particular point in the experiment and as an example, P could be a state with the coin toss being Heads and C being a state in which Sleeping Beauty is awake.

From here, Giulio goes on to describe two possible “probability” calculations. The first would be familiar to thirders and Giulio notes:

What thirders appear to be calculating is the probability that an external observer randomly inspecting the state of an experiment finds the state to be satisfying P . Indeed, someone coming to randomly inspect this modified SB problem (not knowing on what day it started) is twice as likely to find the experiment in the case where tails was tossed. This reflects the fact that the reference frame or ‘time­frame’ of this external observer is different to that of (or, shall we say, to that ‘inside’) the experiment they have come to observe. To formally model this situation would seem to require modelling an experiment being run within another experiment.

The halfer approach is then characterised as follows:

The halfers are effectively calculating as follows: first calculate for each complete behaviour of the experiment the probability that the behaviour is in a state satisfying property P; and then take the expected value of this quantity with respect to the probability measure on the space of behaviours of the experiment. Denote this quantity by Π_X(P) .

An interesting observation about this definition follows:

Note that even though at the level of each behaviour the ‘probability of being in a state satisfying P’ is a genuine probability measure, the quantity Π_X(P) is not in general a probability measure on the set of states of X . Rather, it is an expected value of such probabilities. Mathematically, it fails in general to be a probability measure because the normalization denominators n(p) may vary for each path. Even though this is technically not a probability measure, I will, perhaps wrongly, continue to call Π_X(P) a probability.

I think that this is an important observation. As I noted at the outset, the mathematics of the thirder position “works”, but typically halfers end up facing all sorts of nasty side-effects. For example, an incautious halfer may be forced to conclude that, if the experimenters tell Sleeping Beauty that today is Monday then she should update her degree of belief that the coin toss came up Heads to 2/3. In the literature there are some highly inelegant attempts to avoid these kinds of conclusions. Giulio’s avoids these issues by embracing the idea that, for the Sleeping Beauty problem, something other than a probability measure may be more appropriate for modelling “credence”:

I should say at this point that, even though Π_X(P) is not technically a probability, I am a halfer in that I believe it is the right quantity SB needs to calculate to inform her degree of ‘credence’ in being in a state where heads had been tossed. It does not seem Ξ_X(P) [the thirders probability] reflects the temporal or behavioural properties of the experiment. To see this, imagine a mild modification of the SB experiment (one where the institute in which the experiment is carried out is under cost pressures): if Heads is tossed then the experiment ends after the Monday (so the bed may now be used for some other experiment on the Tuesday). This experiment now runs for one day less if Heads was tossed. There are two behaviours of the experiment: one we denote by p_Tails which involves passing through two states S₁ = (Mon, Tails), S₂ = (Tue, Tails) ; and the other we denote by p_Heads which involves passing through one state S₃ = (Mon,Heads). Let P = {S₃}, which corresponds to the behaviour pHeads . That is, to say the experiment is in P is the same as saying it is is in the behaviour p_Heads. Note π(p_Heads) = 1/2 , but Ξ_X(P) = 1/3 . So the thirders view is that the probability of the experiment being in the state corresponding to the behaviour p_Heads (i.e. the probability of the experiment being in the behaviour p_Heads) is actually different to the probability of p_Heads occurring!

This halfer “probability” has some interesting characteristics:

There are some consequences of the definition for Π_X(P) above that relate to what some thirders claim are inconsistencies in the halfers’ position (to do with conditioning). In fact, in the context of calculating such probabilities, a form of ‘interference’ can arise for the series composite of two experiments (i.e. the experiment constructed as ‘first do experiment 1, then do experiment 2’), which does not arise for the probabilistic join of two experiments (i.e. the experiment constructed as ‘with probability p do experiment 1, with probability 1-­p do experiment 2’).

…

In a purely formal manner (and, of course, not in a deeper physical sense) this ‘non­locality’, and the importance of defining the starting and ending states of an experiment when calculating probabilities, reminds me of the interference of quantum mechanical experiments (as, say, described by Feynman in the gem of a book QED). I have no idea if this formal similarity has any significance at all or is completely superficial.

Giulio goes on to make an interesting conjecture about composition of Sleeping Beauty experiments:

We could describe this limiting case of a composite experiment as follows. You wake up in a room with a white glow. A voice speaks to you. “You have died, and you are now in eternity. Since you spent so much of your life thinking about probability puzzles, I have decided you will spend eternity mostly asleep and only be awoken in the following situations. Every Sunday I will toss a fair coin. If the toss is tails, I will wake you only on Monday and on Tuesday that week. If the toss is heads, I will only wake you on Monday that week. When you are awoken, I will say exactly the same words to you, namely what I am saying now. Shortly after I have finished speaking to you, I will put you back to sleep and erase the memory of your waking time.” The voice stops. Despite your sins, you can’t help yourself, and in the few moments you have before being put back to sleep you try to work out the probability that the last toss was heads. What do you decide it is?

In this limit, Giulio argues that a halfer progresses to the thirder position, assigning 1/3 to the probability that the last toss was heads!

These brief excerpts don’t do full justice to the framework Giulio has developed, but I do consider it a serious attempt to encompass all of the temporal/non-temporal, in-experiment/out-of-experiment subtleties that the Sleeping Beauty problem throws up. This paper is only for the mathematically inclined and, like so much written on this subject, I doubt it will convince many thirders, but if nothing else I hope it will put Giulio’s mind at rest having the paper published here on the Mule. Over recent weeks, his thoughts have been as plagued by this problem as have mine.