16
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ When you say "expected walking distance" - do you mean in the worst case, where the algorithm is probabilistic, or do you also assume some distribution on the inputs? Also - do you require your algorithm to always be correct, or to be correct w.p. 1? (or less?) - note that the algorithm you present here might never halt (but w.p. 0) $\endgroup$ – Shaull Jan 9 '15 at 9:57
  • $\begingroup$ This is similar to the linear search problem (en.wikipedia.org/wiki/Linear_search_problem). $\endgroup$ – Yuval Filmus Jan 9 '15 at 11:02
  • 2
    $\begingroup$ @Shaull - since both friends are following the same algorithm, it has to be probabilistic or they will never meet. The expectancy is over the randomization of the algorithm. $\endgroup$ – R B Jan 9 '15 at 16:30
  • $\begingroup$ In your algorithm do you mean walk $2^n$ unit time to the right with constant speed $C$? Walking $2^n$ steps may not talk 2^n time. $\endgroup$ – 吖奇说 Jan 12 '15 at 5:03
  • $\begingroup$ @0a-archy - we assume that both are moving at the same speed (let it be 1 $\frac{\text{step}}{\text{time unit}}$ unit for this matter). The idea in the algorithm I gave is that you either walk $2^n$ steps or wait equivalent time, so each iteration starts at the same time for both players. $\endgroup$ – R B Jan 12 '15 at 7:22
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.