13.11: Оптимальні стратегії

Last updated
Save as PDF

Page ID: 99312

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

$\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}}$

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

Визначення

Нагадаємо, що правило зупинки для червоного і чорного - продовжувати грати до тих пір, поки гравець не буде зруйнований або її стан не досягне цільового стану$a$. Таким чином, стратегія азартного гравця полягає в тому, щоб вирішити, скільки робити ставку на кожну гру, перш ніж вона повинна зупинитися. Припустимо, що у нас є клас стратегій, які відповідають певним дійсним фортунам і ставкам;$A$ буде позначати набір фортун і$B_x$ буде позначати набір дійсних ставок для$x \in A$. Наприклад, іноді (як у боязкій грі) ми можемо захотіти обмежити фортуни набором цілих чисел$\{0, 1, \ldots, a\}$; в інших випадках (як у сміливій грі) ми можемо використовувати інтервал$[0, 1]$ як простір фортуни. Що стосується ставок, нагадаємо, що гравець не може робити ставки на те, що у неї немає, і не буде ставити більше, ніж їй потрібно, щоб досягти мети. Таким чином, функція ставок$S$ повинна задовольняти\[ S(x) \le \min\{x, a - x\}, \quad x \in A \] Крім того, ми завжди обмежуємо наші стратегії тими, для яких час зупинки$N$ є кінцевим.

Функція успіху стратегії - це ймовірність того, що гравець досягає мети$a$ з цією стратегією, як функція початкового стану$x$. Стратегія з функцією успіху$V$ є оптимальною, якщо для будь-якої іншої стратегії з функцією успіху$U$, ми маємо$U(x) \le V(x)$ для$x \in A$.

Якщо існує оптимальна стратегія, то оптимальна функція успіху унікальна.

Однак оптимальної стратегії може не існувати або може бути кілька оптимальних стратегій. Більш того, питання оптимальності залежить від величини ймовірності виграшу в грі$p$, крім структури фортун і ставок.

Умова оптимальності

Наша основна теорема дає умову оптимальності:

Стратегія$S$ з функцією успіху$V$ є оптимальною, якщо\[ p V(x + y) + q V(x - y) \le V(x); \quad x \in A, \, y \in B_x \]

Доказ

Розглянемо наступну стратегію: якщо початковий стан є$x \in A$, ми вибираємо,$y \in A_x$ а потім робимо ставку$y$ на першу гру; після цього ми слідуємо стратегії$S$. Обумовивши результат першої гри, функція успіху для цієї нової стратегії є\[ U(x) = p\,V(x + y) + q\,V(x - y) \] Таким чином, теорему можна переоцінити наступним чином: Якщо$S$ оптимально щодо класу стратегій, щойно описаних, то$S$ є оптимальним для всіх стратегій. $T$Дозволяти довільна стратегія з функцією успіху$U$. Випадкову$V(X_n)$ величину можна інтерпретувати як ймовірність виграшу, якщо стратегія гемблера буде замінена стратегією$S$ за часом$n$. Умовлення на результат гри$n$ дає\[ \E[V(X_n) \mid X_0 = x] = \E[p \, V(X_{n-1} + Y_n) + q \, V(X_{n-1} - Y_n) \mid X_0 = x] \] Використання умови оптимальності дає\[ \E[V(X_n) \mid X_0 = x] \le \E[V(X_{n-1}) \mid X_0 = x] , \quad n \in \N_+, \; x \in A \] Якщо випливає, що$\E[V(X_n) \mid X_0 = x] \le V(x)$ для$n \in \N_+$ і$x \in A$. Тепер$N$ позначимо час зупинки для стратегії$T$. Допускаючи, що$n \to \infty$ ми маємо$\E[V(X_N) \mid X_0 = x] \le V(x)$ для$x \in A$. Але$\E[V(X_N) \mid X_0 = x] = U(x)$ для$x \in A$. Таким чином$U(x) \le V(x)$ для$x \in A$.

