[This is Part 1. See also Part 2.]

Introduction

The Sleeping Beauty problem has been debated ad nauseum since Elga's original paper [Elga2000], yet no consensus has emerged on its solution. I believe this confusion is due to the following errors of analysis:

• Failure to properly apply probability theory.
• Failure to construct legitimate propositions for analysis.
• Failure to include all relevant information.

The only analysis I have found that avoids all of these errors is in Radford Neal's underappreciated technical report on anthropic reasoning [Neal2007]. In this note I'll discuss how both “thirder” and “halfer” arguments exhibit one or more of the above errors, how Neal's analysis avoids them, and how the conclusions change when we alter the scenario in various ways.

As a reminder, this is the Sleeping Beauty problem:

1. On Sunday the steps of the experiment are explained to Beauty, and she is put to sleep.
2. On Monday Beauty is awakened. While awake she obtains no information that would help her infer the day of the week. Later in the day she is put to sleep again.
3. On Tuesday the experimenters flip a fair coin. If it lands Tails, Beauty is administered a drug that erases her memory of the Monday awakening, and step 2 is repeated.
4. On Wednesday Beauty is awakened once more and told that the experiment is over.

The question is this: when awakened during the experiment, what probability should Beauty give that the coin in step 3 lands Heads?

“Halfers” argue that the answer is 1/2, and “thirders” argue that the answer is 1/3. I will argue that any answer between 1/2 and 1/3 may be obtained, depending on details not specified in the problem description; but under reasonable assumptions the answer is slightly more than 1/3. Furthermore,

• halfers employ valid reasoning but get the wrong answer because they omit some seemingly irrelevant information; and
• thirders (except Neal) employ invalid reasoning that nonetheless arrives at (nearly) the right answer.

The standard framework for solving probability problems

There are actually three separate “Heads” probabilities that arise in this problem:

1. $p_1$, the probability that Beauty should give for Heads on Sunday.
2. $p_2$, the probability that Beauty should give for Heads on Monday/Tuesday.
3. $p_3$, the probability that Beauty should give for Heads on Wednesday.

There is agreement that $p_1=p_3=1/2$, but disagreement as to whether $p_2=1/2$ or $p_2=1/3$. What does probability theory tell us about how to approach this problem? The $p_i$ are all epistemic probabilities, and they are all probabilities for the same proposition—coin lands “Heads”—so any difference can only be due to different information possessed by Beauty in the three cases. The proper procedure for answering the question is then the following:

