The Sleeping Beauty Paradox The situation
Some researchers would like to put you to sleep.  Depending on the secret toss of a fair coin, they will briefly awaken you either once (Heads) or twice (Tails).  After each waking, they will put you back to sleep with a drug that makes you forget that awakening.  When you are awakened, to what degree should you believe that the outcome of the coin toss was Heads?
(OK, maybe you don’t want to be the subject of this experiment!  Suppose instead that Sleeping Beauty (SB) agrees to it (with the full approval of the Magic Kingdom’s Institutional Review Board, of course).  She’s about to go to sleep for one hundred years, so what are one or two more days, anyway?)

[Detail of a Maxfield Parrish illustration.]
Are you a Halfer or a Thirder?
The Halfer position.  Simple! The coin is fair--and SB knows it--so she should believe there's a one-half chance of heads.
The Thirder position. Were this experiment to be repeated many times, then the coin will be heads only one third of the time SB is awakened.  Her probability for heads will be one third.
Thirders have a problem
Most, but not all, people who have written about this are thirders.  But:

*

*On Sunday evening, just before SB falls asleep, she must believe the chance of heads is one-half: that’s what it means to be a fair coin.


*Whenever SB awakens, she has learned absolutely nothing she did not know Sunday night.  What rational argument can she give, then, for stating that her belief in heads is now one-third and not one-half?
Some attempted explanations

*

*SB would necessarily lose money if she were to bet on heads with any odds other than 1/3.  (Vineberg, inter alios)


*One-half really is correct: just use the Everettian “many-worlds” interpretation of Quantum Mechanics!  (Lewis).


*SB updates her belief based on self-perception of her “temporal location” in the world.  (Elga, i.a.)


*SB is confused: “[It] seems more plausible to say that her epistemic state upon waking up should not include a definite degree of belief in heads. … The real issue is how one deals with known, unavoidable, cognitive malfunction.”  [Arntzenius]

The question
Accounting for what has already been written on this subject (see the references as well as a previous post), how can this paradox be resolved in a statistically rigorous way?  Is this even possible?

References
Arntzenius, Frank (2002).  Reflections on Sleeping Beauty Analysis 62.1 pp 53-62.
Bradley, DJ (2010).  Confirmation in a Branching World: The Everett Interpretation and Sleeping Beauty.  Brit. J. Phil. Sci. 0 (2010), 1–21.
Elga, Adam (2000).  Self-locating belief and the Sleeping Beauty Problem.  Analysis 60 pp 143-7.
Franceschi, Paul (2005).  Sleeping Beauty and the Problem of World Reduction.  Preprint.
Groisman, Berry (2007).  The end of Sleeping Beauty’s nightmare.  Preprint.
Lewis, D (2001).  Sleeping Beauty: reply to Elga.  Analysis 61.3 pp 171-6.
Papineau, David and Victor Dura-Vila (2008).  A Thirder and an Everettian: a reply to Lewis’s ‘Quantum Sleeping Beauty’.
Pust, Joel (2008).  Horgan on Sleeping Beauty.  Synthese 160 pp 97-101.
Vineberg, Susan (undated, perhaps 2003).  Beauty’s Cautionary Tale.
 A: "Whenever SB awakens, she has learned absolutely nothing she did not know Sunday night." This is wrong, as wrong as saying "Either I win the lottery or I don't, so the probability is $50\%$." She has learned that she has woken up. This is information. Now she should believe each possible awakening is equally likely, not each coin flip.
If you are a doctor and a patient walks into your office, you have learned that the patient has walked into a doctor's office, which should change your assessment from the prior. If everyone goes to the doctor, but the sick half of the population goes $100$ times as often as the healthy half, then when the patient walks in you know the patient is probably sick.
Here is another slight variation. Suppose whatever the outcome of the coin toss was, Sleeping Beauty will be woken up twice. However, if it is tails, she will be woken up nicely twice. If it is heads, she will be woken up nicely once, and will have a bucket of ice dumped on her once. If she wakes up in a pile of ice, she has information that the coin came up heads. If she wakes up nicely, she has information that the coin probably didn't come up heads. She can't have a nondegenerate test whose positive result (ice) tells her heads is more likely without the negative result (nice) indicating that heads is less likely. 
A: 
When you are awakened, to what degree should you believe that the outcome of the coin toss was Heads?

What do you mean by "should"? What are the consequences of my beliefs? In such an experiment I wouldn't believe anything. This question is tagged as decision-theory, but, the way this experiment is conceived, I have no incentive to make a decision.
We can modify the experiment in different ways, so that I feel inclined to give an answer. For example, I might have a guess on whether I was awaken because of "Heads" or "Tails", and I'd earn a candy for each correct answer I give. In that case, obviously, I'd decide on "Tails", because, in repeated experiments, I'd earn one candy per experiment on average: In 50% of the cases, the toss would be "Tails", I'd be awaken twice and I'd earn a candy both times. In the other 50% ("Heads") I'd earn nothing. Should I answer "Heads", I'd be earning only half a candy per experiment, because I'd get only one chance to answer and I'd be correct 50% of the time. If I'd myself toss a fair coin for the answer, I'd be earning $3/4$ of a candy.
Another possibility is to earn a candy for each experiment in which all my answers were correct. In that case, it doesn't matter which systematic answer I give, since, on average, I'll be earning half a candy per experiment: If I decide on answering "Heads" all of the time, I'd be correct in 50% of the cases, and the same holds for "Tails". Only if I toss a coin myself, I'd be earning $3/8$ of a candy: In 50% of the cases the researchers would toss "Heads", and in 50% thereof I'd toss "Heads", too, earning me $1/4$ of a candy. In the other 50% of the cases, when the researches tossed "Tails", I'd have to toss "Tails" twice, which would happen only in $1/4$ of the cases, so that this would earn me only $1/8$ of a candy.

how can this paradox be resolved in a statistically rigorous way? Is this even possible?

Define "statistically rigorous way". The question about a belief is of no practical relevance. Only actions matter.
A: Strategy
I would like to apply rational decision theory to the analysis, because that is one well-established way to attain rigor in solving a statistical decision problem.  In trying to do so, one difficulty emerges as special: the alteration of SB’s consciousness.

*

*Rational decision theory has no mechanism to handle altered mental states.


*In asking SB for her credence in the coin flip, we are simultaneously treating her in a somewhat self-referential manner both as subject (of the SB experiment) and experimenter (concerning the coin flip).
Let’s alter the experiment in an inessential way: instead of administering the memory-erasure drug, prepare a stable of Sleeping Beauty clones just before the experiment begins.  (This is the key idea, because it helps us resist distracting--but ultimately irrelevant and misleading--philosophical issues.)

*

*The clones are like her in all respects, including memory and thought.


*SB is fully aware this will happen.

We can clone, in principle.  E. T. Jaynes replaces the question "how can we build a mathematical model of human common sense"--something we need in order to think through the Sleeping Beauty problem--by "How could we build a machine which would carry out useful plausible reasoning, following clearly defined principles expressing an idealized common sense?"  Thus, if you like, replace SB by Jaynes' thinking robot, and clone that.
(There have been, and still are, controversies about "thinking" machines.

"They will never make a machine to replace the human mind—it does many things which no machine could ever do."


You insist that there is something a machine cannot do.  If you will tell me precisely what it is that a machine cannot do, then I can always make a machine which will do just that!”

--J. von Neumann, 1948.  Quoted by E. T. Jaynes in Probability Theory: The Logic of Science, p. 4.)

