You and a friend lost each other on the line to a concert, and neither is sure which of you is further ahead. Formally, each is at some integer coordinate and may only walk towards a higher coordinate or stay in place.
Assuming you and your friend are following the exact same algorithm (and no, you may not say "if (name=="R B") do something :) ), and the initial distance between the two of you was $x$ (which is not known to you).
What is the algorithm which minimizes the expected walking distance till you and your friend meet?
You may assume both your friend and yourself are moving in the same constant speed.
An example simple algorithm would be something like:
At stage $n$ (starting from $0$):
- Walk $3^n$ steps to the right w.p. $\frac{1}{2}$ or wait $3^n$ time units otherwise.
To see this algorithm makes the friends meet with probability 1 consider what happens at stage $(\log_3 x+1)$. Even if the friend that was $x$ step ahead always walked and the other always stayed in place, the distance between the two would be: $$x+1+3+9+\ldots+3^{\log_3 x}=2x+\frac{x-1}{2}\leq 3x$$
Therefore, at the $\log_3 x+1$ iteration, the friend which chooses to walk will cover distance of $3^{\log_3 x+1}=3x$, hence with probability $\frac{1}{4}$, the friend which is behind will catch up and they will meet.
A simple optimization (to reduce walking distance) would be, instead of walking $3^x$ steps, walking $c^x$ steps, where $c$ is given by: $$2+\frac{1}{c-1}=c$$
Hence the optimal $c$ for this algorithm is $c=\frac{3+\sqrt 5}{2}\approx 2.618$
Unfortunately, while this algorithm guarantees that the friends will meet with probability 1, the expected walking distance is infinite, which is something I'd like to avoid if possible.
Is there a more efficient algorithm?