Вигідні випробування з мінімальною ставкою

Припустимо тепер, що$p \ge \frac{1}{2}$ так, щоб випробування були сприятливими (або хоча б не несправедливими) по відношенню до азартного гравця. Далі, припустимо, що всі ставки повинні бути кратними базової одиниці, яку ми могли б також припустити, що $1. Звичайно, справжні гральні будинки мають це обмеження. Таким чином, набір дійсних фортун є$A = \{0, 1, \ldots, a\}$ і набір дійсних ставок для$x \in A$ є$B_x = \{0, 1, \ldots, \min\{x, a - x\}\}$. Наш головний результат для цього випадку

Боязка гра - оптимальна стратегія.

Доказ

Згадайте функцію успіху$f$ для боязкої гри і згадайте умову оптимальності. Ця умова дотримується, якщо$p = \frac{1}{2}$. Якщо$p \gt \frac{1}{2}$, умова оптимальності еквівалентна\[ p \left(\frac{q}{p}\right)^{x+y} + q \left(\frac{q}{p}\right)^{x-y} \ge \left(\frac{q}{p}\right)^x \] Але ця умова еквівалентна$p q \left(p^y - q^y\right)\left(p^{y - 1} - q^{y - 1}\right) \le 0$ якій чітко тримає if$p \gt \frac{1}{2}$.

У червоно-чорній грі встановлюємо цільову фортуну на 16, початковий стан - 8, а ймовірність виграшу в грі до 0,45. Визначте стратегію на свій вибір і зіграйте 100 ігор. Порівняйте свою відносну частоту виграшів з ймовірністю виграшу з боязкою грою.

Вигідні випробування без мінімальної ставки

Ми зараз будемо вважати, що будинок допускає довільно невеликі ставки і те$p \gt \frac{1}{2}$, щоб випробування були строго сприятливими. В цьому випадку природно прийняти ціль в якості грошової одиниці, щоб набір фортун$A = [0, 1]$ був, а набір ставок на$x \in A$ є$B_x = [0, \min\{x, 1 - x\}]$. Наш основний результат для цього випадку наведено нижче. Результати для боязкої гри відіграють важливу роль в аналізі, тому ми дозволимо$f(j, a)$ позначити ймовірність досягнення цілої мети$a$, починаючи з цілого числа$j \in [0, a]$, з одиничними ставками.

Оптимальною функцією успіху є$V(x) = x$ для$x \in (0, 1]$.

Доказ

Виправте раціональний початковий стан$x = \frac{k}{n} \in [0, 1]$. $m$Дозволяти бути натуральне число і припустимо, що$x$, починаючи з, гравець робить ставку$\frac{1}{m n}$ на кожну гру. Ця стратегія еквівалентна боязкій грі з цільовою$m n$ фортуною та початковим станом$m k$. Звідси ймовірність досягнення мети 1 за цією стратегією є$f(m k, m n)$. Але$f(m k, m n) \to 1$ як$m \to \infty$. Звідси випливає$V(x) = x$, що$x \in (0, 1]$ це раціонально. Але$V$ збільшується так$V(x) = x$ для всіх$x \in (0, 1]$

Нечесні судові процеси

Ми зараз будемо вважати, що$p \le \frac{1}{2}$ так, щоб судові процеси були несправедливими, або, принаймні, не сприятливими. Як і раніше, ми візьмемо цільовий стан як основну грошову одиницю і допустимо будь-яку дійсну частку цієї одиниці як ставку. Таким чином, набір фортун є$A = [0, 1]$, а набір ставок на$x \in A$ є$B_x = [0, \min\{x, 1 - x\}]$. Наш головний результат для цього випадку

Смілива гра оптимальна.

Доказ