--Rube Goldberg
The Sleeping Beauty experiment restated
Prepare $n \ge 2$ identical copies of SB (including SB herself) on Sunday evening.  They all go to sleep at the same time, potentially for 100 years. Whenever you need to awaken SB during the experiment, randomly select a clone who has not yet been awakened. Any awakenings will occur on Monday and, if needed, on Tuesday.
I claim that this version of the experiment creates exactly the same set of possible results, right down to SB's mental states and awareness, with exactly the same probabilities.  This potentially is one key point where philosophers might choose to attack my solution.  I claim it's the last point at which they can attack it, because the remaining analysis is routine and rigorous.
Now we apply the usual statistical machinery.  Let's begin with the sample space (of possible experimental outcomes).  Let $M$ mean "awakens Monday" and $T$ mean "awakens Tuesday."  Similarly, let $h$ mean "heads" and $t$ mean "tails".  Subscript the clones with integers $1, 2, \ldots, n$.  Then the possible experimental outcomes can be written (in what I hope is a transparent, self-evident notation) as the set
$$\eqalign{
\{&hM_1, hM_2, \ldots, hM_n, \\
&(tM_1, tT_2), (tM_1, tT_3), \ldots, (tM_1, tT_n), \\
&(tM_2, tT_1), (tM_2, tT_3), \ldots, (tM_2, tT_n), \\
&\cdots, \\
&(tM_n, tT_1), (tM_n, tT_2), \ldots, (tM_n, tT_{n-1}) & \}.
}$$
Monday probabilities
As one of the SB clones, you figure your chance of being awakened on Monday during a heads-up experiment is ($1/2$ chance of heads) times ($1/n$ chance I’m picked to be the clone who is awakened).  In more technical terms:

*

*The set of heads outcomes is $h = \{hM_j, j=1,2, \ldots,n\}$.  There are $n$ of them.


*The event where you are awakened with heads is $h(i) = \{hM_i\}$.


*The chance of any particular SB clone $i$ being awakened with the coin showing heads equals $$\Pr[h(i)] = \Pr[h] \times \Pr[h(i)|h] = \frac{1}{2} \times 
\frac{1}{n} = \frac{1}{2n}.$$
Tuesday probabilities

*

*The set of tails outcomes is $t = \{(tM_j, tT_k): j \ne k\}$.  There are $n(n-1)$ of them.  All are equally likely, by design.


*You, clone $i$, are awakened in $(n-1) + (n-1) = 2(n-1)$ of these cases; namely, the $n-1$ ways you can be awakened on Monday (there are $n-1$ remaining clones to be awakened Tuesday) plus the $n-1$ ways you can be awakened on Tuesday (there are $n-1$ possible Monday clones).  Call this event $t(i)$.


*Your chance of being awakened during a tails-up experiment equals $$\Pr[t(i)] = \Pr[t] \times P[t(i)|t] = \frac{1}{2} \times  \frac{2(n-1)}{n(n-1)}  = \frac{1}{n}.$$

Bayes' Theorem
Now that we have come this far, Bayes' Theorem--a mathematical tautology beyond dispute--finishes the work.  Any clone's chance of heads is therefore $$\Pr[h | t(i) \cup h(i)] = \frac{\Pr[h]\Pr[h(i)|h]}{\Pr[h]\Pr[h(i)|h] + \Pr[t]\Pr[t(i)|t]} = \frac{1/(2n)}{1/n + 1/(2n)} = \frac{1}{3}.$$
Because SB is indistinguishable from her clones--even to herself!--this is the answer she should give when asked for her degree of belief in heads.
Interpretations
The question "what is the probability of heads" has two reasonable interpretations for this experiment: it can ask for the chance a fair coin lands heads, which is $\Pr[h] = 1/2$ (the Halfer answer), or it can ask for the chance the coin lands heads, conditioned on the fact that you were the clone awakened.  This is $\Pr[h|t(i) \cup h(i)] = 1/3$ (the Thirder answer).
In the situation in which SB (or rather any one of a set of identically prepared Jaynes thinking machines) finds herself, this analysis--which many others have performed (but I think less convincingly, because they did not so clearly remove the philosophical distractions in the experimental descriptions)--supports the Thirder answer.
The Halfer answer is correct, but uninteresting, because it is not relevant to the situation in which SB finds herself.  This resolves the paradox.
This solution is developed within the context of a single well-defined experimental setup.  Clarifying the experiment clarifies the question.  A clear question leads to a clear answer.
Comments
I guess that, following Elga (2000), you could legitimately characterize our conditional answer as "count[ing] your own temporal location as relevant to the truth of h," but that characterization adds no insight to the problem: it only detracts from the mathematical facts in evidence.  To me it appears to be just an obscure way of asserting that the "clones" interpretation of the probability question is the correct one.
This analysis suggests that the underlying philosophical issue is one of identity: What happens to the clones who are not awakened?  What cognitive and noetic relationships hold among the clones?--but that discussion is not a matter of statistical analysis; it belongs on a different forum.
A: The question is ambiguous and so there only appears to be a paradox.  The question is posed this way:

When you are awakened, to what degree should you believe that the outcome of the coin toss was Heads?

Which is confused with this question:

When you are awakened, to what degree should you believe Heads was the reason you were awakened?

