13.10: Смілива гра

\(\newcommand{\P}{\mathbb{P}}\)\(\newcommand{\E}{\mathbb{E}}\)\(\newcommand{\R}{\mathbb{R}}\)\(\newcommand{\N}{\mathbb{N}}\)\(\newcommand{\bs}{\boldsymbol}\)\(\newcommand{\var}{\text{var}}\)\(\newcommand{\sd}{\text{sd}}\)

Основна теорія

Попередні етапи

Нагадаємо, що при стратегії сміливої гри в червоному і чорному кольорі, гравець на кожну гру робить ставку або весь свій стан, або суму, необхідну для досягнення цільового стану, залежно від того, що менше. Як завжди, нас цікавить ймовірність того, що гравець досягне мети і очікувана кількість випробувань. Перший цікавий факт полягає в тому, що має значення лише відношення початкового стану до цільової фортуни, цілком на відміну від боязкої гри.

Припустимо, що азартний гравець сміливо грає з початковим фортуном\(x\) і цільовим фортуном\(a\). Як завжди, давайте\(\bs{X} = (X_1, X_2, \ldots)\) позначимо процес фортуни для азартного гравця. Для будь-якого\(c \gt 0\), випадковий процес\(c \bs{X} = (c X_0, c X_1, \ldots)\) - це процес фортуни для сміливої гри з початковою фортуною\(c x\) та цільовою фортуною\(c a\).

Через такого результату зручно використовувати цільовий стан в якості грошової одиниці і допускати ірраціональні, а також раціональні початкові фортуни. Таким чином, простір фортуни є\([0, 1]\). Іноді в нашому аналізі ми ігноруємо стани 0 або 1; очевидно, що в цьому немає ніякої шкоди, тому що в цих станах гра закінчена.

Нагадаємо, що функція ставок\(S\) - це функція, яка дає суму ставки як функцію поточного стану. Для сміливої гри функція ставок\[ S(x) = \min\{x, 1 - x\} = \begin{cases} x, & 0 \le x \le \frac{1}{2} \\ 1 - x, & \frac{1}{2} \le x \le 1 \end{cases} \]

Малюнок\(\PageIndex{1}\): Функція ставок для сміливої гри

Імовірність виграшу

Ми позначимо ймовірність того, що жирний гравець досягне мети,\(a = 1\) починаючи з початкового стану,\(x \in [0, 1]\) по\(F(x)\). За властивістю масштабування ймовірність того, що жирний гравець досягне якогось іншого цільового значення\(a \gt 0\), починаючи з,\(x \in [0, a]\) є\(F(x / a)\).

Функція\(F\) задовольняє наступним функціональним рівнянням і граничним умовам:

1. \(F(x) = \begin{cases} p F(2 x), & 0 \le x \le \frac{1}{2}\\ p + q F(2 x - 1), & \frac{1}{2} \le x \le 1 \end{cases}\)
2. \(F(0) = 0\),\(F(1) = 1\)

З попереднього результату, і трохи роздумів, повинно бути зрозуміло, що важливу роль відіграє наступна функція:

\(d\)Дозволяти функція,\([0, 1)\)\[ d(x) = 2 x - \lfloor 2 x \rfloor = \begin{cases} 2 x, & 0 \le x \lt \frac{1}{2} \\ 2 x - 1, & \frac{1}{2} \le x \lt 1 \end{cases} \] визначена на Функція\(d\) називається функцією подвоєння, мод 1, оскільки\(d(x)\) дає дробову частину\(2 x\).

Зверніть увагу, що до останньої ставки, яка закінчує гру (з гравцем зруйнованим або переможним), послідовні фортуни гравця слідують за ітераціями карти\(d\). Таким чином, смілива гра тісно пов'язана з динамічною системою, пов'язаною с\(d\).

Малюнок\(\PageIndex{2}\): Карта подвоєння, по модулю 1

Бінарні розширення

Одним із ключів нашого аналізу є представлення початкового стану у двійковій формі.

