Hilang dalam konser "satu arah"

Anda dan seorang teman kehilangan satu sama lain pada saat konser, dan tidak ada yang yakin Anda lebih maju. Secara formal, masing-masing berada pada koordinat bilangan bulat dan hanya dapat berjalan menuju koordinat yang lebih tinggi atau tetap di tempatnya.

Anggap Anda dan teman Anda mengikuti algoritma yang sama persis (dan tidak, Anda mungkin tidak mengatakan "jika (nama ==" R B ") melakukan sesuatu :)), dan jarak awal antara Anda berdua adalah (yang tidak diketahui oleh Anda).$x$

Apa algoritma yang meminimalkan jarak berjalan yang diharapkan sampai Anda dan teman Anda bertemu?

Anda mungkin menganggap teman dan diri Anda bergerak dalam kecepatan konstan yang sama.

Contoh algoritma sederhana adalah sesuatu seperti:

1. Pada tahap (mulai dari 0 ):$n$$0$

   • Jalan langkah ke kanan wp $3^n$ atau tunggu3nunit waktu jika tidak.$\frac{1}{2}$$3^n$

Untuk melihat algoritma ini membuat teman-teman bertemu dengan probabilitas 1 mempertimbangkan apa yang terjadi pada tahap . Bahkan jika teman yang x langkah maju selalu berjalan dan yang lain selalu tetap di tempatnya, jarak antara keduanya adalah: x + 1 + 3 + 9 + … + 3 log 3 x = 2 x + x - $(\log_3 x+1)$$x$

Oleh karena itu, di iterasi, teman yang memilih untuk berjalan kaki akan menutupi jarak 3 log 3 x + 1 = 3 x , maka dengan probabilitas $\log_3 x+1$$3^{\log_3 x+1}=3x$ , teman yang ada di belakang akan menyusul dan mereka akan bertemu.$\frac{1}{4}$

Optimalisasi sederhana (untuk mengurangi jarak berjalan) adalah, alih-alih berjalan langkah, berjalan c x langkah, di mana c diberikan oleh: 2 + $3^x$$c^x$$c$

Karenanya optimal untuk algoritma ini adalah c = 3 + $c$ $c=\frac{3+\sqrt 5}{2}\approx 2.618$

Sayangnya, meskipun algoritma ini menjamin bahwa teman-teman akan bertemu dengan probabilitas 1, jarak jalan kaki yang diharapkan tidak terbatas, yang merupakan sesuatu yang ingin saya hindari jika memungkinkan.

Apakah ada algoritma yang lebih efisien?

Pada langkah , gambar angka acak q secara seragam antara 1 , 2 , dan 3 .$k$$q$$1$$2$$3$

• jika , jalan 2 k - 1 , tunggu 2 k + 1 , jalan 2 k - $q = 1$$2^{k-1}$$2^{k+1}$$2^{k-1}$
• jika , tunggu 2 k - 1 , jalan 2 k - 1 , tunggu 2 k , jalan 2 k - 1 , tunggu 2 k - $q = 2$$2^{k-1}$$2^{k-1}$$2^{k}$$2^{k-1}$$2^{k-1}$
• jika , tunggu 2 k , jalan 2 k , tunggu 2 $q = 3$$2^k$$2^k$$2^k$

Pada setiap langkah , kedua teman akan berjalan langkah 2 k . Jika k < log 2 ( x ) + 1 , mereka tidak akan bertemu selama langkah itu, namun jika k > = log 2 ( x ) + 1 , mereka akan bertemu jika dan hanya jika mereka tidak menggambar angka yang sama. Probabilitas bahwa ini tidak terjadi hanya 1 / 3 pada setiap langkah.$k$$2^k$$k < \log_2(x) + 1$$k >= \log_2(x) + 1$$1/3$

Karenanya jarak jalan kaki yang diharapkan adalah (dibatasi di atas oleh):

Yang terbatas, dan sama, jika matematika serbet saya dapat dipercaya, untuk .$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$ adalah properti yang jauh lebih kuat dan saya rasa tidak mungkin menemukan solusi yang memuaskannya.