This one is a classic, so I can just copy-paste the solution from Google.
The more interesting point is that this is one of those cases where math doesn’t correspond to reality.
In the spirit of “trying to offer concrete models and predictions” I propose you a challenge: write a bot which would consistently beat my Rob implementation over the long run enough that it would show on numerical experiments. I need some time to work on implementing it (and might disappear for a while, in which case consider this one forfeited by me).
One of the rules I propose that neither of us are allowed to use details of others’ implementation, in order to uphold the spirit of the original task.
A simple way to do this is for ROB to output the pair of integers {n, n+1} with probability K((K-1)/(K+1))^|n|, where K is some large number. Then even if you know ROB’s strategy the best probability you have of winning is 1⁄2 + 1/(2K).
If you sample an event N times the variance in your estimate of its probability is about 1/N. So if we pick K >> √N then our probability of success will be statistically indistinguishable from 1⁄2.
The only difficulty is implementing code to sample from a geometric distribution with a parameter so close to 1.
This one is a classic, so I can just copy-paste the solution from Google. The more interesting point is that this is one of those cases where math doesn’t correspond to reality.
In the spirit of “trying to offer concrete models and predictions” I propose you a challenge: write a bot which would consistently beat my Rob implementation over the long run enough that it would show on numerical experiments. I need some time to work on implementing it (and might disappear for a while, in which case consider this one forfeited by me).
One of the rules I propose that neither of us are allowed to use details of others’ implementation, in order to uphold the spirit of the original task.
A simple way to do this is for ROB to output the pair of integers {n, n+1} with probability K((K-1)/(K+1))^|n|, where K is some large number. Then even if you know ROB’s strategy the best probability you have of winning is 1⁄2 + 1/(2K).
If you sample an event N times the variance in your estimate of its probability is about 1/N. So if we pick K >> √N then our probability of success will be statistically indistinguishable from 1⁄2.
The only difficulty is implementing code to sample from a geometric distribution with a parameter so close to 1.