Suppose two robots are competing in a game of long jump along the real number line. They both start at 0. Each round a robot must draw a real number from [0,1], distributed uniformly, and add the drawn number to its current position. It can then choose to wait or jump. Waiting means the robot will play another round. Jumping means the robot will draw a final real number between [0,1], uniformly, and “land” at the sum of its current position and the number drawn. The place on the number line at which the robot lands is considered its final score. The robot must take off (start its jump) prior to passing “1.0” on the number line. Otherwise the jump violates the rules (lane violation) and receives a score of 0.
Assume that a robot does not know the other robot’s moves until both robots have completed their attempt. What is the probability that a robot receives a score of zero on an attempt?
0, Draw 0.25, Wait, Draw 0.35, Wait, Draw 0.10, Jump, Draw 0.75
The final score of such a sequence of draws and decisions is 1.45
0, Draw 0.75, Wait, Draw, 0.75 (Violation)
This is a violation because the robot failed to jump before passing over the take-off point.
I make the assumption that the optimal strategy is to wait if the current position is ≤ 0.5 and jump otherwise. This is because the expected value of a draw is 0.5. If the current position is less than 0.5, the expected next position will be less than 1. Otherwise the expected next position will be greater than 1, leading to a violation. In other words, as long as the current position is less than 1, there is higher probability of drawing a number which advances you to a position which is less than 1 than a position greater than 1, and therefore you should wait at least another round before jumping. These values can be tweaked to make the strategy more aggressive or more conservative.
Formalization
Let S be the sample space. It contains all possible outcome sequences of the form $d_1d_2d_3...[j]d_n$. $d_i$ is the i’th draw and is a real number in [0,1]. The j denotes a jump by the robot. j only exists within the sequence if the sum of the draws prior to it was greater than 0.5 as per the optimal strategy and less than 1 per the rules of the game. For sequences where there is a jump, there will always be 1 and only 1 draw following the jump. The final position of the robot, i.e the final score is the sum of all draws in the sequence. If there is no jump within the sequence it implies the robot received a score of 0 due to a lane violation. A lane violation can only happen if the sum of $d_1$ to $d_{n-1}$ is ≤ 0.5 but the sum $d_1$ to $d_{n}$ is ≥ 1. This happens because our strategy opts to wait for another draw if the sum of the draws so far is ≤ 0.5 due to the fact that the total sum of the draws after incorporating the new draw (i.e the next position of the robot) is more likely to be less than 1 rather than greater than 1. Therefore, it makes sense to try to get closer to the take off point prior to jumping.
Finding the probability that an attempt will score a zero is equivalent to finding the fraction of sequences within S which don’t contain the string “j” for jump. This in turn is equivalent to finding the probability a sequence of length 2 has no “j”, or a sequence of length 3 has no “j”, or a sequence of length 4 has no “j”, and so on and so forth up till a sequence of infinite draws that have no “j”:
$$ P(\text{s is an invalid sequence)} = P(\text{s is an invalid sequence of length 2})\lor P(\text{s is an invalid sequence of length 3})\lor P(\text{s is an invalid sequence of length 4})\lor...\lor P(\text{s is an invalid sequence of length n}) $$