Sleeping Beauty problem
You are encouraged to solve this task according to the task description, using any language you may know.
- 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 is 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 Beauty 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 credence or as a percentage of the times Sleeping Beauty is asked the question.
11l
<lang 11l>F sleeping_beauty_experiment(repetitions)
‘ Run the Sleeping Beauty Problem experiment `repetitions` times, checking to see how often we had heads on waking Sleeping Beauty. ’ V gotheadsonwaking = 0 V wakenings = 0 L 0 .< repetitions V coin_result = random:choice([‘heads’, ‘tails’])
// On Monday, we check if we got heads. wakenings++ I coin_result == ‘heads’ gotheadsonwaking++
// If tails, we do this again, but of course we will not add as if it was heads.. I coin_result == ‘tails’ wakenings++ I coin_result == ‘heads’ gotheadsonwaking++ // never done
print(‘Wakenings over ’repetitions‘ experiments: ’wakenings)
R Float(gotheadsonwaking) / wakenings
V 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: 1500892 Results of experiment: Sleeping Beauty should estimate a credence of: 0.332540916
Arturo
<lang rebol>sleepingBeauty: function [reps][
wakings: 0 heads: 0 do.times: reps [ coin: random 0 1 wakings: wakings + 1 if? coin = 0 -> heads: heads + 1 else -> wakings: wakings + 1 ] print ["Wakings over" reps "repetitions =" wakings] return 100.0 * heads//wakings
]
pc: sleepingBeauty 100000 print ["Percentage probability of heads on waking =" pc "%"]</lang>
- Output:
Wakings over 100000 repetitions = 150096 Percentage probability of heads on waking = 33.24805457840316 %
BASIC
BASIC256
<lang BASIC256> iteraciones = 1000000 cara = 0 dormir = 0
for i = 1 to iteraciones lanza_moneda = int(rand * 2) dormir = dormir + 1 if lanza_moneda = 1 then cara = cara + 1 else dormir = dormir + 1 end if next i
print "Wakings over "; iteraciones; " repetitions = "; dormir print "Percentage probability of heads on waking = "; (cara/dormir*100); "%" end </lang>
- Output:
Igual que la entrada de FreeBASIC.
FreeBASIC
<lang freebasic> Const iteraciones = 1000000 Randomize Timer Dim As Uinteger cara = 0, dormir = 0
For i As Uinteger = 1 To iteraciones
Dim As integer lanza_moneda = Int(Rnd * 2) + 1 dormir += 1 if lanza_moneda = 1 then cara += 1 else dormir += 1
Next i
Print Using "Wakings over #####,### repetitions = #####,###"; iteraciones ; dormir Print using "Percentage probability of heads on waking = ###.######%"; (cara/dormir*100)'; "%" Sleep </lang>
- Output:
Wakings over 1,000,000 repetitions = 1,499,718 Percentage probability of heads on waking = 33.358405%
GW-BASIC
In this simulation, Sleeping Beauty flips a coin of her own. <lang gwbasic>10 RANDOMIZE TIMER 20 MONDAY = 0 : TUESDAY = 1 30 HEADS = 0 : TAILS = 1 40 FOR SB = 1 TO 300000! 50 IF COIN = HEADS THEN GOSUB 150 ELSE GOSUB 210 60 COIN = INT(RND*2) 70 NEXT SB 80 PRINT "Sleeping Beauty was put through this experiment ";SB-1;" times." 90 PRINT "She was awoken ";AWAKE;" times." 100 PRINT "She guessed heads ";CHEADS+WHEADS;" times." 110 PRINT "Those guesses were correct ";CHEADS;" times. ";100*CHEADS/(CHEADS+WHEADS);"%" 120 PRINT "She guessed tails ";WTAILS+CTAILS;" times." 130 PRINT "Those guesses were correct ";CTAILS;" times. ";100*CTAILS/(CTAILS+WTAILS);"%" 140 END 150 REM interview if the coin came up heads 160 AWAKE = AWAKE + 1 170 NHEADS = NHEADS + 1 180 GUESS = INT(RND*2) 190 IF GUESS = HEADS THEN CHEADS = CHEADS + 1 ELSE WTAILS = WTAILS + 1 200 RETURN 210 REM interviews if the coin came up tails 220 FOR DAY = MONDAY TO TUESDAY 230 AWAKE = AWAKE + 1 240 GUESS = INT(RND*2) 250 IF GUESS = HEADS THEN WHEADS = WHEADS + 1 ELSE CTAILS = CTAILS + 1 260 NEXT DAY 270 RETURN</lang>
- Output:
Sleeping Beauty was put through this experiment 300000 times. She was awoken 449981 times. She guessed heads 224569 times. Those guesses were correct 74985 times. 33.39063 % She guessed tails 225412 times. Those guesses were correct 150378 times. 66.71251 %
Yabasic
<lang Yabasic> iteraciones = 1000000 cara = 0 dormir = 0
for i = 1 to iteraciones
lanza_moneda = int(ran(2)) dormir = dormir + 1 if lanza_moneda = 1 then cara = cara + 1 else dormir = dormir + 1 endif
next i
print "Wakings over ", iteraciones, " repetitions = ", dormir print "Percentage probability of heads on waking = ", (cara/dormir*100), "%" end </lang>
- Output:
Igual que la entrada de FreeBASIC.
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
CLU
<lang clu>% This program needs to be merged with PCLU's "misc" library % to use the random number generator.
experiment = cluster is run
rep = null own awake: int := 0 own awake_heads: int := 0 % Returns true if heads, false if tails coin_toss = proc () returns (bool) return(random$next(2)=1) end coin_toss
% Do the experiment once do_experiment = proc () heads: bool := coin_toss() % monday - wake up awake := awake + 1 if heads then awake_heads := awake_heads + 1 return end % tuesday - wake up if tails awake := awake + 1 end do_experiment % Run the experiment N times run = proc (n: int) returns (real) awake := 0 awake_heads := 0 for i: int in int$from_to(1,n) do do_experiment() end return(real$i2r(awake_heads) / real$i2r(awake)) end run
end experiment
start_up = proc ()
N = 1000000 po: stream := stream$primary_output() stream$puts(po, "Chance of waking up with heads: ") chance: real := experiment$run(N) stream$putl(po, f_form(chance, 1, 6))
end start_up </lang>
- Output:
Chance of waking up with heads: 0.333758
Dyalect
<lang dyalect>let experiments = 10000 var heads = 0 var wakenings = 0 for _ in 1..experiments {
wakenings += 1 match rnd(min: 0, max: 10) { <5 => heads += 1, _ => wakenings += 1 }
} print("Wakenings over \(experiments) experiments: \(wakenings)") print("Sleeping Beauty should estimate a credence of: \(Float(heads) / Float(wakenings))")</lang>
Excel
LAMBDA
Binding the name SLEEPINGB to the lambda expression below in the Excel Workbook Name Manager:
(See LAMBDA: The ultimate Excel worksheet function)
<lang lisp>SLEEPINGB =LAMBDA(n,
LET( headsWakes, LAMBDA(x, IF(1 = x, {1,1}, {0,2} ) )( RANDARRAY(n, 1, 0, 1, TRUE) ), CHOOSE( {1,2}, SUM(INDEX(headsWakes, 0, 1)), SUM(INDEX(headsWakes, 0, 2)) ) )
)</lang>
- Output:
The pair of values in cells B2 and C2 both result from the application of SLEEPINGB in B2.
The credence value is returned as a ratio by the expression B2/C2 in cell D2,
with the format setting Number > Fraction > Up to three digits.
fx | =SLEEPINGB(1000000) | ||||
---|---|---|---|---|---|
A | B | C | D | ||
1 | Heads | Wakenings | Credence | ||
2 | Results | 500111 | 1499889 | 1/3 |
F#
<lang fsharp> // Sleeping Beauty: Nigel Galloway. May 16th., 2021 let heads,woken=let n=System.Random() in {1..1000}|>Seq.fold(fun(h,w) g->match n.Next(2) with 0->(h+1,w+1) |_->(h,w+2))(0,0) printfn "During 1000 tosses Sleeping Beauty woke %d times, %d times the toss was heads. %.0f%% of times heads had been tossed when she awoke" woken heads (100.0*float(heads)/float(woken)) </lang>
- Output:
During 1000 tosses Sleeping Beauty woke 1519 times, 481 times the toss was heads. 32% of times heads had been tossed when she awoke
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
Go
<lang go>package main
import (
"fmt" "math/rand" "rcu" "time"
)
func sleepingBeauty(reps int) float64 {
wakings := 0 heads := 0 for i := 0; i < reps; i++ { coin := rand.Intn(2) // heads = 0, tails = 1 say wakings++ if coin == 0 { heads++ } else { wakings++ } } fmt.Printf("Wakings over %s repetitions = %s\n", rcu.Commatize(reps), rcu.Commatize(wakings)) return float64(heads) / float64(wakings) * 100
}
func main() {
rand.Seed(time.Now().UnixNano()) pc := sleepingBeauty(1e6) fmt.Printf("Percentage probability of heads on waking = %f%%\n", pc)
}</lang>
- Output:
Sample run:
Wakings over 1,000,000 repetitions = 1,500,256 Percentage probability of heads on waking = 33.310582%
Haskell
<lang haskell>import Data.Monoid (Sum(..)) import System.Random (randomIO) import Control.Monad (replicateM) import Data.Bool (bool)
data Toss = Heads | Tails deriving Show
anExperiment toss =
moreWakenings <> case toss of Heads -> headsOnWaking Tails -> moreWakenings where moreWakenings = (1,0) headsOnWaking = (0,1)
main = do
tosses <- map (bool Heads Tails) <$> replicateM 1000000 randomIO let (Sum w, Sum h) = foldMap anExperiment tosses let ratio = fromIntegral h / fromIntegral w putStrLn $ "Ratio: " ++ show ratio</lang>
*Main> main Ratio: 0.33339378051805013
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 of course we will not add as if it was heads. 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
Mathematica/Wolfram Language
<lang Mathematica>ClearAll[SleepingBeautyExperiment] SleepingBeautyExperiment[reps_Integer] := Module[{gotheadsonwaking, wakenings, coinresult},
gotheadsonwaking = 0; wakenings = 0; Do[ coinresult = RandomChoice[{"heads", "tails"}]; wakenings++; If[coinresult === "heads", gotheadsonwaking++; , wakenings++; ] , {reps} ]; Print["Wakenings over ", reps, " experiments: ", wakenings]; gotheadsonwaking/wakenings ]
out = N@SleepingBeautyExperiment[10^6]; Print["Results of experiment: Sleeping Beauty should estimate a credence of: ", out]</lang>
- Output:
Wakenings over 1000000 experiments: 1499714 Results of experiment: Sleeping Beauty should estimate a credence of: 0.333588
Nim
<lang Nim>import random
const N = 1_000_000
type Side {.pure.} = enum Heads, Tails
const Sides = [Heads, Tails]
randomize() var onHeads, wakenings = 0 for _ in 1..N:
let side = sample(Sides) inc wakenings if side == Heads: inc onHeads else: inc wakenings
echo "Wakenings over ", N, " experiments: ", wakenings echo "Sleeping Beauty should estimate a credence of: ", onHeads / wakenings</lang>
- Output:
Wakenings over 1000000 experiments: 1499971 Sleeping Beauty should estimate a credence of: 0.3333591116094911
Pascal
<lang pascal> program sleepBeau; uses
sysutils; //Format
const
iterations = 1000*1000;
fmt = 'Wakings over %d repetitions = %d'+#13#10+
'Percentage probability of heads on waking = %8.5f%%';
var
i, heads, wakings, flip: Uint32;
begin
randomize; for i :=1 to iterations do Begin flip := random(2)+1;//-- 1==heads, 2==tails inc(wakings,1 + Ord(flip=2)); inc(heads,Ord(flip=1)); end; writeln(Format(fmt,[iterations,wakings,heads/wakings*100]));
end.</lang>
- Output:
Wakings over 1000000 repetitions = 1499741 Percentage probability of heads on waking = 33.35636%
Perl
<lang perl>use strict; use warnings;
sub sleeping_beauty {
my($trials) = @_; my($gotheadsonwaking,$wakenings); $wakenings++ and rand > .5 ? $gotheadsonwaking++ : $wakenings++ for 1..$trials; $wakenings, $gotheadsonwaking/$wakenings
}
my $trials = 1_000_000; printf "Wakenings over $trials experiments: %d\nSleeping Beauty should estimate a credence of: %.4f\n", sleeping_beauty($trials);</lang>
- Output:
Wakenings over 1000000 experiments: 1499816 Sleeping Beauty should estimate a credence of: 0.333
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 of course we will not add as if it was heads.. 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
Quackery
<lang Quackery> [ $ "bigrat.qky" loadfile ] now!
[ say "Number of trials: " dup echo cr 0 ( heads count ) 0 ( sleeps count ) rot times [ 1+ 2 random if [ 1+ dip 1+ ] ] say "Data: heads count: " over echo cr say " sleeps count: " dup echo cr say "Credence of heads: " 2dup 20 point$ echo$ cr say " or approximately: " 10 round vulgar$ echo$ cr ] is trials ( n --> n/d )
1000000 trials</lang>
- Output:
Number of trials: 1000000 Data: heads count: 500212 sleeps count: 1500212 Credence of heads: 0.33342754224069664821 or approximately: 1/3
R
There's nothing complicated here. Pretty much every language that resembles C is going to use virtually the same solution. <lang rsplus>beautyProblem <- function(n) {
wakeCount <- headCount <- 0 for(i in seq_len(n)) { wakeCount <- wakeCount + 1 if(sample(c("H", "T"), 1) == "H") headCount <- headCount + 1 else wakeCount <- wakeCount + 1 } headCount/wakeCount
} print(beautyProblem(10000000))</lang>
- Output:
[1] 0.3335838
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
Red
<lang rebol>Red ["Sleeping Beauty problem"]
experiments: 1'000'000 heads: awakenings: 0 loop experiments [
awakenings: awakenings + 1 either 1 = random 2 [heads: heads + 1] [awakenings: awakenings + 1]
] print ["Awakenings over" experiments "experiments:" awakenings] print ["Probability of heads on waking:" heads / awakenings]</lang>
- Output:
Awakenings over 1000000 experiments: 1500063 Probability of heads on waking: 0.3332773356852345
REXX
When using Regina REXX, the seed specified (for random) was 46. <lang rexx>/*REXX pgm uses a Monte Carlo estimate for the results for the Sleeping Beauty problem. */ parse arg n seed . /*obtain optional arguments from the CL*/ if n== | n=="," then n= 1000000 /*Not specified? Then use the default.*/ if datatype(seed, 'W') then call random ,,seed /* Specified? Then use as RAND seed*/ awake= 0 /* " " " " awakened. */
do #=0 for n /*perform experiment: 1 million times?*/ if random(,1) then awake= awake + 1 /*Sleeping Beauty is awoken. */ else #= # + 1 /* " " keeps sleeping. */ end /*#*/ /* [↑] RANDOM returns: 0 or 1 */
say 'Wakenings over ' commas(n) " repetitions: " commas(#) say 'The percentage probability of heads on awakening: ' (awake / # * 100)"%" exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?</lang>
- output when using the input of: , 46
Wakenings over 1,000,000 repetitions: 1,500,000 The percentage probability of heads on awakening: 33.3333333%
Ruby
<lang ruby>def sleeping_beauty_experiment(n)
coin = [:heads, :tails] gotheadsonwaking = 0 wakenings = 0 n.times do wakenings += 1 coin.sample == :heads ? gotheadsonwaking += 1 : wakenings += 1 end puts "Wakenings over #{n} experiments: #{wakenings}" gotheadsonwaking / wakenings.to_f
end
puts "Results of experiment: Sleeping Beauty should estimate a credence of: #{sleeping_beauty_experiment(1_000_000)}" </lang>
- Output:
Wakenings over 1000000 experiments: 1499604 Results of experiment: Sleeping Beauty should estimate a credence of: 0.3336854262858728
Swift
<lang swift>let experiments = 1000000 var heads = 0 var wakenings = 0 for _ in (1...experiments) {
wakenings += 1 switch (Int.random(in: 0...1)) { case 0: heads += 1 default: wakenings += 1 }
} print("Wakenings over \(experiments) experiments: \(wakenings)") print("Sleeping Beauty should estimate a credence of: \(Double(heads) / Double(wakenings))")</lang>
- Output:
Wakenings over 1000000 experiments: 1500036 Sleeping Beauty should estimate a credence of: 0.3333013341013149
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%