Двійкове розширення\(x \in [0, 1)\) є\[ x = \sum_{i=1}^\infty \frac{x_i}{2^i} \] де\(x_i \in \{0, 1\}\) для кожного\(i \in \N_+\). Це уявлення є унікальним, за винятком випадків, коли\(x\) є двійковим раціональним (іноді також називають діадичним раціональним), тобто число форми\(k / 2^n\) де\(n \in \N_+\) і\(k \in \{1, 3, \ldots, 2^n - 1\}\);\(n\) додатне ціле число називається рангом\(x\). Бінарні раціональності більш детально розглянуті в розділі про основи.

Для двійкового\(x\) раціонального рангу\(n\) ми будемо використовувати стандартне завершувальне представлення де\(x_n = 1\) і\(x_i = 0\) для\(i \gt n\). Ранг може бути розширений на всі числа в [0, 1) шляхом визначення рангу 0 бути 0 (0 також вважається двійковим раціональним) і шляхом визначення рангу двійкового ірраціонального бути\(\infty\). Позначимо ранг\(x\) по\(r(x)\).

Застосовується до двійкових послідовностей функція подвоєння\(d\) є оператором зсуву:

Для\(x \in [0, 1)\),\( [d(x)]_i = x_{i+1} \).

Смілива гра в червоному і чорному кольорі може бути елегантно описана, порівнявши біти початкового фортуни з ігровими бітами.

Припустимо, що азартний гравець починається з початкового стану\(x \in (0, 1)\). Гемблер в кінцевому підсумку досягає мети 1 тоді і тільки тоді, коли існує додатне ціле число\(k\) таке, що\(I_j = 1 - x_j\) для\(j \in \{1, 2, \ldots, k - 1\}\) і\(I_k = x_k\). Тобто, азартний гравець виграє, якщо і тільки тоді, коли гра біт узгоджується з відповідним бітом фортуни в перший раз, що біт 1.

Випадкова величина, біти якої є доповненням бітів фортуни, відіграватиме важливу роль у нашому аналізі. Таким чином, нехай

\[ W = \sum_{j=1}^\infty \frac{1 - I_j}{2^j} \]

Зверніть увагу, що\(W\) це чітко визначена випадкова величина, яка приймає значення в\([0, 1]\).

Припустимо, що азартний гравець починає з початкового фортуну\(x \in (0, 1)\). Тоді азартний гравець досягає мети 1 якщо і тільки тоді\(W \lt x\).

Доказ

Це випливає з попереднього результату.

\(W\)має безперервний розподіл. Тобто\(\P(W = x) = 0\) для будь-якого\(x \in [0, 1]\).

З попередніх двох результатів випливає, що\(F\) це просто функція розподілу\(W\). Зокрема,\(F\) є зростаючою функцією, а оскільки\(W\) має безперервний розподіл,\(F\) є безперервною функцією.

Функція успіху\(F\) є унікальним неперервним розв'язком функціонального рівняння вище.

Доказ

Індукція на ранг показує, що будь-які два рішення повинні узгоджуватися на бінарних раціональних. Але тоді будь-які два безперервних рішення повинні погодитися для всіх\(x \in [0, 1]\).

Якщо ввести трохи більше позначень, ми можемо дати приємний вираз для\(F(x)\), а пізніше для очікуваної кількості ігор\(G(x)\). Нехай\(p_0 = p\) і\(p_1 = q = 1 - p\).

Функцію ймовірності виграшу\(F\) можна виразити наступним чином:\[ F(x) = \sum_{n=1}^\infty p_{x_1} \cdots p_{x_{n-1}} p x_n \]

Зауважте, що\( p \cdot x_n \) в останньому виразі є правильним; це не помилка\( p_{x_n} \). Таким чином, в суму\( x_n = 1 \) включаються тільки терміни з.

\(F\)суворо збільшується на\([0, 1]\). Це означає, що розподіл\(W\) має підтримку\([0, 1]\); тобто немає підінтервалів,\([0, 1]\) що мають позитивну довжину, але 0 ймовірності.

