Потерянный в одностороннем концерте

Вы и друг потеряли друг друга в очереди на концерт, и никто не уверен, кто из вас еще впереди. Формально каждый из них имеет некоторую целочисленную координату и может идти только к более высокой координате или оставаться на месте.

Предполагая, что вы и ваш друг придерживаетесь одного и того же алгоритма (и нет, вы не можете сказать «если (name ==« R B ») что-то делаете :)), и начальное расстояние между вами было (что не известно вам).$x$

Каков алгоритм, который минимизирует ожидаемое расстояние ходьбы, пока вы и ваш друг не встретитесь?

Вы можете предположить, что и ваш друг, и вы движетесь с одинаковой постоянной скоростью.

Пример простого алгоритма будет выглядеть примерно так:

1. На этапе (начиная с 0 ):$n$$0$

   • Прогулка шагов к правильному сор $3^n$ или подождите3nединиц времени в противном случае.$\frac{1}{2}$$3^n$

Чтобы увидеть, что этот алгоритм заставляет друзей встретиться с вероятностью 1, подумайте, что происходит на этапе . Даже если друг, который был на x шаг впереди, всегда шел, а другой всегда оставался на месте, расстояние между ними было бы: x + 1 + 3 + 9 + … + 3 log 3 x = 2 x + x - $(\log_3 x+1)$$x$

Следовательно, на итерации друг, который выбирает прогулку, преодолеет расстояние 3 log 3 x + 1 = 3 x , следовательно, с вероятностью $\log_3 x+1$$3^{\log_3 x+1}=3x$ , друг, который позади, догонит, и они встретятся.$\frac{1}{4}$

Простая оптимизация (для уменьшения пройденного расстояния) состояла бы в том, чтобы вместо шаговых шагов пройти х х шагов, где с определяется как: 2 + $3^x$$c^x$$c$

Таким образом, оптимальная для этого алгоритма является C = 3 + $c$ $c=\frac{3+\sqrt 5}{2}\approx 2.618$

К сожалению, хотя этот алгоритм гарантирует, что друзья встретятся с вероятностью 1, ожидаемое расстояние ходьбы бесконечно, чего я бы хотел избежать, если это возможно.

Есть ли более эффективный алгоритм?

На шаге нарисуйте случайное число q равномерно между 1 , 2 и 3 .$k$$q$$1$$2$$3$

• если , пройти 2 k - 1 , подождать 2 k + 1 , пройти 2 k - $q = 1$$2^{k-1}$$2^{k+1}$$2^{k-1}$
• если , подождите 2 k - 1 , пройдитесь 2 k - 1 , подождите 2 k , пройдитесь 2 k - 1 , подождите 2 k - $q = 2$$2^{k-1}$$2^{k-1}$$2^{k}$$2^{k-1}$$2^{k-1}$
• если , подождите 2 k , пройдите 2 k , подождите 2 $q = 3$$2^k$$2^k$$2^k$

На каждом шаге оба друга пройдут 2 k шагов. Если k < log 2 ( x ) + 1 , они не встретятся на этом шаге, однако, если k > = log 2 ( x ) + 1 , они встретятся тогда и только тогда, когда они не нарисуют одно и то же число. Вероятность того, что этого не происходит только 1 / 3 на каждом шаге.$k$$2^k$$k < \log_2(x) + 1$$k >= \log_2(x) + 1$$1/3$

Следовательно, ожидаемое расстояние ходьбы (ограничено сверху):

Который конечен и равен, если верить моей математике с салфетками, .$2^{\lceil\log_2(x)\rceil+3}-2 \le 16x$

$d$$\forall D>0, \mathrm{P}(d>D) > 0$$\sum_{D=0}^{\infty}\mathrm{P}(d=D)\cdot D = \mathbb{E}[d]$$d$ это гораздо более сильное свойство, и я считаю, что невозможно найти решение, удовлетворяющее его.