A recent numberphile episode had a neat idea of how to, apparently, beat the odds in guessing whether one known number is larger than an unknown random number, by adding a third random number.
Well, to back up, the game is this: you pick any two real numbers and write them down on two cards, one number per card. I get to flip a card and then decide whether or not it is larger or smaller than the other card, sight unseen. The claim is that I can do this with better than 50% success if I pick a third number at random and:
- if it is larger than the number I flipped, I guess the unknown number is larger
- if it is smaller than the number I flipped, I guess the unknown number is smaller
At the end of the video he supposes that if this was run with real people they would mostly pick numbers within some easily accessible range, he says between 10 and 50, but I'll extend it to 0 and 50 because. Now we can be clever and pick the distribution of the third number to maximize the odds of us picking a number between the two numbers, thus guaranteeing our victory.
I set this up as a simple iterator in python, using
numpy as it has a convenient set of random number generators.
My person picks two real numbers,
B, then a third number
k is chosen from a normal distribution. If we win we get 1 point, if we lose we lose 1 point (or win -1 points). For comparison I also see what would happen if I flipped a coin and determined the game that way.
import numpy as np def guessing_game(trials=100, l=0, h=50): mean = 0.5*(l+h) stdev = np.sqrt((1.0/12))*(h-l) i = 0 while i<trials: A,B = np.random.uniform(low=l,high=h, size=2) coin_flip = np.random.randint(1) k = np.random.normal(mean,stdev) #flip a coin if (coin_flip<1 and A<B) or (coin_flip>0 and A>=B): coin = 1 else: coin = -1 # we use our third random number as a strategy if (A<k and A<B) or (A>=k and A>=B): strategy = 1 else: strategy = -1 yield (coin,strategy) i +=1
I can run a game of 100 trials and see what happens. By plotting the cumulative score it is more obvious if our strategy pays off, even a slight advantage to one side or the other will accumulate over time and see the line race off in one direction.
Clearly there is an advantage to our strategy, it accumulates points in the long run whereas the naive coin flips strategy fluctuates around zero.
Because computers are magic math machines, I can run this 100 trial game 1000 times and see what the distribution of final scores looks like.
That the histograms resemble bell curves is not surprising. However that these bell curves peak at different final scores tells us there is a difference between our two strategies, and my result from above wasn't just a fluke.
Coin flipping appears to be centered around a score of zero, so in the long run flipping coins doesn't really pay off. On the other hand the guessing game strategy is centered around a score of 40, so in the long run this is a good idea.
Which is to say that if we know or suspect what range of values our opponent will chose from, we can tailor our random number selection and do much better than chance at guessing whether
A is greater or lesser than
As usual the ipython notebook is on github