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…”

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)

brilliant entry!

How probabilities can help you on a day to day basis 🙂

je prenais pour acquis que cette stratégie était optimale, mais si on peut le prouver, ca serait joli… Tu aurais des références sur le sujet ?

on utiise ça dans les premiers TD de théorie de l’information pour expliquer la coincidence entre la quantité d’information au sens de l’optimisation de la stratégie (correspondant à l’intuition) et l’information de Shannon (en calculant la quantité d’information au sens de Shannon renvoyée par la réponse à une proposition de nombre, et dérivant cette quantité, on montre en 4 ou 5 lignes de calcul que la bonne stratégie est de propose le nombre au milieu de l’intervalle.