Зокрема,

1. \(F\left(\frac{1}{8}\right) = p^3\)
2. \(F\left(\frac{2}{8}\right) = p^2\)
3. \(F\left(\frac{3}{8}\right) = p^2 + p^2 q\)
4. \(F\left(\frac{4}{8}\right) = p\)
5. \(F\left(\frac{5}{8}\right) = p + p^2 q\)
6. \(F\left(\frac{6}{8}\right) = p + p q\)
7. \(F\left(\frac{7}{8}\right) = p + p q + p q^2\)

Якщо\(p = \frac{1}{2}\) тоді\(F(x) = x\) для\(x \in [0, 1]\)

Доказ

Є два докази. Найпростішим доказом є зауваження, що\(x \mapsto x\) є безперервним і задовольняє функціональному рівнянню у функціональному рівнянні. Інший доказ може бути побудований за допомогою подання у\( F \) вигляді суми.

Таким чином, для\(p = \frac{1}{2}\) (справедливих випробувань) ймовірність того, що сміливий гравець досягає цільового стану,\(a\) починаючи з початкового стану\(x / a\),\(x\) є, як і для боязкого азартного гравця. Зауважте також, що випадкова величина\(W\) має рівномірний розподіл на\([0, 1]\). Коли\(p \ne \frac{1}{2}\), поширення\(W\) досить дивне. Щоб викладати результат лаконічно, вкажемо залежність міри\(\P\) ймовірності від параметра\(p \in (0, 1)\). Спочатку ми визначаємо\[ C_p = \left\{ x \in [0, 1]: \frac{1}{n} \sum_{i=1}^n (1 - x_i) \to p \text{ as } n \to \infty \right\} \] Таким чином,\(C_p\) це набір,\(x \in [0, 1]\) для якого відносна частота 0 в двійковому розширенні є\(p\).

Для виразних\(p, \, t \in (0, 1)\)

1. \(\P_p(W \in C_p) = 1\)
2. \(\P_p(W \in C_t) = 0\)

Доказ

Частина (а) випливає з сильного закону великих чисел. Частина (b) випливає з частини (а), оскільки\(C_p \cap C_t = \emptyset\).

Коли\(p \ne \frac{1}{2}\),\(W\) не має функції щільності ймовірності (щодо міри Лебега на [0, 1]), хоча\(W\) має безперервний розподіл.

Доказ

Доказ - протиріччя. Припустимо, що\(W\) має функцію щільності ймовірності\(f\). Потім\( 1 = \P_p(W \in C_p) = \int_{C_p} f(x) \, dx \). Але якщо\( p \ne \frac{1}{2} \),\( \int_{C_p} 1 \, dx = \P_{1/2}(W \in C_p) = 0 \). Тобто\(C_p\) має міру Лебега 0. Але потім\(\int_{C_p} f(x) \, dx = 0\), протиріччя.

Коли\(p \ne \frac{1}{2}\),\(F\) має похідну 0 майже в кожній точці\([0, 1]\), хоча вона строго збільшується.

Малюнок\(\PageIndex{3}\): Графіки\(F\) коли\(p = 0.5\)\(p = 0.4\), і\(p = 0.2\)

У червоно-чорному експерименті виберіть пункт «Відтворити жирним шрифтом». Змінюйте початковий стан, цільову фортуну та ймовірність виграшу в грі за допомогою смуг прокрутки та зверніть увагу, як змінюється ймовірність перемоги в грі. Зокрема, відзначимо, що ця ймовірність залежить тільки від\(x / a\). Тепер для різних значень параметрів запустіть експеримент 1000 разів і порівняйте функцію відносної частоти з функцією щільності ймовірності.

Очікувана кількість випробувань

Нехай\(G(x) = \E(N \mid X_0 = x)\)\(x \in [0, 1]\), очікувана кількість випробувань, починаючи з\(x\). Для будь-якого іншого цільового стану очікувана кількість випробувань\(a \gt 0\), починаючи з,\(x \in [0, a]\) є справедливою\(G(x / a)\).

