Sleeping Beauty problem
- Background on the task
In decision theory, The Sleeping Beauty Problem
is a problem invented by Arnold Zoboff and first publicized on Usenet. The experimental
subject, named Sleeping Beauty, agrees to an experiment as follows:
Sleeping Beauty volunteers to be put into a deep sleep on a Sunday. There is then a fair coin toss.
If this coin toss comes up heads, Sleeping Beauty wakes once (on Monday) and asked to
estimate the probability that the coin toss was heads. Her estimate is recorded and she is
then put back to sleep for 2 days until Wednesday, at which time the experiment's results are tallied.
If instead the coin toss is tails, Sleeping Beauty wakes as before on Monday and asked to
estimate the probability the coin toss was heads, but is then given a drug which makes her forget
that she had been woken on Monday before being put back to sleep again. She then wakes only 1 day
later, on Tuesday. She is then asked (on Tuesday) again to guess the probability that the coin toss
was heads or tails. She is then put back to sleep and awakes as before 1 day later, on Wednesday.
Some decision makers have argued that since the coin toss was fair Sleeping Beaty should always estimate the probability of heads as 1/2, since she does not have any additional information. Others have disagreed, saying that if Sleeping Beauty knows the study design she also knows that she is twice as likely to wake up and be asked to estimate the coin flip on tails than on heads, so the estimate should be 1/3 heads.
- Task
Given the above problem, create a Monte Carlo estimate of the actual results. The program should find the proportion of heads on waking and asking Sleeping Beauty for an estimate, as a percentage of the times Sleeping Beauty is asked the question.
C++
<lang cpp>#include <iostream>
- include <random>
int main() {
std::cout.imbue(std::locale("")); const int experiments = 1000000; std::random_device dev; std::default_random_engine engine(dev()); std::uniform_int_distribution<int> distribution(0, 1); int heads = 0, wakenings = 0; for (int i = 0; i < experiments; ++i) { ++wakenings; switch (distribution(engine)) { case 0: // heads ++heads; break; case 1: // tails ++wakenings; break; } } std::cout << "Wakenings over " << experiments << " experiments: " << wakenings << '\n'; std::cout << "Sleeping Beauty should estimate a credence of: " << double(heads) / wakenings << '\n';
}</lang>
- Output:
Wakenings over 1,000,000 experiments: 1,500,090 Sleeping Beauty should estimate a credence of: 0.333253
Factor
<lang factor>USING: combinators.random io kernel math prettyprint ;
- sleeping ( n -- heads wakenings )
0 0 rot [ 1 + .5 [ [ 1 + ] dip ] [ 1 + ] ifp ] times ;
"Wakenings over 1,000,000 experiments: " write 1e6 sleeping dup . /f "Sleeping Beauty should estimate a credence of: " write .</lang>
- Output:
Wakenings over 1,000,000 experiments: 1500127 Sleeping Beauty should estimate a credence of: 0.3332204540015612
Julia
<lang julia>"""
Run the Sleeping Beauty Problem experiment `repetitions` times, checking to see how often we had heads on waking Sleeping Beauty.
""" function sleeping_beauty_experiment(repetitions)
gotheadsonwaking = 0 wakenings = 0 for _ in 1:repetitions coin_result = rand(["heads", "tails"])
# On Monday, we check if we got heads. wakenings += 1 if coin_result == "heads" gotheadsonwaking += 1 end
# If tails, we do this again, but add only if tails, so do not add. if coin_result == "tails" wakenings += 1 if coin_result == "heads" gotheadsonwaking += 1 # never done end end end
# Show the number of times she was wakened. println("Wakenings over ", repetitions, " experiments: ", wakenings)
# Return the number of correct bets SB made out of the total number # of times she is awoken over all the experiments with that bet. return gotheadsonwaking / wakenings
end
CREDENCE = sleeping_beauty_experiment(1_000_000) println("Results of experiment: Sleeping Beauty should estimate a credence of: ", CREDENCE)
</lang>
- Output:
Wakenings over 1000000 experiments: 1499534 Results of experiment: Sleeping Beauty should estimate a credence of: 0.33374768428058316
Phix
constant iterations = 1_000_000, fmt = """ Wakings over %,d repetitions = %,d Percentage probability of heads on waking = %f%% """ integer heads = 0, wakings = 0 for i=1 to iterations do integer flip = rand(2) -- 1==heads, 2==tails wakings += 1 + (flip==2) heads += (flip==1) end for printf(1,fmt,{iterations,wakings,heads/wakings*100})
- Output:
(You'll get the exact result less than 1% of the time!!)
Wakings over 1,000,000 repetitions = 1,500,000 Percentage probability of heads on waking = 33.333333%
Python
Procedural
<lang python>from random import choice
def sleeping_beauty_experiment(repetitions):
""" Run the Sleeping Beauty Problem experiment `repetitions` times, checking to see how often we had heads on waking Sleeping Beauty. """ gotheadsonwaking = 0 wakenings = 0 for _ in range(repetitions): coin_result = choice(["heads", "tails"])
# On Monday, we check if we got heads. wakenings += 1 if coin_result == "heads": gotheadsonwaking += 1
# If tails, we do this again, but add only if tails, so do not add. if coin_result == "tails": wakenings += 1 if coin_result == "heads": gotheadsonwaking += 1 # never done
# Show the number of times she was wakened. print("Wakenings over", repetitions, "experiments:", wakenings)
# Return the number of correct bets SB made out of the total number # of times she is awoken over all the experiments with that bet. return gotheadsonwaking / wakenings
CREDENCE = sleeping_beauty_experiment(1_000_000)
print("Results of experiment: Sleeping Beauty should estimate a credence of:", CREDENCE)
</lang>
- Output:
Wakenings over 1000000 experiments: 1499765 Results of experiment: Sleeping Beauty should estimate a credence of: 0.333542254953276
Functional
<lang python>Sleeping Beauty Problem
from random import choice from itertools import repeat from functools import reduce
- experiment :: (Int, Int) -> IO (Int, Int)
def experiment(headsWakings):
A pair of counts updated by a coin flip. heads, wakings = headsWakings
return ( 1 + heads, 1 + wakings ) if "h" == choice(["h", "t"]) else ( heads, 2 + wakings )
- ------------------------- TEST -------------------------
- main :: IO ()
def main():
Observed results from one million runs.
n = 1_000_000 heads, wakes = applyN(n)( experiment )( (0, 0) )
print( f'{wakes} wakenings over {n} experiments.\n' ) print('Sleeping Beauty should estimate credence') print(f'at around {round(heads/wakes, 3)}')
- ----------------------- GENERIC ------------------------
- applyN :: Int -> (a -> a) -> a -> a
def applyN(n):
n applications of f. (Church numeral n). def go(f): def ga(a, g): return g(a)
def fn(x): return reduce(ga, repeat(f, n), x) return fn return go
- MAIN ---
if __name__ == '__main__':
main()
</lang>
- Output:
1500188 wakenings over 1000000 experiments. Sleeping Beauty should estimate credence at around 0.333
Raku
<lang perl6>sub sleeping-beauty ($trials) {
my $gotheadsonwaking = 0; my $wakenings = 0; ^$trials .map: { given <Heads Tails>.roll { ++$wakenings; when 'Heads' { ++$gotheadsonwaking } when 'Tails' { ++$wakenings } } } say "Wakenings over $trials experiments: ", $wakenings; $gotheadsonwaking / $wakenings
}
say "Results of experiment: Sleeping Beauty should estimate a credence of: ", sleeping-beauty(1_000_000);</lang>
- Output:
Wakenings over 1000000 experiments: 1500040 Results of experiment: Sleeping Beauty should estimate a credence of: 0.333298
Wren
<lang ecmascript>import "random" for Random import "/fmt" for Fmt
var rand = Random.new()
var sleepingBeauty = Fn.new { |reps|
var wakings = 0 var heads = 0 for (i in 0...reps) { var coin = rand.int(2) // heads = 0, tails = 1 say wakings = wakings + 1 if (coin == 0) { heads = heads + 1 } else { wakings = wakings + 1 } } Fmt.print("Wakings over $,d repetitions = $,d", reps, wakings) return heads/wakings * 100
}
var pc = sleepingBeauty.call(1e6) Fmt.print("Percentage probability of heads on waking = $f\%", pc)</lang>
- Output:
Sample run:
Wakings over 1,000,000 repetitions = 1,500,321 Percentage probability of heads on waking = 33.304806%