مساله ۷۱. بازی با اعداد تصادفی

مژگان این بازی رو انجام میده: یک عدد X داره که در ابتدا صفره. در هر مرحله دو گزینه داره: یا بازی رو با عدد X فعلی تموم کنه، یا اینکه یه عدد تصادفی بین صفر و یک به X اضافه کنه. اگه X از یک بیشتر بشه هم بازی تموم می‌شه.

اگه موقعی که بازی رو تموم می‌شه X کمتر از یک باشه، مژگان امتیاز نهایی X رو می‌گیره. در غیر اینصورت امتیاز نهایی صفر رو می‌گیره.

هدف مژگان اینه که طوری بازی کنه که امید ریاضی امتیاز نهاییش بیشینه بشه. یک استراتژی خوب (نه لزوما بهینه) برای مژگان پیشنهاد بدید و امید ریاضی بازی رو با این استراتژی حساب کنید.

لینک سوال در توویتر: https://x.com/Riazi_Cafe/status/1792437931619287340

اگر به محض اینکه امتیاز بیشتر از $\sqrt{2} - 1 \approx 0.4142$ ‎ شد بازی را تمام کنیم، امید ریاضی بازی تقریبا $0.6268$ خواهد شد.

فرض کنید امتیاز فعلی $q$ است و می‌خواهیم تصمیم بگیریم آیا افزودن یک عدد تصادفی دیگر به صرفه است یا نه. اگر عدد تصادفی شده بین $0$ و $1-q$ باشد، آنگاه امتیاز ما در مرحله‌ی بعد بیشتر از الان خواهد بود، وگرنه صفر خواهد شد. پس متوسط امتیاز با یک حرکت خواهد شد:

$$ \int_0^{1-q} (q + x) \cdot dx = \frac{1-q^2}{2} $$

و برای اینکه افزودن یک عدد تصادفی دیگر به صرفه باشد، باید این مقدار بیشتر از $q$ باشد. پس:

$$ \frac{1-q^2}{2} > q \implies q^2+2q-1 < 0 \implies q < \sqrt{2}-1 $$

پس استراتژی‌ای که انتخاب می‌کنیم این است که بلافاصله پس از اینکه X عدد $\sqrt{2} - 1$ را رد کرد بازی را تمام می‌کنیم (برای دقیقا $\sqrt{2} - 1$ امید ریاضی امتیاز در صورت ادامه دادن و ندادن برابر است. در ادامه فرض می‌کنیم در این حالت نیز بازی را ادامه می‌دهیم و عدد تصادفی جدید تولید می‌کنیم).

حال می‌خواهیم امیدریاضی امتیاز با استراتژی بالا وقتی از $x \le \sqrt{2} - 1‏$‎ شروع کنیم را حساب کنیم. این مقدار را با $f(x)$ نمایش می‌دهیم. در اینصورت ‏$‎\sqrt{2} - 1‏$‎ را رد نکرده‌ایم و باید عدد تصادفی تولید کنیم. با شروع از $x$ و تولید عدد تصادفی جدید، عددمان بطور یکنواخت به عدد جدید $t$ در بازه‌ی $[x, 1+x]$ افزایش خواهد یافت. سه حالت خواهیم داشت:

  • اگر مقدار جدید $t$ کمتر از یا مساوی با $\sqrt{2} - 1‏$‎ باشد، طبق استراتژی بالا باید بازی را ادامه دهیم پس در این حالت امیدریاضی امتیازمان با شروع از $t$ برابر با $f(t)$ خواهد شد.
  • اگر مقدار جدید $t$ بین $\sqrt{2} - 1$ و $1$ باشد، طبق استراتژی بالا بازی را تمام خواهیم کرد و امتیازمان $t$ خواهد شد.
  • اگر مقدار جدید $t$ بیشتر از $1$ باشد، بازی تمام خواهد شد و امتیازمان صفر خواهد شد.

پس می‌توانیم تابع $f(x)$ به شرط $x \le \sqrt{2} - 1‏$‎ را به صورت رابطه‌ی بازگشتی زیر بنویسیم:

$$ f(x) = \int_x^{\sqrt{2} - 1} f(t) \cdot dt + \int_{\sqrt{2} - 1}^1 t \cdot dt + \int_1^{1+x} 0 \cdot dt $$

که اگر از هر دو طرف مشتق بگیریم معادله‌ی دیفرانسیل $f'(x) + f(x) = 0‏$‎ بدست می‌آید. همچنین برای $x=\sqrt{2} - 1‏$‎ طول بازه‌ی انتگرال اول در رابطه‌ی بالا صفر خواهد شد و خواهیم داشت ‏$‎f(\sqrt{2} - 1) = \sqrt{2} - 1‏$.‎ با حل این معادله‌ی دیفرانسیل با شرط مرزی ‏$‎f(\sqrt{2} - 1) = \sqrt{2} - 1‏$ تابع $f$ زیر را بدست می‌آوریم:

$$ f(x) = \exp(-x + \log(\sqrt{2} - 1) + \sqrt{2} - 1) $$

و امید ریاضی بازی با شروع از امتیاز صفر برابر با $f(0) \simeq 0.6268‏$‎ است.