How to Win a Guessing Game - Numberphile

A clever use of random numbers to improve your odds in a number guessing game.
More links & stuff in full description below ↓↓↓

NUMBERPHILE

Videos by Brady Haran

[TakeWalker]

I am so very disappointed you didn't play the game. :(

[BunniBuu]

From the logical standpoint, this seems to be what the video tries to point out:
-If K > A > B, you lose.
-If K < A < B, you lose.
-If A > B > K, you win.
-If A < B < K, you win.
-If A > K > B, you win.
-If A < K < B, you win.

Theoretically, it seems like you should win 2/3 of the time with this strategy.

This logic seems to have some flaws though, as if you're working with the infinite realm of real numbers, the chances of getting a midpoint with A, B, and K being completely random, is pretty negligible. If you are working with a finite realm of real, rational numbers, however, say you make bounds of -100 and +100, then you might as well use the midpoint (in this case 0) as your "K" and you now have a >50% chance no matter what numbers come up. I'm not really the best at maths, but that's my take on it lol

[jaimebenito]

Using real random 9-digit integers (not pseudo-generators) for A, B and K, and guessing 3333 times I get the correct guess 67.8% of the time! A second attempt with 3333 guesses gave me 66.1%. It seems to be around 2/3. These random numbers have no particular distribution, so all numbers are equally likely.

[MarcDittner]

When the numbers A and B are chosen from the real number line, which has no lower and no upper bound, the distribution of K should also have no upper and no lower bound. Therefore, P(A<K<B) tends to 0.And therefore, the chance of guessing the lower, or higher, number is 50% + the Borel probablity measure of the unbounded real number line. This amounts to the chance of guessing the lower number correctly, being 50%.
Mr. Bellos assumes a prior probability distribution for the initial guesses of A and B. And this is where we fare into the territory of Bayesian Statistics.
I loved the thought experiment, though.

[Jkirek_]

I feel this is heavily reliant on you knowing the range from which A and B are chosen. If you tell someome clever what you're going to do, they'll pick something like A=g64+870070039 and B =g64+870070040 making your odds pretty much 50% again.

[kawaiimmy]

What if instead of just choosing one random number, you generate two?  Would your odds improve even more?  

Suppose you had two random numbers prepared, K and M. There are 4! possible permutations of A, B, K and M.  If we assume K<M, then there are 4!/2 permutations, or just 12. Since they are all random, each permutation is equally likely.

When he flips over A there are 3 possible scenarios:
1. A<K<M
2. K<A<M
3. K<M<A

Consider option 1.  Four of our permutations satisfy it: B<A<K<M; A<B<K<M; A<K<B<M; and A<K<M<B, which are all equally likely. Which means we'd have a 75% chance of being right in guessing that A<B.

For option 2, there is a 50% chance that A<B.
For option 3, there is a 75% chance that A>B

Out of our 12 total permutations, 8 of them would lead to success (3 for option 1, 2 for option 2, and 3 for option 3).  So, 2/3rds chance.  When you only have one random number, K, there are 3! permutations, and 4 of them are successful, which is *also* a 2/3rds chance.

So, I guess it doesn't improve our odds, but is that always true?  Would choosing 3 random numbers work better?

Suppose you choose N random numbers, and assume they are in order, so there would be (N+2)!/N! permutations, or just (N+1)(N+2). Flipping over A would have N+1 scenarios, because there are N+1 places A can be in the ascending numbers.  Each scenario would have N+2 possible positions for B. If A is less than all of your numbers, then by guessing A<B, you'd be correct so long as B is to the right of A in the ascending chain, and there are N+1 ways that B could be to the right of A.  For option 2, there are N ways.  Option 3, N-1 ways...etc.

If N is even: when A is in the middle, then there are N/2+1 successful permutations for that option, and for later options, the number of successes starts increasing again. The total number of successful permutations would then be (N+1)+N+(N-1)+...+(N/2+1)+...+(N-1)+N+(N+1), which can be simplified to (3N/4+1/2)(N+2).  Probability of success is therefore (3N/4+1/2)(N+2)/((N+1)*(N+2)) = (3N/4+1/2)/(N+1)

If N is odd: The number of successes starts increasing again after A passes the 
(N+1)/2 term. Total successful permutations = ((N+1)+N+...+((N+1)/2+1))*2
It's multiplied by two because it is symmetrical in the odd case.  All that stuff simplifies to (3N/4+5/4)(N+1).  Probability of success is (3N/4+5/4)(N+1)/((N+1)(N+2)) = (3N/4+5/4)/(N+2)

Let P(N) be the probability of success function (this function is piecewise). If you plug in N+1 for N in the even equation, you get the odd equation. Coincidence maybe? This means that P(1)=P(2), P(3)=P(4), P(5)=P(6), etc.

This is an amazing result! Notice that P(1) and P(2) give us 2/3rds. But P(3) is a 70% success rate! P(N) approaches 75% as N approaches infinity. This begs the question, is there a method to achieve greater than 75% success?

[marcinkozlowski]