1. Construct a probabilistic model $M$ incorporating the information common to the three cases. That is, choose a set of variables that describe the situation and posit an explicit joint probability distribution over these variables. We'll assume that $M$ includes a variable $H$ which is true if the coin lands heads and false otherwise.
2. Identify propositions $X_1$, $X_2$, and $X_3$ expressing the additional information (if any) that Beauty has available in each of the three cases, beyond what is already expressed by $M$.
3. Then $p_i=Pr\left(H\mid X_i,M\right)$, which can be computed using the rule for conditional probabilities (Bayes' Rule).

Since Beauty does not forget anything she knows on Sunday, we can take $M$ to express everything she knows on Sunday, and $X_1$ to be null (no additional information).

Failure to properly apply probability theory

With the exception of Neal, thirders do not follow the above process. Instead they posit one model $M_1$ for the first and third cases, which they then toss out in favor of an entirely new model $M_2$ for the second case. This is a fundamental error.

To be specific, $M_1$ is something like this:

where $W_M$ means that Beauty wakes on Monday, $W_T$ means that Beauty wakes on Tuesday, and $Bernoulli\left(p\right)$ is the distribution on $\{false,true\}$ that assigns probability $p$ to true. $X_3$ would be Beauty's experiences and observations from the last time she awakened, and this is implicitly assumed to be irrelevant to whether $H$ is true, so that

Thirders then usually end up positing an $M_2$ that is equivalent to the following:

The first line above means that $H_M$, $T_M$, and $T_T$ are mutually exclusive, each having probability 1/3.

• $H_M$ means “the coin lands Heads, and it is Monday,”
• $T_M$ means “the coin lands Tails, and it is Monday,” and
• $T_T$ means “the coin lands Tails, and it is Tuesday.”

$M_2$ is not derived from $M_1$ via conditioning on any new information $X_2$; instead thirders construct an argument for it de novo. For example, Elga's original paper [Elga2000] posits that, if the coin lands Tails, Beauty is told it is Monday just before she is put to sleep again, and declares by fiat that her probability for $H$ at this point should be $1/2$; he then argues backwards from there as to what her probability for $H$ had to have been prior to being told it is Monday.

A red herring: betting arguments

Some thirders also employ betting arguments. Suppose that on each Monday/Tuesday awakening Beauty is offered a bet in which she wins $2 if the coin lands Tails and loses $3 if it lands Heads. Her expected gain is positive ($0.50) if she accepts the bets, since she has two awakenings if the coin lands Tails, yielding $4 in total, but will have only one awakening and lose only $3 if it lands Heads. Therefore she should accept the bet; but if she uses a probability of 1/2 for Heads on each awakening she computes a negative expected gain (-$0.50) and will reject the bet.

One can argue that Beauty is using the wrong decision procedure in the above argument, but there is a more fundamental point to be made: probability theory is logically prior to decision theory. That is, probability theory can be developed, discussed, and justified [Cox1946, VanHorn2003, VanHorn2017] entirely without reference to decision theory, but the concepts of decision theory rely on probability theory. If our probabilistic model yields $p$ as Beauty's probability of Heads, and plugging this probability into our decision theory yields suboptimal results evaluated against that same model, then this a problem with the decision theory; perhaps a more comprehensive theory is required [Yudkowsky&Soares2017].

Failure to construct legitimate propositions for analysis

Another serious error in many discussions of this problem is the use of supposedly mutually exclusive “propositions” that are neither mutually exclusive nor actually legitimate propositions. $H_M$, $T_M$, and $T_T$ can be written as

These are not truly mutually exclusive because, if $\text{not}H$, then Beauty will awaken on both Monday and Tuesday. Furthermore, the supposed propositions “it is Monday” and “it is Tuesday” are not even legitimate propositions. Epistemic probability theory is an extension of classical propositional logic [Cox1946, VanHorn2003, VanHorn2017], and applies only to entities that are legitimate propositions under the classical propositional logic—but there is no “now,” “today,” or “here” in classical logic.

Both Elga's paper and much of the other literature on the Sleeping Beauty problem discuss the idea of “centered possible worlds,” each of which is equipped with a designated individual and time, and corresponding “centered propositions”—which are not propositions of classical logic. To properly reason about “centered propositions” one would need to either translate them into propositions of classical logic, or develop an alternative logic of centered propositions; yet none of these authors propose such an alternative logic. Even were they to propose such an alternative logic, they would then need to re-derive an alternative probability theory that is the appropriate extension of the alternative propositional logic.

However, it is doubtful that this alternative logic is necessary or desirable. Time and location are important concepts in physics, but physics uses standard mathematics based on classical logic that has no notion of “now”. Instead, formulas are explicitly parameterized by time and location. Before we go off inventing new logics, perhaps we should see if standard logic will do the job, as it has done for all of science to date.

Failure to include all relevant information

Lewis [Lewis2001] argues for a probability of $p_2=1/2$, since Sunday's probability of Heads is $p_1=1/2$, and upon awakening on Monday or Tuesday Beauty has no additional information—she knew that she would experience such an awakening regardless of how the coin lands. That is, Lewis bases his analysis on $M_1$, and assumes that $X_2$ contains no information relevant to the question:

Lewis's logic is correct, but his assumption that $X_2$ contains no information of relevance is wrong. Surprisingly, Beauty's stream of experiences after awakening is relevant information, even given that her prior distribution for what she may experience upon awakening has no dependence on the day or the coin toss. Neal discusses this point in his analysis of the Sleeping Beauty problem. He introduces the concept of “full non-indexical conditioning,” which roughly means that we condition on everything, even stuff that seems irrelevant, because often our intuition is not that good at identifying what is and is not actually relevant in a probabilistic analysis. Neal writes,

…note that even though the experiences of Beauty upon wakening on Monday and upon wakening on Tuesday (if she is woken then) are identical in all "relevant" respects, they will not be subjectively indistinguishable. On Monday, a fly on the wall may crawl upwards; on Tuesday, it may crawl downwards. Beauty's physiological state (heart rate, blood glucose level, etc.) will not be identical, and will affect her thoughts at least slightly. Treating these and other differences as random, the probability of Beauty having at some time the exact memories and experiences she has after being woken this time is twice as great if the coin lands Tails than if the coin lands Heads, since with Tails there are two chances for these experiences to occur rather than only one.

Bayes' Rule, applied with equal prior probabilities for Heads and Tails, then yields a posterior probability for Tails that is twice that of Heads; that is, the posterior probability of Heads is $1/3$.

Defining the model

Verbal arguments are always suspect when it comes to probability puzzles, so let's actually do the math. Our first step is to extend $M_1$ to model $M$ as follows:

• $n_d$ is the number of distinguishable subjective moments Beauty experiences on day $d$. For simplicity we take this to be finite. If $\text{not}{W}_d$ (Beauty does not awaken on day $d$) then $n_d=0$.
• $P_{dt}$ is the stream of perceptions that Beauty remembers experiencing since awakening, as of moment $t$ on day $d$, for $1\le t\le n_d$. For simplicity we assume that there are only a finite number of distinguishable perceptions Beauty can have and remember at any point in time, as her senses are not infinitely discriminating and her memory has finite capacity. Thus there are only a finite number of possible values for $P_{dt}$.
• $P_d$ is the sequence $P_{d,1},\dots ,P_{d,n_d}$. We do not specify a particular joint distribution for $P_M$ and $P_T$ conditional on $H$ (which determines $W_M$ and $W_T$), but analyze what happens for arbitrary distributions.
• Define $R(y,d)$ to mean that at some point on day $d$, Beauty's remembered stream of experiences since awakening is $y$; that is,

• Note that $R(y,d)$ is false if $W_d$ is false.
• The fact that Beauty “obtains no information that would reveal the day of the week” (nor whether $H$ is true) means that

• We write $p\left(y\right)$ for any of these three equal probabilities.
• The fact that $H$ implies $\text{not}{W}_T$ means that

• The statement of the problem implies that the distributions for $P_M$ and $P_T$, conditional on $H$ being false, are identical, but not necessarily independent. Therefore we also define

• Writing $y$ for the stream of perceptions Beauty remembers experiencing since being awakened, her additional information after awakening is

This is the crucial point. Usually we apply Bayes' Rule by conditioning on the information that some variable has some specific value, or that its value lies in some specific range. It is very unusual to condition on this sort of disjunction (OR) of possibilities, where we know the value but not which specific variable has that value. This novelty may explain why the Sleeping Beauty problem has proven so difficult to analyze.

Analysis

The prior for $H$ is even odds:

The likelihoods are

and

Applying Bayes' Rule we obtain

Now let's consider various possibilities:

• $p\left(y\right)\ll 1$, $P_M$ and $P_T$ are independent. This is Neal's assumption, and it is a reasonable one. If the perceptions and memories Beauty can distinguish are sufficiently fine-grained, then $p\left(y\right)$ will be small for any given $y$. Then $q\left(y\right)=p\left(y\right)$, hence $q\left(y\right)\ll 1$, hence $p_2$ is slightly greater than $1/3$.
• $q\left(y\right)=0$. For example, the experimenters might have a Probabilist's Urn containing a white marble and a black marble. On Monday they reach in and choose one marble at random, placing it on the nightstand next to Beauty's bed where she will see it as soon as they awaken her. If they awaken her on Tuesday also, then they first remove Monday's marble from the nightstand and replace it with the one remaining in the urn. This guarantees that whatever Beauty experiences on Monday, she will experience something different on Tuesday. Then $p_2=1/3$ exactly.
• $q\left(y\right)=1$. That is, whatever Beauty experiences on Monday, she experiences the exact same thing on Tuesday (if she awakens on Tuesday). This could be the case if Beauty is an AI whose perceptions the experimenters completely control. Then $p_2=1/2$.
• $q\left(y\right)=2^{-k}$, $k\ge 0$. Suppose that Beauty is an AI and her only sensory experience on awakening is to receive as input a sequence of 0/1 values, chosen independently at random with equal probabilities. Then after receiving the first $k$ values in the sequence we have $q\left(y\right)=p\left(y\right)=2^{-k}$ and therefore

• (Continuing) That is, at the moment of awakening $p_2=1/2$. When Beauty receives the first value in the sequence then $p_2=1/2.5$. When she receives the second value then $p=1/2.75$, and so on, $p_2$ asymptotically approaching $1/3$ from above as she receives more of the sequence.

In fact, any value for $p_2$ between $1/2$ and $1/3$ is possible. Let $q=3-1/p$, for any desired $p$ in the range $1/3\le p\le 1/2$. If the experimenters set things up so that, with probability $q$, Beauty's Monday and Tuesday experiences are identical, and with probability $1-q$ they are different, then $p_2=p$.

Conclusion

There are three important lessons here:

• Epistemic probabilities are a function of the information one has. Thus if two people have different epistemic probabilities, or the same person at different times, there must be some identifiable difference in the information they have available.
• "Propositions" that refer to concepts such as "now," "today," or "here" are not legitimate objects of analysis for classical logic nor for probability theory. Problems that involve such concepts must be translated into classical logic using some form of explicit time or space parameterization.
• We must be very careful about discarding information considered irrelevant. It can turn out to be relevant in surprising ways.

References

[Cox1946] R. T. Cox, 1946. "Probability, frequency, and reasonable expectation," American Journal of Physics 17, pp. 1-13.

[Elga2000] A. Elga, 2000. "Self-locating belief and the Sleeping Beauty problem," Analysis 16, pp. 143-147.

[Lewis2001] D. Lewis, 2001. "Sleeping Beauty: reply to Elga," Analysis 61, pp. 171-176.

[Neal2007] R. M. Neal, 2007. "Puzzles of anthropic reasoning resolved using full non-indexical condition," Technical Report No. 0607, Dept. of Statistics, University of Toronto. Online at https://arxiv.org/abs/math/0608592.

[VanHorn2003] K. S. Van Horn, 2003. "Constructing a logic of plausible inference: a guide to Cox's Theorem," International Journal of Approximate Reasoning 34, no. 1, pp. 3-24. Online at https://www.sciencedirect.com/science/article/pii/S0888613X03000513

[VanHorn2017] K. S. Van Horn, 2017. "From propositional logic to plausible reasoning: a uniqueness theorem," Int'l Journal of Approximate Reasoning 88, pp. 309--332. Online at https://www.sciencedirect.com/science/article/pii/S0888613X16302249, preprint at https://arxiv.org/abs/1706.05261.

[Yudkowsky&Soares2017] E. Yudkowsky and N. Soares, 2017. "Functional decision theory: a new theory of instrumental rationality," https://arxiv.org/abs/1710.05060 .