Assume that there are (say) 100 chocolate eggs in a basket, 20 are dark chocolate, while 80 are milk chocolate. Unfortunately, eggs are wrapped, and there is no way you can distinguish them. My daughter has the following algorithm for eating them (and she actually plans to eat all of them)
- if there are eggs in her basket, she picks one – at random – looks if it is either dark or milk chocolate, write it down on a piece of paper (just to remember how many of each kind are left), eat it, and move to strategy 2.
- if there are eggs in her basket, she picks one – at random – looks if it is either dark or milk chocolate, write it down on a piece of paper and:
- if it is the same kind as the one she got before, then eat it, and go again to step 2.
- if it is not the same kind as the one she got before, she wraps it back, and go again to step 1.
At the end, if there is only one egg left, the probability that it is a milk chocolate egg is exactly 1/2… Nice, isn’t it ?
It is a simple rejection technique algorithm. It is possible to run some code to check the answer. The algorithm which return the taste of the last egg remaining is
> lastchocolate=function(dark=80,milk=20){ + s=1 + while(dark+milk>1){ + if(s==1){ + (eatnow=sample(c("D","M"),prob=c(dark,milk),size=1)) + if(eatnow=="D"){dark=dark-1}; + if(eatnow=="M"){milk=milk-1}; + eatbefore=eatnow;s=2} + if(s==2){ + if(dark+milk>1){ + s=1; + eatnow=sample(c("D","M"),prob=c(dark,milk),size=1) + if(eatnow==eatbefore){s=2 + eat=eatnow; + if(eatbefore=="D"){dark=dark-1}; + if(eatbefore=="M"){milk=milk-1}} + }} + } + return(c(dark,milk))}
If we run it 2,000 times, we obtain
> set.seed(1) > m=lastchocolate(dark=80,milk=20) > for(s in 1:1999){m=cbind(m,lastchocolate(dark=80,milk=20))} > apply(m,1,sum) [1] 1022 978
So it looks like we have half chance to end up with a dark chocolate egg, and half chance to end up with a milk chocolate egg.
Let us prove that result… Let denote the number of milk chocolate and
the number of dark chocolate eggs, when we start. Consider an inductive proof of the fact that the probability has to be
. The first step is when
. Then