The main problem here is that, unless I'm mistaken, we don't have a way to generate discrete random integers from an unbounded set - no computer in the world can generate numbers up to plus infinity (for hopefully obvious reasons). If we have a bounded set, picking K as the mid point of that set yields even better results than a random K (again, hopefully obvious - if A is in the lower half of the whole set, then there is a higher chance of B > A (the opposite is also true).

EDIT: Just to back this up with some numbers: for random numbers in range 1 <-> 1000 (inclusive), we guess correctly 50% of times when choosing randomly, 66% for a random K and 75% for K = 500

EDIT 2: Applying the logic used in this video - to have the greatest chance of guessing correctly, we want such a K that has the highest chance of being between A and B (or B and A depending on which is bigger). Mid point of the range of all possible numbers is the best choice.

[DrDeeDot]

I see 2/3 success rates announced by a lot of commenters who are running Monte Carlo simulations to test Alex's algorithm. If A and B are chosen randomly from the set of finite numbers (this seems to be the case for those running Monte Carlo simulations), then one can simplify the winning algorithm by simply flipping A, and if A is in the lower half of the distribution of possible numbers, then one should bet that B>A. If A is in the upper half of the distribution of possible number, than one should bet that A>B. I think you'll get similar winning results.

Things change when the set of possible numbers is infinite.

[ThistleBlue]

Ah, the amazing uses of RNG. Praise RNGesus!

[enchomishinev]

Well if we simplify the game and assume that you know a finite interval [L;R] in which A and B will be (as you said, most people will go for something like [1;100]) then we can actually calculate the win-chance and it doesn't depend on the interval.

We can ignore the chance of K=A or K=B as it is very small and shouldn't affect the answer. Then we have three numbers A, B and K chosen at random. It easy to see that there are 6 possibilities for their ordering : A<B<K ; A<K<B; B<A<K; B<K<A; K<A<B and finally K<B<A. Two of them have K in the middle, and all of them are equally likely, so the chance of K falling between A and B is 1/3.

Then we know that in 1/3 of the cases we will win with 100% chance and in the rest 2/3 we're just going by luck, so 50%. This gives us a total of 66.6% winning chance in general :)

Of course in real-world you can't define the interval [L;R] with certainty, but hey, your chances can't get worse than 50% :D

[bit_pineapple]

I'm a jerk and I picked pi and pi plus 1/grahams number.

[RalphTheodory]

Can i say that i'm absolutely in love with your channel and your content, i've been watching your videos for so long, I feel very happy watching your videos, you bring out my inner geek and i feel like i want to find someone to keep discussing maths and numbers all night long ! Thank you

[georgehornsby]

Never knew Michael Sheen was so into maths!

[geniusmp]

I really like that in the middle of the video, I was thinking that you're basically taking a choice between two numbers and turning it into a Monty Hall problem, to take advantage of the probability benefits of having a third choice. And then you linked to your video on the Monty Hall problem at the end of the video.

[EebstertheGreat]

K doesn't have to be generated randomly, just according to some mechanism the other person cannot predict. For instance, I could pick K = 10 every time, but as long as my opponents don't know that's what I am going to do, I still have a greater than 50% chance of winning. On the other hand, if my opponent _does_ know how I will choose my K, he can choose A and B in order to minimize my advantage to any arbitrary degree. (However, as long as the random distribution covers all real numbers, albeit not uniformly, the probability will always be greater than 50%.)

[rikschaaf]

If you consider all the finite real numbers as being possible, then the gap between A and B will be infinitesimally small, because there is always a significantly higher number than the larger of the 2 and a significantly lower number than the lower of the 2. For example, if you just were to take the numbers between X and Y where X is the absolute value of 10^42 times the difference between A and B added to the highest number and Y is the absolute value of 10^42 times the difference of A and B removed from the lower number, then the chance of taking K between A and B is 1/(2*10^42). Now replace 10^42 with the highest number you can think of (limit -> inf) and the chance of getting K between A and B gets infinitely small (chance A<K<B -> 0)

[jasondalton]

He stated that the guesser doesn't know which is larger, A or B, but that's critical to his strategy. If B is smaller, he'll guess wrong more than 50% of the time. So I think any perceived benefit of guessing K to fall between A and B is made null by not knowing their order.

[michaelhultstrom]

Perhaps a more interesting thing is the development of the variation with increasing number of guesses. So the average of a large number of trials is 66.68%. If you follow the development of the confidence interval of your chance of being right depending on how many guesses you get (still using 1000 trials). The progression is
 1:  -24 to 158
 2:   21 to 113
 4:   44 to 90
 8:   55 to 79
 16:   61 to 73
 32:   64 to 70
 64:   65.6  to 68.4
 128:   66.3  to 67.7
 256:   66.6  to 67.3

## Code
means <- rep(NA, 8)
cis <- rep(NA, 8)
for (N in 0:8) {
l <- rep(NA, 1000)
m <- rep(NA, 2^N)
for (j in 1:1000) {
  for (i in 1:2^N) {
    n <- rnorm(3, mean = 50, sd = 20)
    m[i] <- n[1]<n[2] & n[1]<n[3] | n[1]>n[2] & n[1]>n[3]}
l[j] <- mean(m)}
means[N+1] <- mean(l)
cis[N+1] <- sd(l)/sqrt(2^N)*1.96}
## table of confidence intervals
cbind(round((mean(means)-cis)*100, digits = 0), round((mean(means)+cis)*100, digits = 0))
## nice plot
plot(x = 1:9,
     means,  
     ylim = c(-0.5, 2),  
     xlab = "2^n")
     segments(1:9, mean(means)-cis, 1:9, mean(means)+cis)

[LucaMasters]

Reading the comments on this video is infuriating for a very different reason than with the comments on most YouTube videos. They're not completely idiotic, but it's people making the same basic programming error (choosing A, B, and K all from the same finite set) over and over and over again and thus "confirming" everyone else's code is "correct".

That plus the recurring argument about p approaches 0 without limit vs. p=0.

[SyntekkTeam]

I'd say it's still more or less 50 : 50, saying a < b is more likely when a < k is based on the assumption "infinity < infinity + n" where n is a finite number. No matter how large n is it still makes an insignificant difference. When working with infinity we generally would say "infinity = infinity + n" because infinity is defined as the largest number possible. So under those circumstances this problem would be a 50 : 50 chance.