Нехай$F$ позначають функцію успіху для гри жирним шрифтом, і нехай\[ D(x, y) = F \left(\frac{x + y}{2}\right) - [p F(x) + q F(y)] \] умова оптимальності еквівалентна$D(x, y) \le 0$ for$0 \le x \le y \le 1$. З безперервності$F$, досить довести цю нерівність, коли$x$ і$y$ є бінарними раціональними. Це просто побачити, що$D(x, y) \le 0$ коли$x$ і$y$ мають ранг 0:$x = 0$,$y = 0$ або$x = 0$,$y = 1$ або$x = 1$,$y = 1$. Припустимо тепер, що$D(x, y) \le 0$ коли$x$ і$y$ мають ранг$m$ або менше. У нас є такі випадки:

Якщо$x \le y \le \frac{1}{2}$ тоді$D(x, y) = p D(2 x, 2 y)$.
Якщо$\frac{1}{2} \le x \le y$ тоді$D(x, y) = q D(2 x - 1, 2 y - 1)$.
Якщо$x \le \frac{x + y}{2} \le \frac{1}{2} \le y$ і$2 y - 1 \le 2 x$ тоді$D(x, y) = (q - p) F(2 y - 1) + q D(2 y - 1, 2 x)$.
Якщо$x \le \frac{x + y}{2} \le \frac{1}{2} \le y$ і$2 x \le 2 y - 1$ тоді$D(x, y) = (q - p) F(2 x) + q D(2 x, 2 y - 1)$.
Якщо$x \le \frac{1}{2} \le \frac{x + y}{2} \le y$ і$2 y - 1 \le 2 x$ тоді$D(x, y) = p (q - p) [1 - F(2 x)] + p D(2 y - 1, 2 x)$.
Якщо$x \le \frac{1}{2} \le \frac{x + y}{2} \le y$ і$2 x \le 2 y - 1$ тоді$D(x, y) = p (q - p) [1 - F(2 y - 1)] + p D(2 x, 2 y - 1)$.

Індукційна гіпотеза тепер може бути застосована до кожного випадку, щоб закінчити докази.

У червоно-чорній грі встановіть цільовий стан на 16, початковий стан - 8, а ймовірність виграшу в грі - 0,45. Визначте стратегію на свій вибір і зіграйте 100 ігор. Порівняйте свою відносну частоту виграшів з ймовірністю виграшу при сміливій грі.

Інші оптимальні стратегії у суб-справедливій справі