\(G\)задовольняє наступним функціональним рівнянням і граничним умовам:

1. \(G(x) = \begin{cases} 1 + p G(2 x), & 0 \lt x \le \frac{1}{2} \\ 1 + q G(2 x - 1), & \frac{1}{2} \le x \lt 1 \end{cases}\)
2. \(G(0) = 0\),\(G(1) = 0\)

Доказ

Функціональне рівняння випливає з обумовлення результату першої гри.

Відзначимо, цікаво, що функціональне рівняння не задовольняється при\(x = 0\) або\(x = 1\). Як і раніше, ми можемо дати альтернативний аналіз, використовуючи двійкове представлення початкового стану\(x \in (0, 1)\).

Припустимо, що початковий стан азартного гравця є\(x \in (0, 1)\). Потім\(N = \min\{k \in \N_+: I_k = x_k \text{ or } k = r(x)\}\).

Доказ

Якщо\(x\) є двійковим раціональним, то\(N\) приймає значення у множині\(\{1, 2, \ldots, r(x)\}\). Гра триває до тих пір, поки номер гри не погодиться з рангом фортуни або біт гри не погодиться з відповідним бітом фортуни, залежно від того, що менше. У першому випадку передостаннє фортуна\(\frac{1}{2}\), єдина фортуна, для якої наступна гра завжди остаточна. Якщо\(x\) двійковий ірраціональний, то\(N\) приймає значення в\(\N_+\). Гра триває до тих пір, поки біт гри не погодиться з відповідним бітом фортуни.

Ми можемо дати явну формулу для очікуваної кількості випробувань\(G(x)\) в терміні двійкового подання\(x\). Згадаймо наші особливі позначення:\(p_0 = p\),\(p_1 = q = 1 - p\)

Припустимо, що\(x \in (0, 1)\). Тоді\[ G(x) = \sum_{n=0}^{r(x) - 1} p_{x_1} \ldots p_{x_n} \]

Зверніть увагу, що\(n = 0\) термін дорівнює 1, так як товар порожній. Сума має скінченну кількість членів, якщо\(x\) є двійковим раціональним, а сума має нескінченну кількість членів, якщо\(x\) є двійковим ірраціональним.

Зокрема,

1. \(G\left(\frac{1}{8}\right) = 1 + p + p^2\)
2. \(G\left(\frac{2}{8}\right) = 1 + p\)
3. \(G\left(\frac{3}{8}\right) = 1 + p + p q\)
4. \(G\left(\frac{4}{8}\right) = 1\)
5. \(G\left(\frac{5}{8}\right) = 1 + q + p q\)
6. \(G\left(\frac{6}{8}\right) = 1 + q\)
7. \(G\left(\frac{7}{8}\right) = 1 + q + q^2\)

Якщо\(p = \frac{1}{2}\) тоді

\[ G(x) = \begin{cases} 2 - \frac{1}{2^{r(x) - 1}}, & x \text{ is a binary rational} \\ 2, & x \text{ is a binary irrational} \end{cases} \]

Малюнок\(\PageIndex{4}\): Очікувана кількість ігор жирним шрифтом грати з чесними іграми

У червоно-чорному експерименті виберіть пункт «Відтворити жирним шрифтом». Змінюйте\(x\)\(a\), а за\(p\) допомогою смуг прокрутки і зверніть увагу, як змінюється очікувана кількість випробувань. Зокрема, зверніть увагу, що середнє значення залежить тільки від співвідношення\(x / a\). Для вибраних значень параметрів виконайте експеримент 1000 разів і порівняйте середнє значення вибірки з середнім розподілом.

Для фіксованого\(x\),\(G\) є безперервним як функція\(p\).

Однак, як функція початкового стану\(x\), для фіксованого\(p\), функція\(G\) дуже нерегулярна.

\(G\)є переривчастим у двійкових раціональних в\([0, 1]\) і безперервним у двійкових ірраціональних.