[Solved]: Lost in a "one directional" concert

Problem Detail: 

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:

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

Asked By : R B

Answered By : David Durrleman

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 < \log_2(x) + 1$, they won't meet during that step, however if $k >= \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>0, \mathrm{P}(d>D) > 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37093