In the first question the probability is 1/2.   In the second question, 1/3.
The problem is that the first question is stated, but second question is implied in the context of the experiment.  Those who subconsciously accept the implication say it's 1/3. Those who read the question literally say it's 1/2.
Those who are confused are not sure which question they're asking!
A: "Whenever SB awakens, she has learned absolutely nothing she did not know Sunday night."
This isn't correct, which is the error in the halfer argument. One thing that makes it hard to argue with,tho, is that the halfer argument which is based on this statement is seldom expressed with any more rigor than what I quoted.
There are three problems. First, the argument does not define what "new information" means. It seems to mean "An event that originally had a non-zero probability cannot have occurred based on the evidence." Second, it never enumerates what is known on Sunday to see if it fits this definition; and it can, if you look at it properly. Finally, there is no theorem that says "if you have no new information of this kind, you can't update." If you do have it, Bayes Theorem will produce an update. But it is a fallacy to conclude, if you don't have this new information, that you can't update. Being a fallacy doesn't mean it isn't true, it means you can't make this conclusion based on this evidence alone.
On Sunday Night, say SB rolls an imaginary six-sided die of her own. Since it is imaginary, she can't look at the result. But the purpose is to see if it matches the day she is awake: an even number means it matches Monday, and an odd number means Tuesday. But it can't match both, which effectively distinguishes the two days.
SB can now (that is, on Sunday) calculate the probability for the eight possible combinations of {Heads/Tails, Monday/Tuesday, Match/No Match}. Each will be 1/8. But when she is awake, she knows that {Heads, Tuesday, Match} and {Heads, Tuesday, No Match} did not happen. This constitutes "new information" of the form the halfers argument says doesn’t exist, and it allows SB to update the probability that the researcher's coin landed on heads. It is 1/3 whether or not her imaginary coin matches the actual day. Since it is the same either way, it is 1/3 whether or not she knows if there is a match; and in fact, whether or not she rolls, or imagines rolling, the die.
This extra die seems like a lot to go through to get a result. In fact, it isn’t necessary, but you need a different definition of "new information" to see why. Updating can occur anytime the significant (i.e., independent and not zero-probability) events in the prior sample space differ from the significant events in the posterior sample space. That way, the denominator of the ratio in Bayes Theorem is not 1. While this usually occurs when the evidence makes some of the events have zero probability, it can also occur when the evidence changes whether events are independent. This is a very unorthodox interpretation, but it works because Beauty is given more than one opportunity observe an outcome. And the point of my imaginary die, which distinguished the days, was to render the system into one where the total probability was 1.
On Sunday, SB knows P(Awake,Monday,Heads) = P(Awake,Monday,Tails) = P(Awake,Tuesday,Tails)=1/2. These add up to more than 1/2 because the events are not independent based on the information SB has on Sunday. But they are independent when she is awake. The answer, according to Bayes Theorem, is (1/2)/(1/2+1/2+1/2)=1/3. There is nothing wrong with a denominator that is greater that 1; but the imaginary coin argument was designed to accomplish the same things without such a denominator.
A: I just re-tripped across this. I've refined some of my thoughts since that last post, and thought I might find a receptive audience for them here.
First off, on the philosophy of how to address such a controversy: Say arguments A and B exist. Each has a premise, a sequence of deductions, and a result; and the results differ.
The best way way to prove one argument is incorrect is to invalidate one of its deductions. If that were possible here, there wouldn't be a controversy. Another is to disprove the premise, but you can't do that directly. You can argue for why you don’t believe one, but that won't resolve anything unless you can convince others to stop believing it.
To prove a premise wrong indirectly, you have to form an alternate sequence of deductions from it that leads to an absurdity or to a contradiction of the premise. The fallacious way is to argue that the opposing result violates your premise. That means that one is wrong, but it doesn't indicate which.
+++++
The halfer's premise is "no new information." Their sequence of deductions is empty - none are needed. Pr(Heads|Awake) = Pr(Heads)=1/2.
The thirders (specifically, Elga) have two premises - that Pr(H1|Awake and Monday) = Pr(T1|Awake and Monday), and Pr(T1|Awake and Tails) = Pr(T2|Awake and Tails). An incontrovertible sequence of deductions then leads to Pr(Heads|Awake) = 1/3.
Note that the thirders don't ever assume there is new information - their premises are based on whatever information exists - "new" or not - when SB is awake. And I've never seen anyone argue for why a thirder premise is wrong, except that it violates the halfer result. So the halfers have provided none of the valid arguments I've listed. Just the fallacious one.
But there are other deductions possible from "no new information," with a sequence of deductions that start with Pr(Heads|Awake) = 1/2. One is that Pr(Heads|Awake and Monday) = 2/3 and Pr(Tails|Awake and Monday) = 1/3. This does contradict the thirder premise, but like I said, that doesn’t help the halfer cause since it still could be their premise that is wrong. Ironically, this result does prove something - that the halfer premise contradicts itself. On Sunday, SB says Pr(Heads|Monday) = Pr(Tails|Monday), so adding the information "Awake" has allowed her to update these probabilities. It is new information.
So I have proven the halfer premise can't be right. That doesn't mean the thirders are right, but it does mean that halfers have not provided any contrary evidence.
+++++
There is another argument I find more convincing. It isn't completely original, but I'm not sure if the proper viewpoint has been emphasized enough. Consider a variation of the experiment: SB is always wakened on both days; usually it is in a room that is painted blue, but on Tuesday after Heads it is in a room that is painted red. What should she say the probability of Heads is, if she finds herself awake in a blue room?
I don’t think anybody would seriously argue that it is anything but 1/3. There are three situations that could correspond to her current one, all are equally likely, and only one includes Heads.
The salient point is that there is no difference between this version, and the original. What she "knows" - her "new information" - is that it is not H2. It does not matter how, or IF, she would know it could be H2 if it could. Her capability to observe situations that she knows do not apply is irrelevant if she knows they do not apply.
I can not believe the halfer premise. It is based on a fact - that she can't observe H2 - that cannot matter since she can, and does, observe that it isn't H2.
So I hope that I have provided a convincing argument for why the halfer premise is invalid. Along the way, I know I have demonstrated that the thirder result must be correct.
A: Since sleeping beauty can't remember how many times she has woken up before, we are not looking at the probability of Heads given that she has woken up just this once, but the probability of Heads given that she has woken up at least once:
So we have: $P(Heads\mid x\geq1) = 1/2$ and not $P(Heads\mid x=1) = 1/3$
Thus the answer is 50% (the halfers are right), and there is no paradox.
People seem to be making this far, far more complex than it really is!
A: A simple explanation for this would be that there are 3 ways in which sleeping beauty can wake up two of which are from a Tails toss. So the probability has to be 1/3 for a heads every time she wakes up. I've outlined it in a blog post
The main argument against the "halfer" point of view is the following: In a bayesian sense, SB is always looking to see what new information she has. In reality, the moment she has decided to take part in the experiment, she has additional information that when she wakes up it could be in of the days. Or put in other words the lack of information (wiping out the memory) is what is providing the evidence here, subtly though. 
A: One third of possible wakings are Heads wakings, and two thirds of possible wakings are Tails wakings.  However, one half of princesses (or whatever) are Heads princesses, and one half are  Tails princesses.  The Tails princesses, individually and in aggregate, experience twice as many wakings as the Heads princesses.    
From the perspective of the princess, on waking up, there are three possibilities.  She is either a Heads princess awaking for the first (and only) time ($H1$), a Tails princess awaking for the first time ($T1$), or a tails princess awaking for a second time ($T2$).  There seems no reason to assume that these three outcomes are equally likely.  Rather $P[H1]=0.5$, $P[T1]=0.25$, and $P[T2]=0.25$. 
I haven't read Vineberg's reasoning, but I think I can see how she arrives at a fair bet of $\$1/3$.  Suppose that every time a princess awakens, she makes a bet of $\$x$ that she is a Heads princess, receiving \$1 if she is indeed a Heads princess, and \$0 otherwise.  Then a Heads princess will receive $\$(1-x)$, and a Tails princess will receive $\$(-x)$ each time she plays.  Since the Tails princesses must play twice, and since half of princesses are Heads princesses, the expected return is $\$(1-3x)/2$, and the fair price is $\$1/3$.
Normally this would be conclusive evidence that the probability is $1/3$, but the usual reasoning does not hold in this case: the princesses who are destined to lose the bet are obliged to play the game twice, whereas those who are destined to win will play only once!  This imbalance uncouples the usual relationship between probabilities and fair bets.
(On the other hand, a technician who was assigned to help with the waking process really would have only a one third chance of being assigned to a Heads princess.)
A: Non-statistially
In all her congenial geniousness, Sleeping Beauty can perform the hypothetical experiment in her sleep, which will shape her believes:
import numpy as np
    
# Take clones of our Sleeping Beauties.
# One type of clones is persistently heads guessing,
# the other persistently guesses tails.

# Keeping score for heads guessing Sleeping Beauty ...
guessed_heads_right = 0
    
# ... and also for the tails guessing Sleeping Beauty
guessed_tails_right = 0
    
# Coding the toss outcomes
HEADS = 0
TAILS = 1
    
# Function to wake up heads guessing Sleeping Beauty
def heads_guesser_guesses_right(toss):
    return toss == HEADS
    
    
# Function to wake up tails guessing Sleeping Beauty
def tails_guesser_guesses_right(toss):
    return toss == TAILS
    
    
# Repeating the tossing and awakenings many times
for i in range(1000):
    
    # Toss fair coin, result is either HEADS or TAILS
    toss = np.random.randint(0, 2)
    
    # Waking SBs up first time and count successful guesses
    if heads_guesser_guesses_right(toss):
        guessed_heads_right += 1
    if tails_guesser_guesses_right(toss):
        guessed_tails_right += 1

    # If toss was TAILS, wake SBs up second time ...
    if toss == TAILS:

        # ... and counts successful guesses
        if heads_guesser_guesses_right(toss):
            guessed_heads_right += 1
        if tails_guesser_guesses_right(toss):
            guessed_tails_right += 1

# Print the raw statistics
print('Guessed HEADS right: {}'.format(guessed_heads_right))
print('Guessed TAILS right: {}'.format(guessed_tails_right))

Output:
Guessed HEADS right: 498
Guessed TAILS right: 1004

