{"word_count": 424, "character_count": 2687}
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&#62; lastchocolate=function(dark=80,milk=20){+ s=1+ while(dark+milk&#62;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&#62;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&#62; set.seed(1)&#62; m=lastchocolate(dark=80,milk=20)&#62; for(s in 1:1999){m=cbind(m,lastchocolate(dark=80,milk=20))}&#62; apply(m,1,sum)[1] 1022 978So 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 . Thenout of chocolates, the probability to pick a milk chocolate egg is . Assume that it is  for all pairs  such that  and .Assume that after some steps, there are  and  chocolates, with  (again, at least one egg has been eaten). The probability to have  isSimilarly, the probability to have  isSo, the probability that both are strictly positive is thenThen we can use our inductive assumption. Thus, the overall probability that the last egg is a milk one iswhere the part on the left is  and the second one is . This probability is exactly one half (straightforward).