Perdu dans un concert «unidirectionnel»

Vous et un ami vous êtes perdus sur la ligne à un concert, et vous ne savez pas lequel d'entre vous est plus avancé. Formellement, chacun a une coordonnée entière et ne peut marcher que vers une coordonnée plus élevée ou rester en place.

En supposant que vous et votre ami suivez exactement le même algorithme (et non, vous ne pouvez pas dire "si (nom ==" R B ") faites quelque chose :)), et la distance initiale entre vous deux était (ce qui n'est pas que vous connaissez).$x$

Quel est l'algorithme qui minimise la distance de marche attendue jusqu'à ce que vous et votre ami vous rencontriez?

Vous pouvez supposer que votre ami et vous-même évoluez à la même vitesse constante.

Un exemple d'algorithme simple serait quelque chose comme:

1. Au stade (à partir de 0 ):$n$$0$

   • Marcher pas à droite wp $3^n$ ou attendre3nunités de temps autrement.$\frac{1}{2}$$3^n$

Pour voir cet algorithme, les amis rencontrent la probabilité 1 de considérer ce qui se passe au stade . Même si l'ami qui était x en avance marchait toujours et que l'autre restait toujours en place, la distance entre les deux serait: x + 1 + 3 + 9 + … + 3 log 3 x = 2 x + x - $(\log_3 x+1)$$x$

Par conséquent, à l' itération , l'ami qui choisit de marcher couvrira une distance de 3 log 3 x + 1 = 3 x , donc avec probabilité $\log_3 x+1$$3^{\log_3 x+1}=3x$ , l'ami qui est derrière rattrapera son retard et se rencontrera.$\frac{1}{4}$

Une optimisation simple (pour réduire la distance de marche) serait, au lieu de marcher pas, marcher c $3^x$$c^x$ pas, où est donné par: 2 + $c$

D'où le c optimal$c$ pour cet algorithme est $c=\frac{3+\sqrt 5}{2}\approx 2.618$

Malheureusement, alors que cet algorithme garantit que les amis rencontreront la probabilité 1, la distance de marche attendue est infinie, ce que j'aimerais éviter si possible.

Existe-t-il un algorithme plus efficace?

À l'étape , tracez un nombre aléatoire q uniformément entre 1 , 2 et $k$$q$$1$$2$$3$ .

• si , marcher 2 k - 1 , attendre $q = 1$$2^{k-1}$ , marcher 2 $2^{k+1}$$2^{k-1}$
• si , attendre 2 k - 1 , marcher 2 k - 1 , attendre 2 k - marcher$q = 2$$2^{k-1}$$2^{k-1}$$2^{k}$ , attendez 2 k - $2^{k-1}$$2^{k-1}$
• si , attendez $q = 3$ , marcher 2 k , attendre 2 $2^k$$2^k$$2^k$

À chaque étape , les deux amis marcheront 2 k étapes. Si k < log 2 ( x ) + 1 , ils ne se rencontreront pas pendant cette étape, cependant si k > = log 2 ( x ) + 1 , ils se rencontreront si et seulement s'ils ne tirent pas le même nombre. La probabilité que cela ne se produise pas n'est que de 1 $k$$2^k$$k < \log_2(x) + 1$$k >= \log_2(x) + 1$ à chaque étape.$1/3$

Par conséquent, la distance de marche attendue est (délimitée ci-dessus par):

Ce qui est fini, et égal, si mes mathématiques de serviette sont fiables, à .$2^{\lceil\log_2(x)\rceil+3}-2 \le 16x$

Soit dit en passant, si est la variable aléatoire représentant la distance parcourue, nous avons toujours que ∀ D > 0 , P ( d > D ) > 0 , c'est-à-dire que la distance est illimitée et peut finir par être arbitrairement élevée. Heureusement, cette probabilité disparaît assez rapidement pour garantir que la somme infinie ∑ ∞ D = 0 P ( d = D ) ⋅ D = E [ d ] converge. Ayant une limite supérieure finie pour $d$$\forall D>0, \mathrm{P}(d>D) > 0$$\sum_{D=0}^{\infty}\mathrm{P}(d=D)\cdot D = \mathbb{E}[d]$$d$ est une propriété beaucoup plus solide et je pense qu'il n'est pas possible de trouver une solution satisfaisante.