So our Sleeping Beauty will believe to better be guessing tails.
And statistically?
The above algorithm is not a statistically rigorous way to determine what to guess. However, it does make it ominously clear that in case of tails, she gets to guess twice, thus guessing tails is twice as likely to be the right guess. This follows from the operational procedure of the experiment.
Frequentist Probability
Frequentist Probability is a concept of statistics based on the theories of Fisher, Neyman and (Egon) Pearson.
A basic notion in Frequentist Probability is that the operations in experiments can be repeated, at least hypothetically, an infinite number of times. Each such operation $n$ leads to an outcome $E_{n}$.
Crucially, an "Experiment" here is the act of waking her up and not the act of throwing the coin.
The Frequentist Probability of an outcome $E$ is defined as: $Pr(E)\equiv\texttt{lim}_{n\rightarrow\infty}\left(\frac{E_{n}}{N}\right)$
This is exactly what Sleeping Beauty did in her head above: if $E$ is the event of being right while guessing HEADS, then $Pr(E)$ converges to $\frac{1}{3}$.
And her believes?
So when she finally arrives here in her reasoning she has statistically rigorous grounds to base her believes on. But how she will ultimately shape them, really depends on her psyche.
A: I really like this example but I would argue that there is one point to make confounded with a couple of nuisance distractions. 
To avoid nuisance distractions, one arguable should try to discern an abstract diagrammatic representation of the problem that is clearly beyond reasonable doubt (as an adequate representation) and can be verifiably manipulated (re-manipulated by qualified others) to demonstrate the claims.  As a simple example think of an (abstract mathematical) rectangle and the claim that it can be made into two triangles. 
Draw a free hand rectangle as a representation of a mathematical rectangle (in your drawing the four angles will not add exactly to 180 degrees and the adjacent lines will not be exactly equal or straight but there will be no real doubt that it represents a true rectangle). Now manipulate it by drawing a line from one opposite corner to another, which anyone else could do and you get a representation of two triangles that no one would reasonably doubt. Any questioning of can this be so seems nonsense, it just is.
The point  I am try to make here is that if you get a beyond a reasonable doubt representation of the SB problem as a joint probability distribution and can condition on an event that happens in the experiment in this representation - then claims of whether anything is learned by that event can be demonstrated by verifiable manipulation and require no (philosophical) discussion or questioning. 
Now I better present my attempt and readers will need to discern if I have succeeded. 
I will use a probability tree to represent joint probabilities for day sleeping in the experiments (DSIE), coin flip outcome on Monday (CFOM) and woken given one was sleeping in the experiment (WGSIE).  I will draw it out (actually just write it out here) in terms of p(DSIE)*p(CFOM|DSIE)*p(WGSIE|DSIE,CFOM). 
I would like to call DSIE and CFOM possible unknowns and WGSIE the possible known, then p(DSIE,CFOM) is a prior and p(WGSIE| DSIE,CFOM) is a data model or likelihood and Bayes theorem applies, without this labelling it’s just conditional probability which is logically the same thing. 
Now we know p(DSIE=Mon) + p(DSIE=Tues) = 1 and p(DSIE=Tues) = ½ p(DSIE=Mon) 
so p(DSIE=Mon)=2/3 and p(DSIE=Tues)=1/3. 
Now P(CFOM=H|DSIE=Mon) = 1/2 , P(CFOM=T|DSIE=Mon) = 1/2 , P(CFOM=T|DSIE=Tues)=1.
P(WGSIE| DSIE=.,CFOM=.) is always equals to one. 
Prior equals 
P(DSIE=Mon ,CFOM=H) = 2/3 * ½ = 1/3
P(DSIE=Mon ,CFOM=T) = 2/3 * ½ = 1/3
P(DSIE=Tues ,CFOM=T) =  1/3 *1  = 1/3
So marginal prior for CFOM = 1/3 H and 2/3 T, and the posterior given you were woken while sleeping in the experiment – will be the same (as no learning occurs) – so you prior is 2/3 T. 
OK – where did I go wrong? 
Do I need to review my probability theory?
A: I'm going to solve this problem for the generic case where SB is waken '$m$' times after 'Heads' and '$n$' times after 'Tails' with $m≤n$.
Specifically, if coin is 'Heads', she will be awakened on...
day 1
day 2
$\cdots$
$\cdots$
day $m$
...and if coin is 'Tails', she will be awakened on...
day 1
day 2
$\cdots$
$\cdots$
day $n$
$m≤n$
Then for this specific question, will be $m=1$ and $n=2$. I'm not going to make assumptions, will use only the given info that the coin is fair, thus before awakening it is
$$P(Heads)=P(Tails)=1/2.$$
Upon SB is waken she doesn't know what day it is or whether she was waken before. She only knows a fair coin was tossed with possible results 'Heads' and 'Tails'. She also knows the awakening is happening on 'day 1' or 'day 2' or $\ldots$ , or 'day $n$'. For the possible result 'Heads', there are '$m$' possible results which I'll name $D_1$, $D_2$,$\ldots$, $D_m$.
$D_1$: This awakening is happening on 'day 1'
$D_2$: This awakening is happening on 'day 2'
$D_3$: This awakening is happening on 'day 3'
$\cdots$
$\cdots$
$D_m$: This awakening is happening on 'day $m$'
For the possible result 'Tails', there are '$n$' possible results including the '$m$' possible results stated above.
$D_1$: This awakening is happening on 'day 1'
$D_2$: This awakening is happening on 'day 2'
$D_3$: This awakening is happening on 'day 3'
$\cdots$
$\cdots$
$D_n$: This awakening is happening on 'day $n$'
So there are $m+n$ possible results. Now given the coin has landed 'Heads', the events $D_1$, $D_2$,$\ldots$, $D_m$ are equally likely. Therefore...
$$P(D_1|H)=P(D_2|H)=\ldots=P(D_m|H) = \frac{1}{m}$$
Also, given the coin has landed 'Tails', the events $D_1$, $D_2$,$\ldots$, $D_n$ are equally likely. Therefore...
$$P(D_1|T)=P(D_2|T)=\ldots=P(D_n|T) = \frac{1}{n}$$
Now, for any possible event $D_i$ where $i$ is integer and $1≤i≤m$
$$P(D_i\cap H)=P(H)\times P(D_i|H)=\frac{1}{2}\times \frac{1}{m} = \frac {1}{2m}$$
$$P(D_i∩T)=P(T)\times P(D_i|T)=\frac{1}{2}\times \frac{1}{n} = \frac {1}{2n}$$
for $m<i≤n$, it is obviously...
$$P(D_i∩H)=P(H)\times P(D_i|H)=\frac{1}{2}\times0=0$$
$$P(D_i∩T)=P(T)\times P(D_i|T)=\frac{1}{2}\times \frac{1}{n} = \frac {1}{2n}$$
Now let's calculate the probabilities of possible events $D_1$, $D_2$,$\ldots$, $D_n$
for $1≤i≤m$
$$P(D_i)=P(D_i∩H)+P(D_i∩T) = \frac {1}{2m}+\frac {1}{2n}$$
for $m<i≤n$
$$P(D_i)=P(D_i∩H)+P(D_i∩T)=0+\frac {1}{2n} = \frac {1}{2n}$$
Now we can calculate the probability of 'Heads' given SB is awake. As said above, the possible events upon awakening are $D_1$, $D_2$,$\ldots$, $D_n$. Therefore the probability is...
\begin{align}P(H|awake)&=P(H|(D_1∪D_2∪...∪D_n))\\
&\\
&=\frac {P(H∩(D_1∪D_2∪\ldots∪D_n))}{P(D_1∪D_2∪\ldots∪D_n)}\\
&\\
&=\frac {P((H∩D_1)∪(H∩D_2)∪\ldots∪(H∩D_n))}{P(D_1∪D_2∪\ldots∪D_n)}\\
&\\
&=\frac{P(H∩D_1)+P(H∩D_2)+\ldots+P(H∩D_n)}{P(D_1)+P(D_2)+\ldots+P(D_n)}\\
&\\
&=\frac{P(H∩D_1)+P(H∩D_2)+\ldots+P(H∩D_m)+\ldots+P(H∩D_n)}{P(D_1)+P(D_2)+\ldots+P(D_m)+\ldots+P(D_n)}\\
&\\
&=\frac{\frac {1}{2m}\times m + 0\times(n-m)}{(\frac {1}{2m}+\frac {1}{2n})\times m + \frac {1}{2n}\times(n-m)}\\
&\\
&=\frac{\frac {1}{2}+0}{\frac {1}{2}+\frac{m}{2n}+\frac {1}{2}-\frac{m}{2n}}=\frac{\frac{1}{2}}{\frac{1}{2}+\frac {1}{2}}=\frac{\frac{1}{2}}{1}=\frac{1}{2} \end{align}
We already have the answer, but let's also calculate the probability of 'Heads' or 'Tails' given the awakening is happening on a certain day
for $1≤i≤m$
$$P(H|D_i)=\frac{P(H∩D_i)}{P(D_i)}=\frac{\frac {1}{2m}}{\frac {1}{2m}+\frac {1}{2n}}=\frac{n}{m+n}$$
$$P(T|D_i)=\frac{P(T∩D_i)}{P(D_i)}=\frac{\frac {1}{2n}}{\frac {1}{2m}+\frac {1}{2n}}=\frac{m}{m+n}$$
for $m<i≤n$
$$P(H|D_i)=\frac{P(H∩D_i)}{P(D_i)}=\frac{0}{P(D_i)}=0$$
$$P(T|D_i)=\frac{P(T∩D_i)}{P(D_i)}=\frac{\frac{1}{2n}}{\frac{1}{2n}}=1$$
I'm aware this is not an answer for those who believe the "1/3" answer. This is just a simple use of conditional probabilities. Thus, I don't believe this problem is ambiguous and therefore a paradox. It is though confusing for the reader by making unclear which are the random experiments and which the possible events of those experiments.
A: Just another approach to frame this paradox with slightly different rules.

