Lost in a "one directional" concert 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?
At step $k$, draw a random number $q$ uniformly between $1$, $2$, and $3$.
  
  
  if $q = 1$, walk $2^{k-1}$, wait $2^{k+1}$, walk $2^{k-1}$
  if $q = 2$, wait $2^{k-1}$, walk $2^{k-1}$, wait $2^{k}$, walk $2^{k-1}$, wait $2^{k-1}$
  if $q = 3$, wait $2^k$, walk $2^k$, wait $2^k$
  


At each step $k$, both friends will walk $2^k$ steps. If $k &lt; \log_2(x) + 1$, they won't meet during that step, however if $k &gt;= \log_2(x) + 1$, they will meet if and only if they don't draw the same number. The probability that this doesn't happen is only $1/3$ at each step.

Hence the expected walking distance is (bounded above by):

$$2\left(\sum_{k=0}^{\lceil\log_2(x)\rceil}2^k+3^{\lceil\log_2(x)\rceil}\sum_{k=\lceil\log_2(x)\rceil+1}^{\infty}\left(\frac{2}{3}\right)^k\right)$$

Which is finite, and equal, if my napkin maths are to be trusted, to $2^{\lceil\log_2(x)\rceil+3}-2 \le 16x$.

By the way, if $d$ is the random variable representing the distance walked, we still have that $\forall D&gt;0, \mathrm{P}(d&gt;D) &gt; 0$, i.e. the distance is unbounded and can end up being arbitrarily high. Luckily this probability vanishes fast enough to ensure that the infinite sum $\sum_{D=0}^{\infty}\mathrm{P}(d=D)\cdot D = \mathbb{E}[d]$ converges. Having a finite upper bound for $d$ is a much stronger property and I reckon it's not possible to find a solution satisfying it.