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.
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.