*

*Sleeping Beauty is set to sleep. The scientists and Sleeping Beauty agree that the scientists will play the lottery (with winning chance one in a Million). If they win, they will wake up Sleeping Beauty 10 Million times. If they don't win, they will wake her up just once.

Now, Sleeping Beauty has been woken up. What should she think, did the scientists really win the lottery?
Of course this is simply paraphrasing and does not resolve the paradox. In this situation, however, intuitively I would definitely believe that the scientists did not win the lottery, as the number of times that I am awakened does not affect the probability of winning the lottery.
However, if money is involved and I win/lose a Dollar each time I am awakened, I would bet that they have won the lottery, as the risk for losing a lot of money in this case is more important to cover than the small gain from guessing correctly if they did not win the lottery.
Apparently, I am a halfer. If someone would bet in this situation that the scientists actually have won the lottery, I would be very interested in your comment.
A: Thanks for this brilliant post (+1) and solution (+1). This paradox already gives me a headache.
I just thought of the following situation which does not require fairies, miracles nor magic potions. Flip a fair coin on Monday noon. Upon 'Tails' send a mail to Alice and Bob (in a way that they don't know that the other has received a mail from you, and that they cannot communicate). Upon 'Heads', send a mail to one of them at random (with probability $1/2$).
When Alice receives a mail, what is the probability that the coin landed on 'Heads'? The probability that she receives a letter is $1/2 \times 1/2 + 1/2 = 3/4$, and the probability that the coin landed on 'Heads' is $1/3$.
Here there is no paradox because Alice does not receive a letter with probability $1/4$, in which case she knows the coin landed on 'Heads'. The fact that we don't ask her opinion in that case, does make this probability equal to 0.
So, what is the difference? Why would Alice gain information by receiving a mail, and SB would learn nothing being awakened?
Moving on to a more miraculous situation, we put 2 different SB to sleep. If the coin lands on 'Tails' we wake up both, if it lands on 'Heads' we wake up one of them at random. Here again, each of the SB should say that the probability of the coin landing on 'Heads' is $1/3$ and again there is no paradox because there is a $1/4$ chance that this SB would not be awakened.
But this situation is very close to the original paradox because erasing the memory (or cloning) is equivalent to having two different SB. So, I am with @Douglas Zare here (+1). SB has learned something by being awakened. The fact that she cannot express her opinion on Tuesday when the coin is 'Heads' up because she is sleeping does not erase the information she has by being awakened.
In my opinion the paradox lies in "she has learned absolutely nothing she did not know Sunday night" which is stated without justification. We have this impression because the situations when she is awakened are identical, but this is just like Alice receiving a mail: it is the fact that she is asked her opinion that gives her information.
MAJOR EDIT: After giving it a deep thought, I change my opinion: Sleeping Beauty has learned nothing and the example I give above is not a good analogue of her situation.
But here is an equivalent problem that is not paradoxical. I could play the following game with Alice and Bob: I toss a coin secretly and independently bet them 1\$ that they cannot guess it. But if the coin landed on 'Tails', the bet of either Alice of Bob is cancelled (money does not change hand). Given that they know the rules, what should they bet?
'Heads' obviously. If the coin lands on 'Heads', they gain 1\$, otherwise, they lose 0.5\$ on average. Does it mean that they believe that the coin has a 2/3 chance of landing on 'Heads'? Sure not. Simply the protocol is such that they do not gain the same amount of money for each answer.
I believe that Sleeping Beauty is in the same situation as Alice or Bob. The events give her no information about the toss, but if she is asked to bet, her odds are not 1:1 because of asymmetries in the gain. I believe that this is what @whuber means by

The Halfer answer is correct, but uninteresting, because it is not relevant to the situation in which SB finds herself. This resolves the paradox.

A: The paradox lies in the perspective change between a single experiment and its limit point.  If # of experiments is taken into account, you can understand this even more precisely than the "either/or" of halvers and thirders: 
Single Experiment: Halvers are right
If there is a single experiment, there are three outcomes and you just have to figure the probabilities from the perspective of the awakened:


*

*Heads was tossed: 50%

*Tails was tossed and this is my first awakening: 25%

*Tails was tossed and this is my second awakening: 25%


So, in a single experiment, at any wakeup event, you should assume 50/50 that you are in a state where heads was tossed
Two experiments: 42%ers are right
Now, try two experiments:


*

*Heads was tossed twice: 25% (for both awakenings combined)

*Tails was tossed twice: 25% (for all four awakenings combined)

*Heads then Tails and this is my first awakening: 25%/3

*Heads then Tails and this is my 2nd or 3rd awakening: 25%*2/3

*Tails then Heads and this my 1st or 2nd awakening: 25%*2/3

*Tails then Heads and this is my 3rd awakening: 25%/3.


So here, {1, 3, 6} are your Heads states, with a combined probability of (25 + 25/3 + 25/3)%, 41.66%, which is less than 50%.  If two experiments are run, at any wakeup event, you should assume 41.66% chance you are in a state where Heads was thrown
Infinite experiments: Thirders are right
I'm not going to do the math here, but if you look at the two-experiments options, you can see #1 and #2 drive it toward halves, and the rest drive it toward thirds.  As the number of experiments increases, the options driving toward halves (all heads/all tails) will decrease in probability down to zero, leaving the "thirds" options to take over.  If infinite experiments are run, at any wakeup event, you should assume 1/3 chance you are in a state where heads was thrown
Preempting Retorts:
But, gambling?
Yes in the single experiment instance, you should still "gamble" by the thirds.  This is not an inconsistency; it's just because you may be placing the same bet multiple times given a certain outcome, and know this in advance.  (Or if you don't, the mafia does).
Okay, how about two single experiments?  Discrepancy much?
No, because knowledge about whether you're on the first or 2nd experiment adds to your, erm, knowledge.  Let's look at the "two experiments" options and filter them by knowledge that you're on the first experiment.


*

*Applicable for first awakening (1/2)

*Applicable for first two awakenings (2/4)

*Applicable

*Never applicable

*Applicable for first awakening (1/2)

*Not applicable


Okay, take the Heads ones (1,3,6) multiply these, odds by applicability: 25/2 + 25/3 + 0 = 125/6.
Now take the Tails ones (2,4,5) and do the same: 25*4/2 + 0 + 25*(2/3)/2 = 125/6.
Viola, they're the same.  The added information about which experiment you're in in fact adjusts the odds of what you know.
But, the clones!!
Simply put, contrary to the OP's answer's postulate, that cloning creates an equivalent experiment: cloning plus random selection does change the knowledge of the experimentee, in the same way "multiple experiments" changes the experiment.  If there are two clones, you can see the probabilities of each clone correspond to the Two Experiments probabilities.  Infinite clones converges to thirders.  But it's not the same experiment, and it's not the same knowledge, as a single experiment with a single non-random subject.
You say "random one of infinite" and I say Axiom of Choice dependency
I don't know, my set theory isn't that great.  But given for N less than infinity, you can establish some sequence that converges from half to a third, the infinite case equaling a third will either be true or undecidable at worst, no matter which axioms you invoke.
A: Let's vary the problem.
If the coin comes up Heads, then SB is never awakened.
If Tails, then SB is awakened once.
Now the camps are Halfers and Zeroers. And clearly the Zeroers are correct.
Or: Heads -> woken once; Tails -> woken a million times. Clearly, given she's awake, it's most likely tails.
(P.S. On the subject of "new information" -- information may have been DESTROYED. So, another question is: has she lost information she once had?)
A: I just thought of a new way to explain my point, and what is wrong with the 1/2 answer. Run two versions of the experiment at the same time, using the same coin flip. One version is just like the original. In the other, three (or four - it doesn’t matter) volunteers are needed; each is assigned a different combination of Heads-or-Tails and Monday-or-Tuesday (the Heads+Tuesday combination is omitted if you use only three volunteers). Label them HM, HT, TM, and TT, respectively (possibly omitting HT).
If a volunteer in the second version is woken up this way, she knows she was equally likely to have been labeled HM, TM, or TT. In other words, the probability she was labeled HM, given that she is awake, is 1/3. Since the coin flip and day correspond to this assignment, she can trivially deduce that P(Heads|Awake)=1/3.
The volunteer in the first version could be woken more than once. But since "today" is only one of those two possible days, when she is awake she has exactly the same information as the awake volunteer in the second version. She knows that her current circumstances can correspond to the label applied to one, AND ONLY ONE, of other volunteers. That is, she can say to herself "either the volunteer labeled HM, or HT, or TT is also awake. Since each is equally likely, there is a 1/3 chance it is HM and so a 1/3 chance the coin landed tails."
The reason people make a mistake is that they confuse "is awake sometime during the experiment" with "is awake now." The 1/2 answer comes from the original SB saying to herself "either HM is the only other awake volunteer NOW, or TM and TT are BOTH awake SOMETIME DURING THE EXPERIMENT. Since each situation is equally likely, there is a 1/2 chance it is HM and so a 1/2 chance the coin landed tails." It is a mistake because only one other volunteer is awake now.
A: As many questions, it depends of the exact meaning of the question:

