Zagubiony w „jednokierunkowym” koncercie

Ty i przyjaciel zgubiliście się na linii na koncercie, i żaden nie jest pewien, który z was jest dalej. Formalnie każda z nich ma jakąś całkowitą współrzędną i może podążać w kierunku wyższej współrzędnej lub pozostać na miejscu.

Zakładając, że ty i twój przyjaciel przestrzegacie dokładnie tego samego algorytmu (i nie, nie można powiedzieć „jeśli (name ==" R B ”) zrób coś :)), a początkowa odległość między wami wynosiła (co nie jest znane tobie).$x$

Jaki jest algorytm, który minimalizuje oczekiwany dystans pieszy do spotkania się ciebie i twojego przyjaciela?

Możesz założyć, że zarówno twój przyjaciel, jak i ty poruszamy się z tą samą stałą prędkością.

Przykładowy prosty algorytm mógłby wyglądać następująco:

1. Na etapie (od 0 ):$n$$0$

   • Przejdź kroków w prawo wp $3^n$ lub poczekaj3njednostek czasu inaczej.$\frac{1}{2}$$3^n$

Aby zobaczyć ten algorytm, przyjaciele spotykają się z prawdopodobieństwem 1 zastanów się, co dzieje się na etapie . Nawet jeśli przyjaciel, który był x krok do przodu zawsze chodził, a drugi zawsze pozostawał na miejscu, odległość między nimi byłaby: x + 1 + 3 + 9 + … + 3 log 3 x = $(\log_3 x+1)$$x$

Dlatego przy iteracji przyjaciel, który zdecyduje się przejść, pokona odległość 3 dziennika 3 x + 1 = 3 x , stąd z prawdopodobieństwem $\log_3 x+1$$3^{\log_3 x+1}=3x$ , przyjaciel, który jest z tyłu, dogoni i spotka się.$\frac{1}{4}$

Prostą optymalizacją (w celu zmniejszenia odległości chodzenia) byłoby, zamiast chodzenia kroków, chodzenie c x kroków, gdzie c jest podane przez: 2 + $3^x$$c^x$$c$

Dlatego optymalnym dla tego algorytmu jest $c$ $c=\frac{3+\sqrt 5}{2}\approx 2.618$

Niestety, podczas gdy ten algorytm gwarantuje, że znajomi spotkają się z prawdopodobieństwem 1, oczekiwany dystans marszu jest nieskończony, czego chciałbym uniknąć, jeśli to możliwe.

Czy istnieje bardziej wydajny algorytm?

W kroku narysuj losowo liczbę q równomiernie między 1 , 2 i 3 .$k$$q$$1$$2$$3$

• jeśli , przejdź 2 k - 1 , poczekaj 2 k + 1 , przejdź 2 k - $q = 1$$2^{k-1}$$2^{k+1}$$2^{k-1}$
• jeśli , poczekaj 2 k - 1 , przejdź 2 k - 1 , poczekaj 2 k , przejdź 2 k - 1 , poczekaj 2 k - $q = 2$$2^{k-1}$$2^{k-1}$$2^{k}$$2^{k-1}$$2^{k-1}$
• jeśli , poczekaj 2 k , przejdź 2 k , poczekaj 2 $q = 3$$2^k$$2^k$$2^k$

Na każdym kroku obaj przyjaciele przejdą 2 k kroków. Jeśli k < log 2 ( x ) + 1 , nie spotkają się podczas tego kroku, jednak jeśli k > = log 2 ( x ) + 1 , spotkają się wtedy i tylko wtedy, gdy nie narysują tego samego numeru. Prawdopodobieństwo, że to nie zdarza się to tylko 1 / 3 na każdym kroku.$k$$2^k$$k < \log_2(x) + 1$$k >= \log_2(x) + 1$$1/3$

Dlatego oczekiwany dystans marszu jest (ograniczony powyżej):

Który jest skończony i równy, jeśli mam zaufać mojej matematyce serwetkowej , do .$2^{\lceil\log_2(x)\rceil+3}-2 \le 16x$

Nawiasem mówiąc, jeśli jest zmienną losową reprezentującą przebytą odległość, nadal mamy to ∀ D > 0 , P ( d > D ) > 0 , tj. Odległość jest nieograniczona i może być dowolnie wysoka. Na szczęście prawdopodobieństwo to zanika wystarczająco szybko, aby zapewnić, że nieskończona suma ∑ ∞ D = 0 P ( d = D ) ⋅ D = E [ d ] zbiega się. Posiadanie skończonej górnej granicy dla$d$$\forall D>0, \mathrm{P}(d>D) > 0$$\sum_{D=0}^{\infty}\mathrm{P}(d=D)\cdot D = \mathbb{E}[d]$$d$ jest znacznie silniejszą własnością i uważam, że nie jest możliwe znalezienie rozwiązania, które by to spełniło.