Sunday evening, stupid games…

April 1, 2012
By

(This article was first published on Freakonometrics - Tag - R-english, and kindly contributed to R-bloggers)

This evening, while I was about to wash the dishes, I heard my elders starting a game (call them Him and Her)
Him: "I have picked - in my head - a number, lower than 50. Try to guess..."
Her: "No way, too difficult..."
Him: "You can try five different numbers..."
Her: ".,. um ... No, no way..."
Me: "Wait... each time we suggest a number, you tell us if yours is either above, or below ?"
You can see me coming clearly, can't you ? Using a simple subdivision rule, we have a fast algorithm (and indeed, if I have to choose between washing the dishes and playing with the kids...)
Him: "um.... ok"
Her: "Daddy, are you sure we will win ?"
Me: "Well... I cannot promise that we will win... but I am rather sure [sic] that we will win quite frequently: more gains than losses..." (I guess).
Her: "Great ! I am playing with daddy..."
Him: "um.... wait, is it one of you trick, again ? I don't to play anymore... Do you want to see the books we've chosen at the library ?"
Her: "Sure..."
Me: "What ? no one wants to see if I was right ? that we have indeed more than 50% chances to win..."
Him and her: "No !
The point of that story ? If we listen to kids, science will not go forward, trust me. But I am curious... I want to see if my intuition was correct. Actually, the intuition was based on the fact that
> 2^5
[1] 32 
> 2^6
[1] 64
so in 5 or 6 steps the algorithm of subdivision should converge. I guess... I mean, I do not know for sure, since 50 is not a power of 2, so it might be difficult, each time, to split in two: we have to deal only with integers here...
To be sure, let us substitute my laptop to my son... to pick up numbers, randomly (yes, sometimes I feel like I am Doctor Tenma, 天馬博士). The algorithm is simple: there are bounds, and at each stop I should suggest the middle of the interval. If the middle is not an integer, I suggest either the integer below or the integer above (with equal probabilities).
cutinhalf=function(a,b){
m=(a+b)/2
if(m %% 1 == 0){m=m}
if(m %% 1 != 0){m=sample(c(m-.5,m+.5),size=1)}
return(round(m))}
The following functions runs 10,000 simulations, and tells us how many times, out of 5 numbers suggested, we got the good one.
winning=function(lower=1,upper=50,tries=5,NS=100000){
SIM=rep(NA,NS)
for(simul in 1:NS){
interval=c(lower,upper)
(unknownnumber=sample(lower:upper,size=1))
success=FALSE
for(i in 1:tries){
picknumber=cutinhalf(interval[1],interval[2])
if(picknumber==unknownnumber){success=TRUE}
if(picknumber>unknownnumber){interval[2]=picknumber}
if(picknumber<unknownnumber){interval[1]=picknumber}
#print(c(unknownnumber,picknumber,success,interval))
};SIM[simul]=success};return(mean(SIM))}
It looks like the probability that we got the good number is higher than 60%,
> winning()
[1] 0.61801
Which is not bad. And if the upper limit was not 50, but something else, the probability of winning would have been the following.
VWN=function(n){winning(upper=n)}
V=Vectorize(VWN)(seq(25,100,by=5))
plot(seq(25,100,by=5),V,type="b",col="red",ylim=c(0,1))

Actually, after losing a couple of times, I am rather sure that my son would have to us that we can suggest only four numbers. In that case, the probability would have been close to 30%, as shown on the blue curve below (where four numbers only can be suggested)
Anyway, as intuited, with five possible suggestions, we were quite likely to win frequently. Actually with a probability of almost 2 out of 3...and 1 out of 3 if my son had decided to pick an number between 1 and 100, or only 4 possible suggestions... Those are quite large actually, when we think about it. It reminds me that McGyver story I mentioned a few months ago... Anyway, calculating probabilities is nice, but I still have to wash the dishes...

To leave a comment for the author, please follow the link and comment on his blog: Freakonometrics - Tag - R-english.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , ,

Comments are closed.