When you are awakened, to what degree should you believe that the outcome of the coin toss was Heads?

If you are interpret it as "what are the odds that a tossed coin is Heads", obviously the answer is "half the odds".
But what you are asking is not (in my interpretation) that, but "which is the chance that the current awakening was caused by a Heads?". In that case, obviously only a third of the awakenings are caused by a Heads, so the most probable answer is "Tails".
A: This is a very interesting question. I will give my answer as if I were to be sleeping beauty. I feel a key point to understand is that we 100% trust the experimenter.
1) On Sunday night, if you ask me what the probability the coin is heads, I will tell you $\frac{1}{2}$.
2) Whenever you wake me up and ask me, I will tell you $\frac{1}{3}$.
3) When you tell me that this is the last time you are awakening me I will immediately switch to telling you the probability is $\frac{1}{2}$.
Clearly (1) follows from the fact the coin is fair. (2) follows from the fact that when you are are woken, you are in one of 3 equally likely situations from your point of view. Each of them can occur with probability $\frac{1}{2}$. 
Then (3) follows in the same manner except that as soon as you are told this is the last time you are being awakened, the number of situations you can be in collapses to 2 (as now tails and this being the first time you were awakened is impossible).
A: Rather than giving a statistically rigorous answer, I'd like to modify the question slightly in a way that might convince people whose intuition leads them to be halfers.

Some researchers want to put you to sleep. Depending on the secret toss of a fair coin, they will awaken you either once (Heads) or nine-hundred and ninety-nine times (Tails). After each awakening they will put you back to sleep with a drug that makes you forget that awakening.
When you are awakened, what degree of belief should you have that the outcome of the coin toss was Heads?

Following the same logic as before, there could be two camps -


*

*Halfers - the coin toss was fair, and SB knows this, so she should believe there is a one-half chance of heads.

*Thousanders - if the experiment was repeated many times, the coin toss would be heads only one in a thousand times, so she should believe that the chance of heads is one in a thousand.


I believe that some of the confusion from the question as originally worded arises simply because there isn't much difference between a half and a third. People naturally think of probabilities as somewhat fuzzy concepts (particularly when the probability is a degree-of-belief rather than a frequency) and it's difficult to intuit the difference between degrees of belief of a half and a third.
However, the difference between a half and one in a thousand is much more visceral. I claim that it will be intuitively obvious to more people that the answer to this problem is one in a thousand, rather than a half. I would be interested to see a "halfer" defend their argument using this version of the problem instead.
A: I think the error is from the "thirders" and my reason for this is that the "awakenings" are not equally likely - if you are woken up then it is more likely to be "the first time" you were woken up - a 75% chance in fact.
This means you cannot count the "3 outcomes" (heads1, tails1, tails2) equally.
I think this also appears to be a case of $AA=A$ where $A$ is the proposition that SB is woken up. Saying something is true twice is the same thing as saying it once. SB has not been provided with new data, because the prediction from the prior was $Pr(A|I)=1$. Other ways of putting it are $I\implies A$ and $IA=I$. This means $p(H|AI)=p(H|I)=0.5$
The maths are clearly shown in the answer given by @pit847, so I won't repeat it in mine.
but, in terms of betting $1$ dollar to guess the outcome at each awakening and you are given $g$ dollars if you are correct. In this case, you should always guess tails because this outcome is "weighted". If the coin was tails, then you will bet twice. so your expected profit (call this $U$) if you guess heads is
$$E(U|h)=0.5\times (g-1) + 0.5\times (-2) = \frac{g - 3}{2}$$
and similarly for guessing tails
$$E(U|t)=0.5\times (-1) + 0.5 \times (2g-2)=\frac{2g - 3}{2}$$
so you gain an extra $\frac{g}{2}$ on average from guessing tails. the "fair bet" amount is $g=\frac{3}{2}=1.5$
Now if we repeat the above but use a third instead of a half, we get $E(U|h)=\frac{g-5}{3}$ and $E(U|t)=\frac{4g-5}{3}$. so we still have that guessing tails is a better strategy. Also, the "fair bet" amount is $g=\frac{5}{4}=1.25$
Now we can say that "thirders" should take a bet where $g=1.4$. But the "halfers" would not take this bet. @Ytsen de Boer has a simulation we can test. We have $498$ heads and $502$ tails, so betting tails would give you $1004 \times 1.4 = 1405.6$ in won bets. But... you had to play $1502$ times to get this - which is a net loss of $97.6$ - so the "thirders" lose! also note this is actually a slightly favourable outcome for betting tails.
A: The perception that there is a paradox here stems from the conflation of two different questions:

*

*What is the probability of heads? (1/2)

*What is the probability of observing a heads upon waking from the sleeper's perspective? (1/3)

However, these are both valid and different questions and so there is no paradox to resolve.
A: Beauty learns no new information, yet her credence for heads is 1/3.
The 1/3 answer comes from two applications of the law of total probability (show below), and the fact that B's credence for her belief in the current day being Monday, given she's told the coin landed tails, is 1/2. The decision quadruple defined below, can then be modified to show, depending on the experiment setup, that her credence for heads changes. But from the perspective of the awakening B, all these experiments look identical - going to sleep and waking up - thus showing that B learns no new information during the course of the experiment which would allow her to update her belief for heads.
Contrast this with the Monty Hall problem, where the host opens a particular, and not merely a door, allowing the contestant to update her belief using Bayes's Theorem.
Let $H$ be the event the coin landed heads, and $M$ the current day being monday.
Then by the law of total probability:

*

*$P(H) = P(H|M)P(M)+P(H|\sim M)P(\sim M)= P(H|M)P(M)+P(H|\sim M)(1-P(M))$

*$P(M) = P(M|H)P(H)+P(M|\sim H)P(\sim H) = P(M|H)P(H)+P(M|\sim H)(1-P(H))  $
forming a linear equation system in $P(H)$ and $P(M)$.
Define the decision quadruple $d:=(P(H|M),P(M|H),P(H|\sim M),P(M|\sim H))$ - giving Beauty's credence for different decisions related to certain events.
This problem has $d=(1/2, 1, 0, 1/2)$, solving (1) and (2) with 1/3 and 2/3.
If $d=(2/3, 1, 0, 1/2)$, corresponding to flipping a second coin on tails to determine which day Beauty should be awoken, but not both, gives a solution of 1/2 and 3/4.
A: Ignore all the complex theory and just calculate the odds.
There are 3 possible events: awake-from-heads, awake-from-tails, awake-from-tails. Heads has one event, while tails has two events. The odds are 1:2 against heads. Since flipping heads and tails are equally likely, we can just count the events from heads divided by the total possible events to get the probability. The probability of heads is 1/3.
If you really want 1/2 to be the correct answer, you'll need to find a coin that flips heads 2/3 of the time.
A: If sleeping beauty had to say either heads or tails - she would minimise her expected 0-1 loss function (evaluated each day) by picking tails. If, however, the 0-1 loss function was only evaluated each trial then either heads or tails would be equally good. 
A: The thirders win
Instead of a coin, lets a assume a fair dice:
on friday, the sleeping beauty will sleep:
if the dice == 1 , they will awake her on saturday;
if the dice == 2 , they will awake her on saturday and sunday;
if the dice == 3 , they will awake her on saturday, sunday and monday;
if the dice == 4 , they will awake her on saturday, sunday, monday and tuesday;
if the dice == 5 , they will awake her on saturday, sunday, monday, tuesday and wednesday;
if the dice == 6 , they will awake her on saturday, sunday, monday, tuesday, wednesday and thursday;

