Игровые системы

Игрок с начальным капиталом $a$ играет до тех пор, пока его состояние не увеличится на $b$ единиц, или пока он не разорится. Предположим, что $\rho >1$. Вероятность успеха умножается на $1+\theta$, если его начальный капитал бесконечен вместо $a$. Покажите, что $0<\theta <\left(\rho^{a}-1\right)^{-1}< (a(\rho -1))^{-1}$; сопоставьте с Примером 7.3.

Как показано на с. 94, с вероятностью 1 игрок либо достигает своей цели $c$, либо разоряется. Для $p \neq q$ выведите это непосредственно из усиленного закона больших чисел. Выведите это (для всех $p$) с помощью леммы Бореля—Кантелли, исходя из того, что если игра никогда не заканчивается, то не может произойти $c$ последовательных +1.

$612 \uparrow$ Если $V_{n}$ — множество последовательностей длины $n$, состоящих из $\pm 1$, то функция $b_{n}$ в (7.9) отображает $V_{n-1}$ в $\left\{ 0,1\right\}$. Системой отбора называется последовательность таких отображений. Хотя систем отбора существует несчётно много, у скольких из них есть эффективное

*Эту тему можно пропустить ${ }^{\mathrm{t}}$ Однако для каждого $\epsilon$ существуют оптимальные стратегии, при которых ставка никогда не превышает $\epsilon$; см. Dubins Savage.

описание в смысле алгоритма или конечного набора инструкций, посредством которых представитель (возможно, машина) мог бы управлять системой от имени игрока? Анализ этого вопроса — предмет математической логики, но нетрудно видеть, что алгоритмов или конечных наборов правил, выражаемых в конечных алфавитах, может быть лишь счётное множество.

Пусть $Y_{1}^{(\sigma )}, Y_{2}^{(\sigma )}, \ldots$ — случайные величины из Теоремы 7.1 для конкретной системы $\sigma$, и пусть $C_{\sigma }$ — множество тех $\omega$, для которых каждый $k$-набор из $\pm 1$ ( $k$ произвольно) встречается в $Y_{1}^{(\sigma )}(\omega ), Y_{2}^{(\sigma )}(\omega ), \ldots$ с правильной асимптотической относительной частотой (в смысле Задачи 6.12). Пусть $C$ — пересечение $C_{\sigma }$ по всем эффективным системам отбора $\sigma$. Покажите, что $C$ принадлежит $\mathscr {F}$ ($\sigma$-алгебре в вероятностном пространстве $(\Omega , \mathscr {F}, P)$, на котором определены $X_{n}$) и что $\mathbb {P}\left(C\right)=1$. Последовательность $\left(X_{1}(\omega ), X_{2}(\omega ), \ldots \right)$ для $\omega$ из $C$ называется коллективом: подпоследовательность, выбранная любым из эффективных правил $\sigma$, содержит все $k$-наборы в правильных пропорциях

Пусть $D_{n}$ равно 1 или 0 в зависимости от того, $X_{2 n-1} \neq X_{2 n}$ или нет, и пусть $M_{k}$ — момент $k$-й единицы, то есть наименьшее $n$, для которого $\sum_{i=1}^{n} D_{i}=k$. Пусть $Z_{k}=X_{2 M_{i}}$. Иными словами, рассмотрим последовательные непересекающиеся пары $(X_{2 n-1}, X_{2 n})$, отбросим согласованные $(X_{2 n-1}=X_{2 n})$ пары и оставим второй элемент несогласованных $(X_{2 n-1} \neq X_{2 n})$ пар. Покажите, что этот процесс имитирует симметричную монету: $Z_{1}, Z_{2}, \ldots$ независимы и одинаково распределены, и $\mathbb {P}\left(Z_{k}=+1\right)=\mathbb {P}\left(Z_{k}=-1\right)=\frac{1}{2}$, каким бы ни было $p$. Следуйте доказательству Теоремы 7.1.

Предположим, что игрок с начальным состоянием 1 ставит долю $\theta (0<\theta <1)$ своего текущего состояния: $F_{0}=1$ и $W_{n}=\theta F_{n-1}$. Покажите, что $F_{n}=\Pi_{k=1}^{n}\left(1+\theta X_{k}\right)$, и, следовательно,

Покажите, что $F_{n} \rightarrow 0$ с вероятностью 1 в невыгодном для игрока (субсправедливом) случае.

В «удвоении» $W_{1}=1, W_{n}=2 W_{n-1}$, и правило состоит в том, чтобы остановиться после первого выигрыша. При любом положительном $p$ игра обязательно завершится. Здесь $F_{T}=F_{6}+1$, но, разумеется, для этого требуется бесконечный капитал. Если $F_{0}=2^{k}-1$ и $W_{n}$ не может превышать $F_{n-1}$, то вероятность $F_{\tau }=F_{0}+1$ в справедливой игре равна $1-2^{-k}$. Докажите это с помощью Теоремы 7.2, а также напрямую.

