Perdido em um concerto "unidirecional"

Você e um amigo se perderam na fila para um concerto, e nenhum deles tem certeza de qual deles está mais à frente. Formalmente, cada um está em alguma coordenada inteira e só pode caminhar em direção a uma coordenada mais alta ou permanecer no local.

Supondo que você e seu amigo estejam seguindo exatamente o mesmo algoritmo (e não, você não pode dizer "if (name ==" R B ") faça algo :)), e a distância inicial entre vocês dois foi (que não é conhecido por você).$x$

Qual é o algoritmo que minimiza a curta distância esperada até você e seu amigo se encontrarem?

Você pode assumir que seu amigo e você estão se movendo na mesma velocidade constante.

Um exemplo de algoritmo simples seria algo como:

1. No estágio (a partir de ):$n$$0$

   • Ande etapas para a direita wp ou aguarde unidades de tempo.$3^n$ 3$\frac{1}{2}$$3^n$

Para ver esse algoritmo faz com que os amigos se encontrem com probabilidade 1, considere o que acontece no estágio . Mesmo que o amigo que estava passo à frente sempre andasse e o outro sempre estivesse no lugar, a distância entre os dois seria: x x + 1 + 3 + 9 + … + 3 log 3 x = 2 x + x - $(\log_3 x+1)$$x$

Portanto, na , o amigo que escolher andar percorrerá a distância de , portanto, com probabilidade , o amigo que está por trás alcançará e eles se encontrarão.3 log 3 x + 1 = 3 x $\log_3 x+1$$3^{\log_3 x+1}=3x$$\frac{1}{4}$

Uma otimização simples (para reduzir a distância a pé) seria, em vez de andar etapas, andar etapas, em que é dada por: c x c 2 + $3^x$$c^x$$c$

Portanto, o ideal para esse algoritmo é$c$ $c=\frac{3+\sqrt 5}{2}\approx 2.618$

Infelizmente, embora esse algoritmo garanta que os amigos encontrarão a probabilidade 1, a distância esperada é infinita, o que é algo que eu gostaria de evitar, se possível.

Existe um algoritmo mais eficiente?

Na etapa , desenhe um número aleatório q uniformemente entre 1 , 2 e 3 .$k$$q$$1$$2$$3$

• se , ande 2 k - 1 , espere 2 k + 1 , ande 2 k - $q = 1$$2^{k-1}$$2^{k+1}$$2^{k-1}$
• se , espere 2 k - 1 , ande 2 k - 1 , espere 2 k , ande 2 k - 1 , espere 2 k - $q = 2$$2^{k-1}$$2^{k-1}$$2^{k}$$2^{k-1}$$2^{k-1}$
• se , aguarde 2 k , caminhe 2 k , aguarde 2 $q = 3$$2^k$$2^k$$2^k$

A cada passo , os dois amigos andam 2 k passos. Se k < log 2 ( x ) + 1 , eles não se encontrarão durante essa etapa; no entanto, se k > = log 2 ( x ) + 1 , eles se encontrarão se e somente se não desenharem o mesmo número. A probabilidade de que isso não acontece apenas 1 / 3 em cada etapa.$k$$2^k$$k < \log_2(x) + 1$$k >= \log_2(x) + 1$$1/3$

Portanto, a distância a pé esperada é (delimitada acima por):

Qual é finito e igual, se minha matemática de guardanapo é confiável, para .$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$ é uma propriedade muito mais forte e acho que não é possível encontrar uma solução que a satisfaça.