Every time they ask her ' to what degree should you believe that the outcome of the dice was 1?'
The halfers will say the probability of dice = 1 is 1/6
The thirders will say the probability of dice = 1 is 1/21
But simulation clearly solves the problem :
days <- c("saturday", "sunday", "monday", "tuesday", "wednesday", "thursday")

#she will answer the dice was 1 every time 
#the trick here is that this is not absolutely random because every day implies the days before it. 


number_of_correct_answer <- 0
number_of_days <- 0
for (i in 1:1000){
dice <- sample(1:6,1)
for (item in days[1:dice]){
        number_of_correct_answer <- number_of_correct_answer + (dice == 1)
        number_of_days <- number_of_days + 1
}
}
number_of_correct_answer/number_of_days
#equals 1/21
#but if we divided by 1000 , which is incorrect because every experiment has more than one day we will get 1/6
number_of_correct_answer/1000
#equals 1/6

Also we can simulate the toss problem
days <- c("monday", "tuesday")
number_of_correct_answer <- 0
number_of_tosses <- 0
for (i in 1:1000){
        toss <- sample(1:2,1)
        for (item in days[1:toss]){
                number_of_correct_answer <- number_of_correct_answer + (toss == 1)
                number_of_tosses <- number_of_tosses + 1
        }
}
number_of_correct_answer/number_of_tosses
#equals 1/3
#but if we divided by 1000 , which is incorrect because every experiment can has more than one toss we will get 1/2
number_of_correct_answer/1000
#equals 1/2

A: The apparent paradox derives from the false premise that probabilities are absolute. In fact, probabilities are relative to the definition of the events being counted.
This is an important point to understand for machine learning. We may wish to calculate the probability of something (eg, a transcription being correct given a piece of audio) through its decomposition into factors (the probabilities of letters at various times, $P(Letter,Time|Audio)$) modeled by a model that looks not at the whole audio but at an instant of it (it calculates $P(Letter|Time,Audio)$). $P(Letter,Time)$ can be equal to $P(Letter|Time)$ because the P's are defined differently. Different P's cannot be put into the same equation, but careful analysis can allow us to convert between the two domains.
Both P(Heads)=1/2 w.r.t. worlds (or births), and P(Heads)=1/3 w.r.t. instants (or awakenings) are true, but after being put to sleep Sleeping Beauty can only calculate probabilities with regard to instants because she knows her memory gets erased. (Before sleeping, she would calculate it with regard to worlds.)
A: When Sleeping Beauty is awoken, she knows:

A fair coin was tossed to give result $r$; if $r = \mathrm{H}$ then this is the sole subsequent awakening; and if $r = \mathrm{T}$ then this is one of two subsequent awakenings.

Call this information $\mathcal{I}$. Nothing else is relevant to her question, which is:

What is $\mathrm{prob}(r = \mathrm{H} | \mathcal{I})?$

This is a question of assigning probabilities, as opposed to inferring them. If $w$ is the number of the awakening, then $\mathcal{I}$ is equivalent to
$$
(r = \mathrm{H} \vee r = \mathrm{T}) \wedge (r = \mathrm{H} \implies w = 1) \wedge (r = \mathrm{T} \implies (w = 1 \vee w = 2))
$$
which is logically equivalent to
$$
(r = \mathrm{H} \wedge w = 1) \vee (r = \mathrm{T} \wedge w = 1) \vee
(r = \mathrm{T} \wedge w = 2)
$$
Sleeping Beauty has no further information. By the principle of insufficient reason, she is obliged to assign a probability of $\frac{1}{3}$ to each disjunct. Therefore, $\mathrm{prob}(r = \mathrm{H} | \mathcal{I}) = \frac{1}{3}$.

PS
On second thoughts, the preceding answer applies when "fair coin" is interpreted to mean merely that there are two possibilities for the coin flip result, $\mathrm{H}$ or $\mathrm{T}$. But probably a more faithful interpretation of the phrase "fair coin" is that it specifies directly that $\mathrm{prob}(r = \mathrm{H} | \mathcal{I}) = \frac{1}{2}$, whereupon the answer is given in the problem statement.
In my view, however, statements of this sort are technically inadmissible, because a probability is something which must be worked out from the antecedent and consequent propositions. The phrase "the secret toss of a fair coin" raises the question: how does Sleeping Beauty know it's fair? What information does she have which establishes that? Normally the fairness of an ideal coin is worked out from the fact that there are two possibilities which are informationally equivalent. When the coin flip is mixed up with the wakening factor, we get three possibilities which are informationally equivalent. It's essentially a three-sided ideal coin, so we arrive at the solution above.
A: Late to the party, I know.
This question is very similar to the Monty Hall problem, where you are asked to guess behind which of 3 doors the prize is. Say you choose Door No.1. Then the presenter (who knows where the prize is) removes Door No.3 from the game, and asks if you'd like to switch your guess from Door No1 to Door No2, or stick with your initial guess. The story goes, you should always switch, because there's a higher probability for the prize to be in Door No2. People usually get confused at this point and point out that the probability of the prize being in either door is still 1/3. But that's not the point. The question isn't what the initial probability was, the real question is what are the chances your first guess was correct, vs what are the chances you got it wrong. In which case, you should switch, because the chances you got it wrong are 2/3.
As with the Monty Hall problem, things become incredibly clearer if we make 3 doors into a million doors. If there's a million doors, and you choose Door No1, and the presenter closes doors from 3 to one million, leaving only Doors No1 and Doors No2 in play, would you switch? Of course you would! The chances of you having picked Door No1 correctly in the first place was 1 in a million. Chances are you didn't.
In other words, the error in reasoning comes from believing that the probability of performing an action is equal to the probability of an action having been performed, when the context between the two does not make them equivalent statements. Phrased differently, depending on the context and circumstances of the problem, the probability of 'choosing correctly' may not be the same as the probability of 'having chosen correctly'.
Similarly with the sleeping beauty problem. If you were not awaken 2 times in the case of tails, but 1 million times, it makes more sense for you to say "this current awakening I'm experiencing right now is far more likely to be one of those in the middle of a streak of million awakenings from a Tails throw, than me having just happened to bump onto that single awakening that has resulted from Heads". The argument that it's a fair coin has nothing to do with anything here. The fair coin only tells you what are the chances of 'throwing' Heads, i.e. the probability of having to wake once versus a million times, when you first throw that coin. So if you ask SB before the experiment to choose whether she'll sleep once or a million times before each throw, her probability of 'choosing correctly' is indeed 50%.
But from that point on, assuming consecutive experiments, and the fact that SB is not told which experiment she's currently in, at any point that she's woken up, the probability of having 'thrown' Heads is far less, since she's more likely to be woken up from one of the million awakenings than from a single one.
Note that this implies consecutive experiments, as per the phrasing of the problem. If SB is reassured from the beginning of the experiment that there will only be a single experiment (i.e. only one toin coss), then her belief goes back to 50%, since at any point in time, the fact that she may have woken up many times before now becomes irrelevant. In other words, in this context, the probability of 'choosing correctly' and 'having chosen correctly' again become equivalent.
Note also, that any rephrasings using 'betting', are also different questions changing the context entirely. E.g. even in a single experiment, if you were to gain money each time you guessed correctly, you'd obviously go for tails; but this is because the expected reward is higher, not because the probability of tails is any different from heads. Therefore any 'solutions' that introduce betting are only valid to the extent that they collapse the problem to a very particular interpretation.
A: Here's an argument that being a halfer can lead Sleeping Beauty astray.
When halfer Sleeping Beauty wakes up she believes $\mathbb{P}(heads) = \frac12$. Suppose she suddenly decides she can't take the uncertainty, overpowers the experimenter, and forces him to tell her whether this is the first or second time she has been woken.
Case A: the experimenter tells her this is the second time she has woken. SB must now believe $\mathbb{P}(heads) = 0$. Her subjective $\mathbb{P}(heads)$ has decreased.
Case B: the experimenter tells her this is the first time she has woken. Now her subjective $\mathbb{P}(heads)$ must increase (by the law of total probability). So she must now believe $\mathbb{P}(heads) > \frac12$! I don't see how this can be a sensible conclusion.