В стратегии «прогрессия и защип» ставка, изначально равная некоторому целому числу, увеличивается на 1 после проигрыша и уменьшается на 1 после выигрыша, а правило остановки — прекратить игру, если следующая ставка равна 0. Покажите, что игра обязательно завершится тогда и только тогда, когда $p \geq \frac{1}{2}$. Покажите, что $F_{\tau }=F_{0}+\frac{1}{2} W_{1}^{2}+\frac{1}{2}(\tau -1)$. Требуется бесконечный капитал.

Вот распространённый мартингал. Непосредственно перед $n$-м вращением колеса у игрока имеется набор $x_{1}, \ldots , x_{k}$ положительных чисел ( $k$ меняется вместе с $n)$. Он ставит $x_{1}+x_{k}$, или $x_{1}$ в случае $k=1$. Если он проигрывает, то на следующем шаге он использует набор $x_{1}, \ldots , x_{k}, x_{1}+x_{k}\left(x_{1}, x_{1}\right.$ в случае $\left.k=1\right)$. Если он выигрывает, то на следующем шаге он использует набор $x_{2}, \ldots , x_{k-1}$, если только $k$ не равно 1 или 2, — в этом случае он прекращает игру. Покажите, что игра обязательно завершится, если $p>\frac{1}{3}$, и что итоговый выигрыш равен сумме чисел в исходном наборе. И здесь снова требуется бесконечный капитал.

Предположим, что $W_{k}=1$, так что $F_{k}=F_{0}+S_{k}$. Предположим, что $p \geq q$ и $\tau$ — момент остановки, такой что $1 \leq \tau \leq n$ с вероятностью 1. Покажите, что $\mathbb {E}\left[F_{\tau }\right] \leq \mathbb {E}\left[F_{n}\right]$, причём равенство достигается при $p=q$. Проинтерпретируйте этот результат в терминах опциона на акцию, который должен быть исполнен не позднее момента $n$, где $F_{0}+S_{k}$ представляет собой цену акции в момент $k$.

Для заданной стратегии пусть $A_{n}^{*}$ — состояние противника игрока в момент $n$. Рассмотрим следующие условия на стратегию. (i) $W_{n}^{*} \leq F_{n-1}^{*}$; (ii) $W_{n}^{*} \leq A_{n-1}^{*}$; (iii) $F_{n}^{*}+A_{n}^{*}$ постоянно. Проинтерпретируйте каждое условие и покажите, что вместе они влекут ограниченность стратегии в смысле (7.24).

Покажите, что $F_{\tau }$ имеет бесконечную область значений, если $F_{0}=1, W_{n}=2^{-n}$, и $\tau$ — наименьшее $n$, для которого $X_{n}=+1$.

Пусть $u$ — вещественная функция на $[0,1], u(x)$ представляет полезность состояния $x$. Рассмотрим стратегии, ограниченные 1; см. (7.24). Пусть $Q_{\pi }\left(F_{0}\right)=\mathbb {E}\left[u\left(F_{\tau }\right)\right]$; это представляет собой ожидаемую полезность при стратегии $\pi$ для начального состояния $F_{0}$. Предположим, что для некоторой стратегии $\pi_{0}$

и что

Покажите, что $Q_{\pi }(x) \leq Q_{\pi_{0}}(x)$ для всех $x$ и всех стратегий $\pi$. Такая стратегия $\pi_{0}$ называется оптимальной. Теорема 7.3 представляет собой частный случай этого результата при $p \leq \frac{1}{2}$, когда роль $\pi_{0}$ играет смелая игра, а $u(x)=1$ или $u(x)=0$ в зависимости от того, $x=1$ или $x<1$.

Условие (7.34) означает, что игра по стратегии $\pi_{0}$ не хуже, чем отказ от игры вообще; (7.35) означает, что, хотя перспективы даже при стратегии $\pi_{0}$ в среднем становятся менее радужными с течением времени, лучше использовать $\pi_{0}$ сейчас, чем на один шаг применить какую-то другую стратегию, а затем перейти к $\pi_{0}$.

Функционального уравнения (7.30) и предположения об ограниченности $Q$ достаточно, чтобы полностью определить $Q$. Во-первых, $Q(0)$ и $Q(1)$ должны быть равны 0 и 1 соответственно, и, значит, выполнено (7.31). Пусть $T_{0} x=\frac{1}{2} x$ и $T_{1} x=\frac{1}{2} x+\frac{1}{2}$; пусть $f_{0} x=p x$ и $f_{1} x=p+q x$. Тогда $Q\left(T_{u_{1}} \cdots T_{u_{n}} x\right)=f_{u_{1}} \cdots f_{u_{n}} Q(x)$. Если двоичные разложения $x$ и $y$ оба начинаются с цифр $u_{1}, \ldots , u_{n}$, то они имеют вид $x=T_{u_{1}} \ldots T_{u_{n}} x^{\prime }$ и $y=T_{u_{1}} \cdots T_{u_{n}} y^{\prime }$. Если $K$ ограничивает $Q$ и $m=\max \left\{ p, q\right\}$, то отсюда следует, что $\left|Q(x)-Q(y)\right| \leq K m^{n}$. Следовательно, $Q$ непрерывна и удовлетворяет (7.31) и (7.33).