Розглянемо ще раз суб-чесну справу, де$p \le \frac{1}{2}$ так, щоб судові процеси не були сприятливими для азартного гравця. Ми покажемо, що смілива гра - не єдина оптимальна стратегія; дивно, що оптимальних стратегій нескінченно багато. Нагадаємо спочатку, що смілива стратегія має функцію ставок.\[ S_1(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}$: Функція ставок для сміливої гри

Розглянемо наступну стратегію, яку ми будемо називати сміливою стратегією другого порядку:

З$x \in \left(0, \frac{1}{2}\right)$ фортуною сміливо грайте з об'єктом досягнення$\frac{1}{2}$ до падіння до 0.
З$x \in \left(\frac{1}{2}, 1\right)$ фортуною сміливо грайте з об'єктом досягнення 1, не опускаючись нижче$\frac{1}{2}$.
З$\frac{1}{2}$ фортуною грайте сміливо і робіть ставку$\frac{1}{2}$

Смілива стратегія другого порядку має функцію ставок,$S_2$ задану\[ S_2(x) = \begin{cases} x, & 0 \le x \lt \frac{1}{4} \\ \frac{1}{2} - x, & \frac{1}{4} \le x \lt \frac{1}{2} \\ \frac{1}{2}, & x = \frac{1}{2} \\ x - \frac{1}{2}, & \frac{1}{2} \lt x \le \frac{3}{4} \\ 1 - x, & \frac{3}{4} \lt x \le 1 \end{cases} \]

Малюнок$\PageIndex{2}$: Функція ставок для жирної стратегії другого порядку

Смілива стратегія другого порядку оптимальна.

Доказ

Давайте$F_2$ позначимо функцію успіху, пов'язану зі стратегією$S_2$. Припустимо спочатку, що гравець починає з фортуни$x \in (0, \frac{1}{2})$ під стратегією$S_2$. Зверніть увагу, що гравець досягає мети 1 тоді і лише тоді, коли він досягне,$\frac{1}{2}$ а потім виграє фінальну гру. Розглянемо послідовність фортун, поки гравець не досягне 0 або$\frac{1}{2}$. Якщо ми подвоїмо фортуни, то у нас є послідовність фортуни за звичайною жирною стратегією, починаючи з$2\,x$ і закінчуючи або 0 або 1. Таким чином, випливає, що\[ F_2(x) = p F(2 x), \quad 0 \lt x \lt \frac{1}{2} \] припустимо наступне, що гравець починає з фортуни$x \in (\frac{1}{2}, 1)$ під стратегією$S_2$. Зверніть увагу, що гравець досягає мети 1 тоді і лише тоді, коли він досягає 1, не впадаючи назад$\frac{1}{2}$ або не падає назад,$\frac{1}{2}$ а потім виграє фінальну гру. Розглянемо послідовність фортун, поки гравець не досягне$\frac{1}{2}$ або 1. Якщо ми подвоїмо фортуни і віднімаємо 1, то у нас є послідовність фортуни за звичайною жирною стратегією, починаючи з$2 x - 1$ і закінчуючи або 0 або 1. Таким чином, випливає, що\[ F_2(x) = F(2 x - 1) + [1 - F(2 x - 2)] p = p + q F(2 x - 1), \quad \frac{1}{2} \lt x \lt 1 \] Але тепер, використовуючи функціональне рівняння для звичайної сміливої гри, ми маємо$F_2(x) = F(x)$ для всіх$x \in (0, 1]$, а значить і$S_2$ є оптимальним.

Як тільки ми зрозуміємо, як робиться ця конструкція, просто визначити сміливу стратегію третього порядку і показати, що вона також оптимальна.

Смілива стратегія третього порядку — Малюнок$\PageIndex{3}$: Функція ставок для жирної стратегії третього порядку

Явно дайте функцію ставок третього порядку і покажіть, що стратегія оптимальна.

У загальному плані ми можемо визначити$n$ жирну стратегію порядку і показати, що вона також оптимальна.

Послідовність жирних стратегій може бути визначена рекурсивно з базової жирної стратегії$S_1$ наступним чином:

\[ S_{n+1}(x) = \begin{cases} \frac{1}{2} S_n(2 x), & 0 \le x \lt \frac{1}{2} \\ \frac{1}{2}, & x = \frac{1}{2} \\ \frac{1}{2} S_n(2 x - 1), & \frac{1}{2} \lt x \le 1 \end{cases} \]

$S_n$оптимально для кожного$n$.

Ще більш загально, ми можемо визначити оптимальну стратегію$T$ наступним чином: для кожного$x \in [0, 1]$ виберіть$n_x \in \N_+$ і нехай$T(x) = S_{n_x}(x)$. На графіку нижче наведено кілька графіків сміливих стратегій. Для оптимальної стратегії$T$ нам просто потрібно вибрати, для кожного$x$ ставку на один з графіків.

Сміливі стратегії — Малюнок$\PageIndex{4}$: Сімейство сміливих стратегій

Мартінгалес

Повернемося до немасштабованої формулювання червоного і чорного, де цільовий стан$ a \in (0, \infty) $ і початковий стан$ x \in (0, a) $. У випадку субсправедливості, коли$ p \le \frac{1}{2} $, жодна стратегія не може зробити краще, ніж оптимальні стратегії, так що ймовірність виграшу обмежена$ x / a $ (з рівністю коли$ p = \frac{1}{2} $). Ще один елегантний доказ цього наведено в розділі про нерівності в главі про мартингалес.