Another argument which I haven't seen before: imagine that if tails is flipped then SB is woken up by a bell once and by a drum once, and that if heads is flipped then SB is woken up once by either a bell or a drum with equal probability. If she finds herself woken by a bell, I think it's uncontroversial that Bayes' Theorem tells her that the probability that the coin was heads is 1/3. Likewise if she is woken by a drum. So she's a thirder regardless of which instrument wakes her, which means she should be a thirder even if she ignores the instruments completely. But ignoring the instruments makes this problem identical to the original problem, implying that she should be a thirder in the original problem.
A: Conclusion: If asked for the limiting proportion of heads, the correct answer is $1/2$ regardless of paradigm.  If asked for the frequentist predictive p-value testing the hypothesis that the coin landed heads, the answer is $1/3$.  If asked for the updated Bayesian belief of the subject whether the coin landed heads, the answer is $1/3$.
Solution: To resolve the paradox it is unavoidable that we must first define and interpret what probability means.  The frequentist interpretation is that probability measures the emergent pattern of many samples; the Bayesian interpretation is that probability measures the subjective belief of the experimenter or in this case the subject.
Let $X$ be the random variable governing the fair coin toss, where $X=1$ (heads) with a long-run limiting proportion $\theta=1/2$.   If we adopt a frequentist interpretation, then the long-run limiting proportion of heads for the fair coin under investigation, $\theta=1/2$, is the probability of heads regardless of who is perceiving the flip and when.  If we adopt a Bayesian interpretation then "probability of heads" initially references the prior predictive distribution for the coin landing heads, $P(X=1)=\int P(X=1|\theta=c)\cdot dP(\theta\le c)$, based on perfect knowledge that the limiting proportion of heads is $\theta=1/2$ with belief probability $P(\theta=1/2)=1$.  To the Bayesian the limiting proportion of heads, $\theta$, is not a probability.  The experimenter's belief, $P(X=1)$, is the probability, which can later change.  If the experimenter had imperfect knowledge of $\theta$ then $P(\theta)$ would not be a degenerate distribution and $P(X=1)$ would represent the experimenter's belief in $X=1$ with imperfect knowledge of $\theta$.
Using Bayes' theorem, Sleeping Beauty's prior predictive distribution for heads is updated based on the information available to her about the number of possible awakenings (1 or 2), forming a posterior predictive distribution.  This results in a predictive belief probability of $1/3$ that the coin landed heads, $P(X=1|\text{awakening}=1 \cup \text{awakening}=2)=$
$\frac{P(\text{awakening}=1\cap X=1)}{P(\text{awakening}=1\cup \text{awakening}=2)}$$ $$=\frac{1/3}{1}=1/3$
Analogous to Bayesian predictive probabilities, Sleeping Beauty could calculate frequentist predictive p-values and prediction confidence levels which describe the long-run performance of the prediction based on observed data without conditioning on parameter values.  The predictive p-value is the probability of the discrepancy between the estimated future result and the hypothesized future result or something more extreme.  In this setting Sleeping Beauty's knowledge of the coin being fair is equivalent to having already flipped the coin a near infinite number of times.  Therefore, the predictive p-value testing the hypothesis that the coin landed heads is equivalent to the limiting proportion of heads over repeated experiments where Sleeping Beauty is woken twice on tails and once on heads, $P(X=1|\text{awakening}=1 \cup \text{awakening}=2)=1/3$.  We are considering each prediction opportunity as an experiment and an opportunity to make a type I error, not every coin flip.  Upon every awakening Sleeping Beauty will predict the coin landed tails, incorrectly rejecting the null hypothesis 33% of the time in repeated testing. Every time she is woken and tests the hypothesis that the coin landed heads she is 67% confident in the alternative, which is tails.
If asked for the limiting proportion of heads, the correct answer is $1/2$ regardless of paradigm.  If asked for the frequentist predictive p-value testing the hypothesis that the coin landed heads, the answer is $1/3$.  If asked for the updated Bayesian belief of the subject whether the coin landed heads, the answer is $1/3$.
A: Before SB goes to sleep she believes that the chance of the next coin flip being heads is 1/2.  After she awakens, she believes that the chance that the most recent coin flip was heads is 1/3.  Those events are not the same thing because there is not a one to one correspondence between awakening and coin flips.
A: How about the following solution:
The question is to assess the probability of the coin coming up "heads".
So, if the Sleeping Beauty were woken up on Monday and knew which day it is, she would indeed have to believe that the probability of "heads" is 50%.
However, were she to be woken up on Tuesday and knew which day it is, the probability of the coin coming up heads would have been zero.
Thus, the knowledge of which day it is adds crucial information changing the probability of "heads".
The Sleeping Beauty, however, doesn't know which day it is when she wakes up. We thus need to determine the probabilities of waking up either on Monday or Tuesday, respectively. 
First, let's consider the probability of it being Tuesday. 
When the experimenter flips the coin, the outcome decides which scenario of the experiment he would follow. If it's heads, the SB is woken up only on Monday. If it's tails she is woken up both on Monday and Tuesday. The probabilities of the experiment taking one of these paths are 50/50 obviously. Now, if we are in the "two-awakenings" branch, the probability of it being a Tuesday or a Monday when the SB wakes up are both 50%. We can thus calculate the total probability of it being Tuesday when the SB wakes up as 0.5*0.5=0.25.
Obviously then, the probability of it being Monday when she wakes up is 1-0.25=0.75
If the SB knew that she woke up on Tuesday, the probability of the coin having come up "heads" would have been zero.
If she, however, knew that she woke up on Monday, the probability of the coin having come up "heads" would have been 50%. But we know that the probability of it being Monday is 0.75. So, to find out the total probability of the coin having come up "heads" we need to multiply 0.75*0.5=0.375
The answer is thus, the probability that the coin came up "heads" is 37.5%
The above is just a suggestion. Please, point out, if you see flaws in my reasoning.
A: I would like to reply to @LuckyPal answer
If the experiment is done a single time I will agree with you (and with the halfers) opinion that it is much more likely that, when SB gets woken up, it's the first day and the scientist didn't win the lottery.
But, if you repeat the experiment an infinite number of times, I would actually think that when SB wakes up (not knowing which experiment she is in), she has to conclude that it's more likely that it's from a streak of 10M waking ups and that the scientist has probably won the lottery in this experiment she is in.
It's the same if you think about 10M clones: if one of the clones has been woken up, the chance that he was the chosen from the 10M after not winning ($999999/1M * 1/10M$) is lower than the chance that the scientist won the lottery and woke up every clone ($1/1M$). (The calculations are in @whuber answer, you can have more than 10M clones)
So, the clones setup is equivalent to doing infinite experiments, and the probabilities for the actual problem depend on how many experients you do (as other people have stated before me). For a single experiment the halfers options seems to be correct, for an infinite number of experiments I would say the thirders are right.
Still, if you had to bet, the more sensible option would be the thirders' (betting on the scientis winning the lottery, even for a single experiment), but that's because you know in advance that doing this, when you right you get to bet 10M times with the same outcome, when you are wrong the experiment ends. That, however, has nothing to do with the actual probability of being right or wrong.
What I mean is that (again, for a single esperiment) betting on the lottery win will probably be wrong (probability of 999999/10M), but if I'm right I will get 10M right bets, so the expected value suggests to bet on the lottery win (still the less probable option).
I think, when we try to simulate the esperiment from SB perspective, that we have to consider as a result of a simulation the coin observed in a single awakening, chosen randomly from the possible ones (this is what SB experiences, a single awakening).
This way, if we simulate many times a single experiment (single awakening), the results from each simulation will be 50% heads and 50% tails.
If we simulate many times infinite experiments (single awakening), then the probabilities converge to thirders' option.
