Perdido en un concierto "one directional"

Usted y un amigo se perdieron en la línea en un concierto, y ninguno de los dos está seguro de cuál de ustedes está más adelante. Formalmente, cada uno está en alguna coordenada entera y solo puede caminar hacia una coordenada más alta o permanecer en su lugar.

Suponiendo que usted y su amigo estén siguiendo exactamente el mismo algoritmo (y no, no pueden decir "if (name ==" R B ") hacen algo :)), y la distancia inicial entre ustedes dos fue $x$ (que no es conocido por ti).

¿Cuál es el algoritmo que minimiza la distancia de caminata esperada hasta que usted y su amigo se encuentren?

Puede suponer que tanto su amigo como usted se mueven a la misma velocidad constante.

Un ejemplo de algoritmo simple sería algo como:

1. En la etapa $n$ (a partir de $0$ ):

   • Camina $3^n$ pasos hacia la derecha wp $\frac{1}{2}$ o espere$3^n$unidades de tiempo de lo contrario.

Para ver este algoritmo hace que los amigos se encuentren con probabilidad 1 considere lo que sucede en la etapa $(\log_3 x+1)$ . Incluso si el amigo que estaba $x$ paso adelante siempre caminaba y el otro siempre permanecía en su lugar, la distancia entre los dos sería:

Por lo tanto, en la iteración , el amigo que elige caminar cubrirá la distancia de 3 log 3 x + 1 = 3 x , por lo tanto, con probabilidad $\log_3 x+1$$3^{\log_3 x+1}=3x$ , el amigo que está detrás se pondrá al día y se encontrarán.$\frac{1}{4}$

Una optimización simple (para reducir la distancia a pie) sería, en lugar de caminar pasos, caminar c x pasos, donde c viene dada por: 2 + $3^x$$c^x$$c$

Por lo tanto, la óptima para este algoritmo es c = 3 + $c$ $c=\frac{3+\sqrt 5}{2}\approx 2.618$

Desafortunadamente, aunque este algoritmo garantiza que los amigos se encontrarán con la probabilidad 1, la distancia de caminata esperada es infinita, que es algo que me gustaría evitar si es posible.

¿Hay un algoritmo más eficiente?

En el paso , dibuja un número aleatorio q uniformemente entre 1 , 2 y 3 .$k$$q$$1$$2$$3$

• si , camina 2 k - 1 , espera $q = 1$$2^{k-1}$ , camina 2 k - $2^{k+1}$$2^{k-1}$
• si , espere 2 k - 1 , camine 2 k - 1 , espere 2 k , camine 2 k - 1 , espere 2 k - $q = 2$$2^{k-1}$$2^{k-1}$$2^{k}$$2^{k-1}$$2^{k-1}$
• si , espera 2 k , camina 2 k , espera 2 $q = 3$$2^k$$2^k$$2^k$

En cada paso , ambos amigos caminarán 2 k pasos. Si k < log 2 ( x ) + 1 , no se encontrarán durante ese paso, sin embargo, si k > = log $k$$2^k$$k < \log_2(x) + 1$ , se encontrarán si y solo si no sacan el mismo número. La probabilidad de que esto no sucede sólo es 1 / 3 en cada paso.$k >= \log_2(x) + 1$$1/3$

Por lo tanto, la distancia de caminata esperada es (acotada arriba por):

Lo cual es finito e igual, si se debe confiar en las matemáticas de mi servilleta, a .$2^{\lceil\log_2(x)\rceil+3}-2 \le 16x$

Por cierto, si es la variable aleatoria que representa la distancia recorrida, todavía tenemos que ∀ D > 0 , P ( d > D ) > 0 , es decir, la distancia no tiene límites y puede llegar a ser arbitrariamente alta. Afortunadamente, esta probabilidad desaparece lo suficientemente rápido como para garantizar que la suma infinita ∑ ∞ D = 0 P ( d = D ) ⋅ D = E [ d ] converja. Tener un límite superior finito para $d$$\forall D>0, \mathrm{P}(d>D) > 0$$\sum_{D=0}^{\infty}\mathrm{P}(d=D)\cdot D = \mathbb{E}[d]$$d$ es una propiedad mucho más fuerte y creo que no es posible encontrar una solución que la satisfaga.