Задача о разорении игрока

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Задача о разорении игрока — задача из области теории вероятностей. Подробно рассматривалась российским математиком А. Н. Ширяевым в монографии «Вероятность»[1].

Траектории справедливой игры длиною 1000 шагов; коридор блуждания частицы обозначен горизонтальными линиями.

Формулировка[править | править исходный текст]

За столом сидят два игрока. У первого в распоряжении находится -A\ (A<0, -A>0) рублей, у второго в распоряжении находится B\ (B>0) рублей. Перед ними на столе лежит асимметричная монета (вероятность, что выпадет аверс, может равняться любому числу от 0 до 1 включительно). Если на монете выпадает аверс, то рубль выигрывает первый игрок (второй игрок выплачивает первому 1 рубль), а если выпадает реверс, то первый игрок платит второму один рубль. Требуется найти вероятность того, что один из игроков проиграется в ноль за n\, шагов, и вероятность проигрыша каждого азартного игрока. Также необходимо вычислить среднюю длину игры.

Данная ситуация может быть смоделирована подобным образом: имеется блуждающая частица и коридор [A;B]. Рассматривается вероятность того, что частица выйдет из коридора за n шагов (проскочит через верхнюю или нижнюю стенку).

Схема Бернулли[править | править исходный текст]

Рассмотрим схему Бернулли с n испытаниями. Пусть (\Omega,\mathcal{A},\mathbb{P}) — вероятностное пространство, где \Omega = \bigl\{\omega\colon \omega=(x_1;\ldots;x_n),\ x_i = \pm 1 \bigr\}. \mathcal{A} = \{ A_i \subseteq \Omega \} — алгебра подмножеств вероятностного пространства. Вероятность задана следующим образом: \mathbb{P}\bigl(\{ \omega \}\bigr) = p^{\nu(\omega)}\cdot q^{n-\nu(\omega)}, где \nu(\omega) — количество выпавших в данной последовательность единиц: \nu(\omega) = \frac{\sum\limits_{i=1}^n x_i + n}{2}. Данная формула позволяет считать количество единиц: \nu(\omega) превращает соответственно полученные значения (+1;-1) в (1;0) и затем уже считает полученные единицы. Введём последовательность бернуллиевских случайных величин \xi_i(\omega)\colon i=\overline{1;n};\quad\mathbb{P}\bigl(\{\xi_i=1\}\bigr)=p;\quad\mathbb{P}\bigl(\{\xi_i=-1\}\bigr)=q;\quad p+q=1.

Подзадача о нормированности вероятности[править | править исходный текст]

Доказать, что \sum\limits_{\omega\in\Omega} \mathbb{P}\bigl(\{\omega\}\bigr) = 1.

Решение. \sum\limits_{\omega\in\Omega} \mathbb{P}\bigl(\{\omega\}\bigr) = \sum\limits_{\omega\in\Omega} p^{\frac{\sum\limits_{i=1}^n x_i + n}{2}} \cdot q^{n-\frac{\sum\limits_{i=1}^n x_i + n}{2}} = \sum\limits_{k=0}^n \sum\limits_{\omega\in A_k} p^{\frac{\sum\limits_{i=1}^n (x_i+1)}{2}} \cdot q^{\frac{\sum\limits_{i=1}^n (1-x_i)}{2}} = \sum\limits_{k=0}^n C^k_n p^k q^{n-k}. Это справедливо в силу того, что \frac{x_i+1}{2}\in \{ 0;1 \}. \sum\limits_{k=0}^n C^k_n p^k q^{n-k} = (p+q)^n = 1, поскольку по условию p+q=1. \blacksquare

Подзадача о независимости случайных величин \xi_i[править | править исходный текст]

Доказать, что \xi_1 и \xi_2 независимы.

Решение. Достаточно доказать, что \mathbb{P}\bigl(\{\xi_1=1\}\cap\{\xi_2=1\} \bigr)=\mathbb{P}\bigl( \{\xi_1=1\} \bigr)\mathbb{P} \bigl(\{\xi_2=1\} \bigr).

\mathbb{P}\bigl( \{\xi_1=1\}\cap\{\xi_2=1\} \bigr) = \mathbb{P} \bigl(\{ \omega\colon \omega=(x_1;\ldots;x_n),\ x_1=1,\ x_2=1 \} \bigr) =
=\sum\limits_{\begin{smallmatrix}x_3=\pm 1 \\ \ldots{} \\ x_n=\pm 1\end{smallmatrix}} p^{\frac{2+\sum\limits_{i=3}^n x_i + n}{2}}\cdot q^{n - \frac{2+\sum\limits_{i=3}^n x_i + n}{2}} =
p^2 \sum\limits_{\begin{smallmatrix}x_3=\pm 1 \\ \ldots{} \\ x_n=\pm 1\end{smallmatrix}} p^{\frac{\sum\limits_{i=3}^n x_i + (n-2)}{2}}\cdot q^{(n-2) - \frac{\sum\limits_{i=3}^n x_i + (n-2)}{2}} = p^2 \cdot 1. \blacksquare

Случайное блуждание[править | править исходный текст]

Введём новое обозначение: S_0 = 0, S_k = \xi_1 + \ldots{} + \xi_k, \quad 1\leqslant k \leqslant n. n — длина игры, а последовательность (S_k)_{k\leqslant n} можно рассматривать как траекторию случайного блуждания некоторой частицы, выходящей из нуля. При этом S_{k+1} = S_k + \xi_{k+1}. Пусть A, B — два целых числа, A\leqslant 0, B \geqslant 0. Требуется найти, с какой вероятностью за n шагов будет осуществлён выход частицы из коридора, ограниченного A и B. Если \xi_i = +1, то второй игрок платит первому. Если \xi_i = -1, то первый игрок платит второму. Поэтому S_k может рассматриваться в качестве выигрыша первого игрока у второго (который, естественно, может быть отрицательным). Далее, пусть x — целое число, x\in \mathbb{Z}\cap [A;B]. Пусть также для 0\leqslant k \leqslant n верно, что S^x_k = x+S_k (что означает, что игроки начинали играть с ненулевым капиталом в распоряжении). Пусть \tau^x_k = \min \bigl\{ l\colon 0\leqslant l \leqslant k, S^x_l = \{A \mathrm{~or~} B \} \bigr\}. Условимся считать, что \tau^x_k = k, если A < S_l^x < B\quad \forall l\colon 0\leqslant l \leqslant k. Если частица так и не пересекла границы, то x_k не определён.

Для каждого 0\leqslant k \leqslant n и x\in [A; B]\cap \mathbb{Z} момент \tau^x_k называется моментом остановки, который является случайной величиной, определённой на пространстве элементарных событий \Omega. \forall l<k\quad \{\omega\colon \tau^x_k = l\} — это событие, состоящее в том, что случайное блуждание \{S^x_i\colon 0\leqslant i \leqslant k \}, начинающееся в точке x, выйдет из интервала [A;B] в момент l. Введём новые обозначения: \mathcal{A}^x_k = \coprod\limits_{0\leqslant l \leqslant k}\{ \omega\colon \tau^x_k= l, \ S^x_l = A  \}, \mathcal{B}^x_k = \coprod\limits_{0\leqslant l \leqslant k}\{ \omega\colon \tau^x_k= l, \ S^x_l = B  \} для 0\leqslant k \leqslant n. Пусть \alpha_k(x) = \mathbb{P} (\mathcal{A}^x_k), \beta_k(x) = \mathbb{P} (\mathcal{B}^x_k) — вероятности выхода частицы за время [0;k] из интервала [A;B] соответственно в точках A и B.

Пусть A<x<B; очевидно, что \alpha_0(x) = \beta_0 (x) = 0 (пока игра не началась, частица находится внутри интервала с вероятностью 1). Пусть теперь 0\leqslant k \leqslant n. Тогда по формуле полной вероятности \beta_k (x) = \mathbb{P} (\mathcal{B}^x_k) = \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x+1 )\cdot \mathbb{P}\bigl(\{\xi_1 = 1 \}\bigr) + \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x-1 )\cdot \mathbb{P}\bigl(\{ \xi_1 = -1 \}\bigr).

Подзадача о рекуррентности[править | править исходный текст]

Доказать, что (1) \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x+1 ) = \mathbb{P} ( \mathcal{B}^{x+1}_{k-1} ) и (2) \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x-1 ) = \mathbb{P} ( \mathcal{B}^{x-1}_{k-1} ).

Доказательство.

(1) Докажем, что \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x+1 ) = \mathbb{P} ( \mathcal{B}^{x+1}_{k-1} ). \mathcal{B}^x_k = \bigl\{ \omega\colon (x;x+\xi_1;\ldots{};x+\xi_1+\ldots{}+\xi_k) \in B^x_k \bigr\}, где B^x_k — множество траекторий вида (x;x+x_1;\ldots{};x+x_1+\ldots{}+x_k),\quad x_i=\pm 1, которые за время [0;k] впервые выходят из интервала (A;B) в точке B (показано на рисунке). Если случайный вектор попадает в подходящую траекторию, то он попадает в множество \mathcal{B}. Представим множество B_k^x как B_k^{x;x+1}\sqcup B_k^{x;x-1}. Дизъюнктное объединение правомерно по причине того, что у любой частицы, проходящей по траектории, x_1=\pm 1. B_k^{x;x+1} — те траектории из B_k^x, для которых x_1=1. B_k^{x;x-1} — те траектории из B_k^x, для которых x_1=-1. Заметим, что каждая траектория (x;x+1;x+1+x_2;\ldots{};x+1+x_2+\ldots+x_k) из B_k^{x;x+1} находится в однозначном соответствии с траекторией (x+1;x+1+x_2;\ldots{};x+1+x_2+\ldots+x_k) из B_{k-1}^{x+1}. Взаимно-однозначное соответствие доказывается от противного. Предположим, что x_1 = -1 (неоднозначное соответствие); тогда данная траектория (x;x-1;x-1+x_2;\ldots;x-1+x_2+\ldots+x_k) не сможет вывести частицу из коридора за k шагов (а только лишь за k+2 из-за изначального отдаления от верхней стенки коридора). В обратную сторону соответствие является также однозначным из определения: S_{k+1} = S_k + \xi_{k+1}. Из этого следует, что \mathbb{P} \Bigl(\big\{ (x+1;x+1+x_2;\ldots; x+1+x_2+\ldots+x_k) \in B_{k-1}^{x+1} \bigr\} \Bigr) = \mathbb{P} \Bigl( \bigl\{ (x+1;x+1+x_1;\ldots; x+1+x_1+\ldots+x_{k-1}) \in B_{k-1}^{x+1} \bigr\} \Bigr) \mathrel{\stackrel{\rm def}=} \mathbb{P}(\mathcal{B}_{k-1}^{x+1}) (так как \xi_i суть независимые одинаково распределённые случайные величины).

Существует и другой способ доказательства:

\mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x+1 ) = \mathbb{P} ( \mathcal{B}^x_k \mid \xi_1 = 1 ) = \mathbb{P} \bigl( (x;x+\xi_1;\ldots{};x+\xi_1+\ldots{}+\xi_k)\in B^x_k \mid \xi_1 = 1 \bigr) =
=\frac{\mathbb{P} \bigl( (x;x+\xi_1;\ldots{};x+\xi_1+\ldots{}+\xi_k)\in B^x_k \cap \xi_1 = 1 \bigr)}{\mathbb{P}(\{ \xi_1 = 1 \})} = \frac{\mathbb{P} \bigl( (x;x+1;\ldots{};x+1+\ldots{}+\xi_k)\in B^x_k \cap \xi_1 = 1 \bigr)}{\mathbb{P}(\{ \xi_1 = 1 \})} =
=\mathbb{P}\bigl( \{ (x;x+1;x+1+\xi_2;\ldots{};x+1+\xi_2+\ldots{}+\xi_k)\in B_k^x \} \bigr) = \mathbb{P}\bigl( \{ (x;x+1;x+1+\xi_1;\ldots{};x+1+\xi_1+\ldots{}+\xi_{k-1})\in B_k^x \} \bigr) =
=\mathbb{P}\bigl( \{ (x;x+1;x+1+\xi_1;\ldots{};x+1+\xi_1+\ldots{}+\xi_{k-1})\in B_{k-1}^{x+1} \} \bigr) =
\mathbb{P} (\mathcal{B}_{k-1}^{x+1}) = \beta_{k-1}(x+1).

Это справедливо потому, что вероятности независимы (это было доказано ранее).

(2) Аналогично докажем, что \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x-1 ) = \mathbb{P} ( \mathcal{B}^{x+1}_{k-1} ). Каждая траектория (x;x-1;x-1+x_2;\ldots{};x-1+x_2+\ldots+x_k) из B_k^{x;x+1} находится в однозначном соответствии с траекторией (x-1;x-1+x_2;\ldots{};x-1+x_2+\ldots+x_k) из B_{k-1}^{x-1}. Отсюда \mathbb{P} \Bigl( \bigl\{ (x-1;x-1+x_2;\ldots; x-1+x_2+\ldots+x_k) \in B_{k-1}^{x-1} \bigr\} \Bigr) = \mathbb{P} \Bigl( \bigl\{ (x-1;x-1+x_1;\ldots; x-1+x_1+\ldots+x_{k-1}) \in B_{k-1}^{x-1} \bigr\} \Bigr) \mathrel{\stackrel{\rm def}=} \mathbb{P}(\mathcal{B}_{k-1}^{x-1}). \blacksquare

Вывод рекуррентного соотношения[править | править исходный текст]

Из уравнения для \beta_k(x) следует, что для x\in (A;B) и k\leqslant n верно: \mathbb{P}(\mathcal{B}_k^x) =
\mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x+1 )\cdot p + \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x-1 )\cdot q =
\mathbb{P} ( \mathcal{B}^{x+1}_{k-1}) \cdot p + \mathbb{P} ( \mathcal{B}^{x-1}_{k-1})\cdot q =
p\beta_{k-1}(x+1) + q\beta_{k-1}(x-1).

\beta_l(B)= 1, \beta_l(A)=0 для l\in[0;n]. Формула полной вероятности также даёт нам следующий результат: \alpha_k(x) = p\alpha_{k-1}(x+1) + q\alpha_{k-1}(x-1). Также отметим, что \mathcal{B}_{k-1} \subset \mathcal{B}_{k}, и поэтому \beta_{k-1}(x)\leqslant \beta_k(x)\leqslant 1 для k \leqslant n. Это утверждение верно, так как к любой траектории, выводящей частицу за меньшее количество шагов, можно прибавить в начало один шаг (x_{j-1}=\pm 1), на котором частица может прийти в точку (j;S^x_{j}) как из (j-1;S^x_{j}-1) (для \xi_j=1), так и из (j-1;S^x_{j}+1) (j\leqslant k).

Нахождение вероятностей[править | править исходный текст]

При достаточно больших n вероятность \beta_n (x) близка к \beta(x) — решению уравнения \beta(x) = p\beta(x+1) + q\beta(x-1) при тех условиях, что \beta(B)=1 (выход произошёл сразу же из точки B — конец игры, выиграл первый игрок), \beta(A)=0 (первый игрок никогда не выиграет, если выход произойдёт мгновенно в точке A). Эти условия следуют из того, что \lim\limits_{l\rightarrow\infty} \beta_l(B) = \beta(B). Это также будет доказано в этом разделе.

Сначала получим решение уравнения \beta(x) = p\beta(x+1) + q\beta(x-1). Пусть игра несправедливая (p\ne q). В таком случае найдём корни уравнения, то есть \beta(x). Одно частное решение видно сразу: \beta(x) = \mathrm{const} = a. Другое решение найдём, воспользовавшись тем, что \beta(x) — функция. Целесообразно употребить выражение с отношением \frac{q}{p}, учитывая, что p+q=1: \left( \frac{q}{p} \right)^x = \frac{q^x(p+q)}{p^x} = \frac{q^x}{p^{x-1}} + \frac{q^{x+1}}{p^x} = p\frac{q^{x+1}}{p^{x+1}} + q\frac{q^{x-1}}{p^{x-1}} = p\left(\frac{q}{p}\right)^{x+1} + q\left(\frac{q}{p}\right)^{x-1}. Отсюда правомерно предположить, что \beta(x) = b\cdot \left(\frac{q}{p}\right)^x. Добавление константы ничего не изменит благодаря тому, что p+q=1.

Теперь рассмотрим общее решение: \beta(x) = a + b\left(\frac{q}{p}\right)^x. Воспользуемся теми условиями, что \beta(A) = a+b\left(\frac{q}{p}\right)^A=0 и \beta(B) = a+b\left(\frac{q}{p}\right)^B=1, и получим, что \beta(x) = \frac{\beta(x)-0}{1-0} = \frac{\beta(x)-\beta(A)}{\beta(B)-\beta(A)} = \frac{a + b\left( \frac{q}{p}\right)^{x} - \left( a + b\left( \frac{q}{p}\right)^{A} \right)}{a + b\left( \frac{q}{p}\right)^{B} - \left( a + b\left( \frac{q}{p}\right)^{A} \right)} = \frac{\left( \frac{q}{p}\right)^{x}-\left( \frac{q}{p}\right)^{A}}{\left( \frac{q}{p}\right)^{B}-\left( \frac{q}{p}\right)^{A}}.

Подзадача о единственности решения[править | править исходный текст]

Докажем единственность решения данной задачи. Для этого покажем, что любое решение задачи \beta(x) = p\beta(x+1) + q\beta(x-1) с граничными условиями может быть представлено в виде \frac{\left( \frac{q}{p}\right)^{x}-\left( \frac{q}{p}\right)^{A}}{\left( \frac{q}{p}\right)^{B}-\left( \frac{q}{p}\right)^{A}}.

Решение. Рассмотрим некоторое решение \check \beta(x) при условиях \check\beta (A)=0, \check\beta(B)=1. Тогда всегда можно подобрать такие константы \check a и \check b, что \check a + \check b \left( \frac{q}{p}\right)^{A} = \check\beta(A), \check a + \check b\left( \frac{q}{p}\right)^{A+1} = \check \beta(A+1). Тогда из уравнения поставленной задачи следует, что \check\beta(A+2) = \check a + \check b \left( \frac{q}{p}\right)^{A+2}. Тогда в общем случае \check \beta(x) = \check a + \check b\left( \frac{q}{p}\right)^{x}. Следовательно, решение \frac{\left( \frac{q}{p}\right)^{x}-\left( \frac{q}{p}\right)^{A}}{\left( \frac{q}{p}\right)^{B}-\left( \frac{q}{p}\right)^{A}} является единственным. Точно такой же ход рассуждений может быть применён и к \alpha(x). \blacksquare

Предельная сходимость[править | править исходный текст]

Рассмотрим вопрос о быстроте предельной сходимости \alpha_n(x) и \beta_n(x) к \alpha(x) и \beta(x). Пусть блуждание начинается из начала координат (x=0). Для простоты обозначим \alpha_n(0)=\alpha_n, \beta_n(0)=\beta_n, \gamma_n = 1-\alpha_n-\beta_n. Иными словами, \gamma_n — это единица минус сумма вероятностей выхода частицы из коридора — вероятность того, что она останется блуждать в коридоре: \gamma_n = \mathbb{P} \{ \omega\colon A<S_k<B; 0\leqslant k \leqslant n \}. \omega представляет собой событие \bigcap\limits_{0\leqslant k \leqslant n} \{ A<S_k<B \}. Рассмотрим число n=rm, где r,m\in \mathbb{Z}, и цепочку случайных величин \zeta_n\colon \zeta_1 = \sum\limits_{i=1}^m \xi_i,~\zeta_2 = \sum\limits_{i=m+1}^{2m} \xi_i,~\ldots{},~\zeta_r = \sum\limits_{i=m(r-1)}^{rm} \xi_i. Если обозначить совокупное богатство за C = |A| +B, то тогда \{A<S_k<B;1\leqslant k \leqslant rm \} \subseteq \bigl\{|\zeta_1|<C;\ldots{};|\zeta_r|<C\bigr\}. Этому есть разумное объяснение: если частица выходит из нуля и не пересекает границ, то тогда совершенно определённо сумма m штук x_i меньше, чем совокупный запас.

Подзадача о независимости случайных величин \zeta_i[править | править исходный текст]

Докажем, что \zeta_j независимы и одинаково распределённые. Достаточно доказать, что они независимы, так как все они имеют биномиальное распределение.

Решение. Докажем, что \mathbb{P}\bigl(\{ \zeta_1=m \} \cap \{ \zeta_2=m \} \bigr) = \mathbb{P} \bigl( \{\zeta_1=m\}\bigr) \cdot \mathbb{P}\bigl( \{\zeta_2=m\}\bigr).

\mathbb{P}\bigl(\{ \zeta_1=m \} \cap \{ \zeta_2=m \} \bigr) = \mathbb{P} \left( \left\{ \sum\limits_{i=1}^{m} \xi_i = m \right\} \cap \left\{ \sum\limits_{i=m+1}^{2m} \xi_i = m \right\} \right) =
=\mathbb{P}\bigl(  \{ \xi_{1;\ldots;m} = 1 \} \cap \{ \xi_{m+1;\ldots;2m} = 1\}  \bigr) = \mathbb{P}^{2m}\bigl( \{\xi_i=1\}\bigr) = \mathbb{P} \bigl(\{\zeta_1=m\}\bigr) \cdot \mathbb{P} \bigl(\{\zeta_2=m\}\bigr). \blacksquare

Вернёмся к рассмотрению сходимости. \gamma_n \leqslant \mathbb{P} \Bigl( \bigl\{ |\zeta_1|;\ldots;|\zeta_r|<C\bigr\} \Bigr) = \prod\limits_{i=1}^r \mathbb{P} \Bigl( \bigl\{ |\zeta_i|<C \bigr\} \Bigr) = \biggl( \mathbb{P} \Bigl( \bigl\{ |\zeta_1|<C \bigr\} \Bigr) \biggr)^r, что следует из только что доказанного. Рассмотрим дисперсию: \mathrm{Var}(\zeta_1) = m\bigl(1-(p-q)^2\bigr) (что вполне правомерно, так как 1-(p-q)^2 =1-\bigl((p+q)^2-4pq\bigr), а \xi — модифицированная бернуллиевская случайная величина), поэтому для достаточно больших m и 0<p<1 верно: \mathbb{P}\Bigl( \bigl\{ |\zeta_1|<C\bigr\} \Bigr) \leqslant \varepsilon_1, где \varepsilon_1<1, так как если \mathbb{P}\Bigl( \bigl\{ |\zeta_1|\leqslant C \bigr\} \Bigr)=1, то \mathrm{Var}(\zeta_1)\leqslant C^2. Если p=0 или p=1, то для довольно больших m верно, что \mathbb{P}\Bigl( \bigl\{ |\zeta_1|<C \bigr\} \Bigr)=0, поэтому неравенство \mathbb{P}\Bigl( \bigl\{ |\zeta_1|<C \bigr\} \Bigr) \leqslant \varepsilon_1 верно \forall p\in[0;1]. Из вышесказанного следует, что \gamma_n \leqslant \varepsilon^n, где \varepsilon = \varepsilon_1^{\frac{1}{m}}<1. Так как \alpha+\beta = 1, то (\alpha-\alpha_n)-(\beta-\beta_n)=\gamma_n; так как \alpha\geqslant \alpha_n и \beta\geqslant \beta_n, то 0\leqslant \alpha-\alpha_n \leqslant \gamma_n \leqslant \varepsilon^n; 0\leqslant \beta-\beta_n \leqslant \gamma_n \leqslant \varepsilon^n при \varepsilon<1. Аналогичные оценки справедливы и для разностей \alpha(x)-\alpha_n(x) и \beta(x)-\beta_n(x), так как можно свести эти разности к разностям \alpha-\alpha_n и \beta-\beta_n при A_1 = A-x, B_1=B-x.

Вернёмся к рассмотрению \alpha(x). По аналогии с решением \frac{\left( \frac{q}{p}\right)^{x}-\left( \frac{q}{p}\right)^{A}}{\left( \frac{q}{p}\right)^{B}-\left( \frac{q}{p}\right)^{A}} уравнения \beta(x) = p\beta(x+1) + q\beta(x-1), можно сказать, что у уравнения \alpha(x) = p\alpha(x+1) + q\alpha(x-1) при граничных условиях \alpha(A)=1, \alpha(B)=0 существует единственное решение \alpha(x) =  \frac{\left( \frac{q}{p}\right)^{B}-\left( \frac{q}{p}\right)^{x}}{\left( \frac{q}{p}\right)^{B}-\left( \frac{q}{p}\right)^{A}},\qquad A\leqslant x \leqslant B.

Нетрудно заметить, что \alpha(x) + \beta(x) = \frac{\left( \frac{q}{p}\right)^{B}-\left( \frac{q}{p}\right)^{x}}{\left( \frac{q}{p}\right)^{B}-\left( \frac{q}{p}\right)^{A}} +  \frac{\left( \frac{q}{p}\right)^{x}-\left( \frac{q}{p}\right)^{A}}{\left( \frac{q}{p}\right)^{B}-\left( \frac{q}{p}\right)^{A}}  = \frac{\left( \frac{q}{p}\right)^{B}-\left( \frac{q}{p}\right)^{A}}{\left( \frac{q}{p}\right)^{B}-\left( \frac{q}{p}\right)^{A}}=1 при любых p\in [0;1]. Если же игра является справедливой (вероятность выпадения аверса равна вероятности выпадения реверса), то решения будут выглядеть следующим образом: \beta(x) = \frac{x-A}{B-A}, \alpha(x) = \frac{B-x}{B-A}.

Ответ о вероятности разорения[править | править исходный текст]

Величины \alpha(x) и \beta(x) было бы можно назвать вероятностями разорения первого и второго игрока при начальных капиталах x-A и x-B при стремлении количества ходов к бесконечности и характеризации случайной величина \xi_i=+1 как выигрыша первого игрока, а \xi_i=-1 — проигрыша первого игрока. В дальнейшем будет показано, почему такую последовательность действительно можно построить.

Если A=0, то интуитивный смысл функции \beta(x) — это вероятность того, что частица, вышедшая из положения x, достигнет верхней стенки (B) ранее, чем нуля. Из формул \beta (x) видно, что \beta(x) = \begin{cases} \frac{x}{B}, & p=q=0{,}5,\\ \frac{\left( \frac{q}{p}\right)^{x}-1}{\left( \frac{q}{p}\right)^{B}-1}, & p\ne q \end{cases}.

Парадокс увеличения ставки при неблагоприятной игре[править | править исходный текст]

Что необходимо сделать первому игроку, если игра неблагоприятна для него?

Его вероятность проигрыша задана формулой \lim\limits_{k\rightarrow\infty} \alpha_k = \alpha = \frac{\left( \frac{q}{p}\right)^{B}-1}{\left( \frac{q}{p}\right)^{B}-\left( \frac{q}{p}\right)^{A}}. Теперь пусть первый игрок с капиталом (-A) примет решение удвоить ставку и играть на два рубля. Теперь \mathbb{P}\bigl( \{\xi_i=2\}\bigr)=p, \mathbb{P}\bigl( \{\xi_i=-2\}\bigr)=q. Тогда обозначим предельную вероятность разорения первого игрока так: \alpha_2. Тогда \alpha_2 = \frac{\left( \frac{q}{p}\right)^{0{,}5B}-1}{\left( \frac{q}{p}\right)^{0{,}5B}-\left( \frac{q}{p}\right)^{0{,}5A}}. Поэтому \alpha = \frac{\left( \frac{q}{p}\right)^{0{,}5B\cdot2} - 1^2}{ \left( \frac{q}{p}\right)^{0{,}5B\cdot2} - \left( \frac{q}{p}\right)^{0{,}5A\cdot2} } =
\frac{\left( \left( \frac{q}{p}\right)^{0{,}5B}-1\right)\cdot \left( \left( \frac{q}{p}\right)^{0{,}5B}+1\right)}{\left( \left( \frac{q}{p}\right)^{0{,}5B}-\left( \frac{q}{p}\right)^{0{,}5A}\right) \cdot \left( \left( \frac{q}{p}\right)^{0{,}5B}+\left( \frac{q}{p}\right)^{0{,}5A}\right)} = \alpha_2 \cdot \frac{\left( \left( \frac{q}{p}\right)^{0{,}5B}+1\right)}{\left( \left( \frac{q}{p}\right)^{0{,}5B}+\left( \frac{q}{p}\right)^{0{,}5A}\right)} > \alpha_2, так как \alpha_2 умножается на дробь, которая больше единицы при q>p.

Поэтому если вероятность выпадения столь желанного для первого игрока аверса меньше 0{,}5, то ему выгодно увеличить ставку в r>1 раз: это уменьшает вероятность его терминального разорения за счёт того, что вырастает вероятность выскочить из коридора в точке B. Это решение кажется парадоксальным, так как складывается впечатление, что при неблагоприятной ситуации надо снизить ставку и уменьшить проигрыш, но в действительности при бесконечном числе игр и низкой ставке проигрывающий игрок в конечном счёте обязательно проиграется в ноль, а игрок с высокой ставкой обладает большими шансами выпадения количества аверсов, достаточного для завершения игры в точке B.

Длительность случайного блуждания[править | править исходный текст]

Рассмотрим среднюю длительность блуждания нашей частицы. Введём математическое ожидание момента, когда игра прекращается: \mathbb{E}(\tau^x_k)= m_k(x) для k\leqslant n. Выведем рекуррентное соотношение для математического ожидания продолжительности игры:

m_k(x) = \mathbb{E}(\tau_k^x) = \sum\limits_{1\leqslant l \leqslant k} l\mathbb{P} \bigl( \{\tau_k^x = l\} \bigr) = \sum\limits_{1\leqslant l \leqslant k} l \Bigl( p\mathbb{P}\bigl(\{ \tau_k^x = l \} \big| \{ \xi_1=1 \}\bigr) + q\mathbb{P}\bigl(\{ \tau_k^x = l \} \big| \{ \xi_1=-1 \}\bigr) \Bigr) =
= 
\sum\limits_{1\leqslant l \leqslant k} l \Bigl( p\mathbb{P}\bigl( \{ \tau_{k-1}^{x+1} = l-1 \}\bigr) + q\mathbb{P}\bigl\{ \tau_{k-1}^{x-1} = l-1 \}\bigr) \Bigr) = \sum\limits_{0\leqslant l \leqslant k-1} (l+1) \Bigl( p\mathbb{P}\bigl( \{ \tau_{k-1}^{x+1} = l\}\bigr) + q\mathbb{P}\bigl(\{ \tau_{k-1}^{x-1} = l \}\bigr) \Bigr) =
=  pm_{k-1}(x+1) + qm_{k-1}(x-1) + \sum\limits_{0\leqslant l \leqslant k-1} \Bigl( p\mathbb{P}\bigl( \{ \tau_{k-1}^{x+1} = l\}\bigr) + q\mathbb{P}\bigl(\{ \tau_{k-1}^{x-1} = l \}\bigr) \Bigr) = pm_{k-1}(x+1) + qm_{k-1}(x-1) + 1.

Для x\in (A;B) и k\in[0;n] мы получили рекуррентное соотношение для функции m_k(x): m_k(x) = pm_{k-1}(x+1) + qm_{k-1}(x-1) + 1 при m_0(x)=0. Введём граничные условия: если игра начинается в точке A или B, то тогда она тут же и завершится — её длительность будет равна 0: m_k(A) = m_k(B)=0. Из рекуррентного соотношения и граничных условий можно один за другим вычислить m_i(x). Так как m_{k+1}(x) \geqslant m_k(x), то существует предел m(x) = \lim\limits_{n\rightarrow\infty} m_n(x), который удовлетворяет соотношению m_k(x) = pm_{k-1}(x+1) + qm_{k-1}(x-1) + 1: m(x) = 1+pm(x+1) + qm(x-1) при выполнении m(A)=m(B)=0. Данные переходы аналогичны тем, что мы рассмотрели при переходе к n\rightarrow\infty в уравнении вероятности проигрыша. Для того чтобы решить данное уравнение, надо ввести ещё одно условие: матожидание количества ходов должно быть конечным, то есть m(x)<\infty, x\in(A;B).

Решим данное уравнение. В уравнении вероятности проигрыша (p\ne q) уже были получены частные решения a и b\left( \frac{q}{p}\right)^{x}. Здесь же появляется ещё один претендент на роль частного решения: \frac{x}{q-p} =\frac{q-p+(p+q)x + p-q}{q-p} = \frac{q-p}{q-p} + \frac{p(x+1)}{q-p} + \frac{q(x-1)}{q-p} = 1 + p\frac{x+1}{q-p} + q\frac{x-1}{q-p}, поэтому m(x) = \frac{x}{q-p} + a + b\left( \frac{q}{p}\right)^{x}. С учётом граничного условия m(A)=m(B)=0 находим при помощи ранее полученных соотношений m(x): m(x) = \frac{1}{p-q}\bigl( B\beta(x) + A\alpha(x) - x\bigr). В случае идеальной монетки получаем следующее выражение: m(x) = a+bx-x^2. Применение граничного условия даёт: m(x)= (B-x)(x-A). Из этого следует, что в случае равных стартовых капиталов m(0)=B^2. Например, если у каждого игрока есть по 5 рублей, а ставка — 1 рубль, то в среднем разоряться игроки будут через 25 ходов.

При рассмотрении вышеуказанных формул подразумевалась конечностью математического ожидания числа ходов: m(x)<\infty. Теперь будет предложено доказательство этого факта.

Задача о конечности ожидаемого числа ходов[править | править исходный текст]

Доказать, что m(x)<\infty\quad \forall A,B.

Решение. Достаточно доказать это для случая x=0 (так как ранее было уже продемонстрировано, что случаи x\ne 0 могут быть сведены к x=0 вариацией A и B) и p=q, а затем рассмотреть случай p\ne q. Итак, рассмотрим последовательность S_{0;1;\ldots;n} и введём случайную величину S_{\tau_n} = S_{\tau_n}(\omega), где \tau_n=\tau_n^0 — момент остановки. Далее, пусть S_{\tau_n} (\omega) = \sum\limits_{k=0}^n S_k(\omega) \mathbf{1}_{\{ {\tau_n=k} \}}(\omega). Интерпретация такова: S_{\tau_n} — это значение случайного блуждания в момент \tau_n. Если \tau_n<n, то S_{\tau_n}\in \{A;B\}; если \tau_n=n, то A\leqslant S_{\tau_n} \leqslant B. Вспомним, что p=q=0{,}5, и докажем, что \mathbb{E}(S_{\tau_n})=0, \mathbb{E}(S_{\tau_n}^2) = \mathbb{E}(\tau_n).

Для доказательства первого равенства напишем: \mathbb{E}(S_{\tau_n}) = \sum\limits_{k=0}^n \mathbb{E} \bigl(S_k\mathbf{1}_{\{ {\tau_n=k} \}}(\omega)\bigr) = \sum\limits_{k=0}^n \mathbb{E} \bigl( S_n\mathbf{1}_{\{ {\tau_n=k} \}}(\omega) \bigr) + \sum\limits_{k=0}^n \bigl( (S_k-S_n)\mathbf{1}_{\{ {\tau_n=k} \}}(\omega) \bigr) = \mathbb{E}(S_n) + \sum\limits_{k=0}^n \bigl( (S_k-S_n)\mathbf{1}_{\{ {\tau_n=k} \}}(\omega) \bigr). Совершенно очевидно, что \mathbb{E}(S_n)=0, так как S_n = \xi_1+\ldots+\xi_n, \xi_i=\pm 1 при p=q. Осталось доказать, что \sum\limits_{k=0}^n \bigl( (S_k-S_n)\mathbf{1}_{\{ {\tau_n=k} \}}(\omega) \bigr) = 0. Для 0\leqslant k < n справедливо, что \{ \tau_n>k \} = \{ A<S_1<B;\ldots;A<S_k<B\}. Последнее событие может быть представлено в виде \bigl\{\omega\colon (\xi_1;\ldots;\xi_n)\in J \bigr\}, где J — некоторое подмножество множества \{ -1;+1 \}^k. Это множество определяется только \xi_i при i=\overline{1;k}. Для бо́льших i значения \xi_{k+1};\ldots;\xi_n не влияют на J. Множество вида \{ \tau_n=k \} = \{ \tau_n>k-1 \} \backslash \{ \tau_n>k \} также может быть представлено в виде \bigl\{\omega\colon (\xi_1;\ldots;\xi_n)\in J \bigr\}. Благодаря независимости \xi_i (доказано в подзадаче 2) вытекает, что \forall 0\leqslant k < n случайные величины S_n-S_k и \mathbf{1}_{\{ \tau_n=k \}} независимы. Отсюда \mathbb{E} \bigl( S_k\cdot\mathbf{1}_{\{ {\tau_n=k} \}}(\omega)\bigr) = \mathbb{E}(S_k)\cdot \mathbb{E}\bigl(\mathbf{1}_{\{ {\tau_n=k} \}}(\omega)\bigr)=0 в силу того, что первый множитель нулевой.

 \mathbb{E}(S_{\tau_n}^2) = \sum\limits_{k=0}^n \mathbb{E} ( S^2_k \mathbf{1}_{\{ {\tau_n=k} \}}) =
 = \sum\limits_{k=0}^n \mathbb{E} \Bigl( \bigl(S_n +(S_k - S_n)^2\bigr) \mathbf{1}_{\{{\tau_n=k}\}}\Bigr) =
\sum\limits_{k=0}^n \Bigl( \mathbb{E}(S^2)\mathbf{1}_{\{{\tau_n=k}\}} + 2\mathbb{E} \bigl( S_n (S_k - S_n)\bigr) \mathbf{1}_{\{{\tau_n=k}\}} + \mathbb{E} \bigl( (S_n-S_k)^2 \bigr)\mathbf{1}_{\{{\tau_n=k}\}} \Bigr) =
=\mathbb{E}(S^2) - \sum\limits_{k=0}^n \mathbb{E} \bigl( (S_n-S_k)^2 \bigr)\mathbf{1}_{\{{\tau_n=k}\}} = n - \sum\limits_{k=0}^n \mathbb{E} (n-k)\mathbb{P}\bigl( \{\tau_n=k\}\bigr) = \sum\limits_{k=0}^n k\mathbb{P}\bigl(\{\tau_n=k\}\bigr) = \mathbb{E}(\tau_n).

Установлено, что для идеальной монетки \mathbb{E}(S_{\tau_n})=0, \mathbb{E}(S_{\tau_n}^2) = \mathbb{E}(\tau_n). В случае же p\ne q имеют место соотношения \mathbb{E}(S_{\tau_n}) = (p-q)\mathbb{E}(\tau_n) (поскольку \mathbb{E}(\xi_1) = p-q) и \mathbb{E}\Bigl( \bigl(S_{\tau_n} - \tau_n \mathbb{E}(\xi_1)\bigr)^2 \Bigr) = \mathrm{Var}(\xi_1) \cdot \mathbb{E}(\tau_n), поскольку \mathrm{Var}(\xi_1) = 1-(p-q)^2. Теперь покажем, что \lim\limits_{n\rightarrow\infty} m_n(0) = m(0)<\infty. В случае справедливой игры в силу соотношения \mathbb{E}(S_{\tau_n}^2) = \mathbb{E}(\tau_n) верно, что \mathbb{E}(\tau_n)\leqslant \max\{ A^2;B^2\}. Тогда же \mathbb{E} (\tau_n) = \mathbb{E}(S^2_{\tau_n}) = A^2 \alpha_n + B^2 \beta_n + \mathbb{E} (S^2_n \mathbf{1}_{\{{A<S_n<B}\}}) \mathbf{1}_{\{{\tau_n=n}\}}, поэтому A^2 \alpha_n + B^2 \beta_n \leqslant \mathbb{E}(\tau_n) \leqslant A^2 \alpha_n + B^2 \beta_n + \max\{ A^2;B^2 \}\cdot \gamma_n. Из неравенства \gamma_n<\varepsilon^n следует, что математическое ожидание \mathbb{E}(\tau_n) сходится при n\rightarrow\infty к предельному значению m(0) = A^2\alpha + B^2 \beta = A^2 \cdot \frac{B}{B-A} - B^2\cdot \frac{A}{B-A} = |AB|. В случае несправедливой игры \mathbb{E}(\tau_n)\leqslant \frac{\max\{ |A|;B \}}{|p-q|}. Так как за \tau_n обозначался момент первого вылета частицы за пределы коридора, то математическое ожидание его меньше определённых чисел, следовательно, меньше бесконечности. При таком условии \mathbb{E}(\tau_n)\rightarrow m(0) = \frac{\alpha A + \beta B}{p-q}. \blacksquare

Компьютерное моделирование (метод Монте-Карло)[править | править исходный текст]

Для моделирования игры воспользуемся программой MATLAB.

Для начала сгенерируем последовательность \xi_i, а затем при некотором первоначальном богатстве x создадим цепочку S_k:

Последовательность \xi (getXI)[править | править исходный текст]

n = 100;                             % The length of \xi_i series
U = rand(n,1);                       % Generate 100 random uniform [0;1] values
XI = zeros(n,1);                     % Reserve memory for 100 modified Bernoulli
q = 0.55;                            % Reverse probability
p = 1 - q;                           % Averse probability
 
                                     % The following cycle creates a Bernoulli distribution based on uniform [0;1]
for i = 1:n                          % This cycle divides the [0;1] array into 2 parts: lengths q and p, q+p=1
   if (U(i,1) < q)                        
       XI(i,1) = -1;                 % If a uniform random value falls into q then \xi=-1
   else XI(i,1) = 1;                 % If a uniform random value falls into p then \xi=+1
   end
end
 
x = 10;                              % Initial 1st player's budget offset
 
S = zeros(n,1);                      % Reserve memory for 100 S_1...S_100
 
for i = 1:n                          % Make S_k series according to rule S_{k+1} = S_k + \xi_{k+1}
    S(i,1) = x + sum(XI(1:i, 1));    % considering the initial welfare offset x
end

Затем введём функцию getS(n, q, x), которая бы не просто, как листинг выше, генерировала ряд S_k сразу и мгновенно, а позволяла бы обобщённо на основе введённых значений n, q и x построить ряд, не усложняя вычислений. Это бы упростило рабочую область.

Генерация ряда (getS function)[править | править исходный текст]

function [S] = getS(n, q, x)         % This function depends on n, q and x --- 3 variables
U = rand(n,1);
XI = zeros(n,1);
 
for i = 2:n                          % Uniform->Bernoulli distribution transformation
   if (U(i,1) < q)
       XI(i,1) = -1; 
   else XI(i,1) = 1;
   end
end
 
S = zeros(n,1);                      % Reserve memory for n S_1...S_n
 
for i = 2:n                          % Calculate the S_1...S_n series
    S(i,1) = sum(XI(1:i, 1));        % Sums the \xi's
end
S = x + S;                           % Adds initial welfare to each S_k of the whole matrix

Возникает разумный вопрос: зачем считать \xi, начиная только со второй величины (for i = 2:n)? Дело в том, что это делается исключительно в целях наглядной визуализации. При построении графика в следующем коде будут строиться траектории S_k, и если бы было написано for i = 1:n, то тогда уже с самого первого значения некоторые траектории бы выходили из x-1, некоторые — из x+1. Так как в данной программе из соображений оптимальности лучше не задействовать нулевое значение (из него частица выходит, но не рисуется, так как прибавление \xi_1 происходит сразу), то просто-напросто сдвинем нумерацию на оси абсцисс на единицу вправо. Теперь проведём серию тестов и наглядно рассмотрим возможные траектории при некоторых вероятностях, длинах игры и количестве игр.

Визуализация (graphS)[править | править исходный текст]

Три игры в 10 шагов при q=0{,}45.
Пять игр в 100 шагов при q=0{,}56. Видно, что частицу «тянет вниз» к точке A.
Сто справедливых игр в 10000 шагов.
N = 3;                               % Number of games played
n = 10;                              % Number of tosses
q = 0.45;                            % Chance 1st player loses 1 rouble
x = 0;                               % Initial welfare offset
 
matrS = zeros(N, n);                 % Reserve memory for N rows n cols matrix
for i = 1:N                          % This loop fills the S matrix with S_k, yielding N trajectories
    matrS(i,:) = getS(n, q, x)';
    plot(matrS(i,:));                % Gives an image
    hold on;                         % Holds the axes for next trajectory overlay
end
hold off;                            % Clears axes for a new plot

Теперь подойдём к самой главной составляющей программной части — алгоритму, который позволил бы вычислять среднюю длину игры при заданных параметрах (A;B;n;q). Если теория верна, то нижеследующий эксперимент её лишь подтвердит. Также допишем в программу строчку, которая будет вычислять вероятность разорения первого игрока (\beta(x)) при заданных начальных капиталах и сопоставлять её с теоретической.

Полная модель игры (Monte_Carlo)[править | править исходный текст]

N = 3000;                                 % Number of games played
n = 3000;                                 % Number of tosses
q = 0.5;                                  % Chance 1st player loses 1 rouble
p = 1-q;                                  % Chance 1st player wins 1 rouble
A = -10;                                  % 1st player budget
B = 10;                                   % 2nd player budget
x = 0;                                    % Budget offset towards 1st player
Bs = 0;                                   % amount of cases particle hits B (it will change soon)
As = 0;                                   % amount of cases particle hits A (it will change soon)
 
matrS = zeros(N, n);                      % Reserve memory for N rows n cols matrix
TAU1 = n * ones(N, n);                    % Fill another N rows n cols matrix with n's
for i = 1:N                               % This loop makes up N trajectories of S_k relying on input q, x, n
  matrS(i,:) = getS(n, q, x)';
  for j = 1:n
      if (matrS(i,j) == A)||(matrS(i,j) == B) % If a particle exceeds A or B, then
      TAU1(i,j) = j;                          % put the number of step into the table
      end
  end
  plot(matrS(i,:));                       % Displays a figure
  grid on;
  hold on;                                % Simultaneous plots within same axes
end
hold off;                                 % Clears axes for a new plot
 
TAU = (min(TAU1'))';                      % TAU = earliest step of [A;B] corridor overrun
 
% As [min] affects columns and gives row then we transpose TAU1,
% minimize it by rows and make it a column again
for i = 1:N                               % Our S_n series are ready; they nest in matrS
    for j=1:TAU(i)                        % Scan only till we encounter the escape step!
        if (matrS(i,j) == A);             % If a particle escaped through A (1st player busted)
        As = As+1;                        % then add +1 to 1st player's failures
        elseif (matrS(i,j) == B)          % Otherwise if its first threshold was B
        Bs = Bs+1;                        % then add +1 to 1st player's wins
        end                               % If n is not large enough, then
    end                                   % As + Bs may not make up N
end
ALPHA = As/(As+Bs)                        % Match alphas with their theoretical values
if (q == p)
   THEORALPHA = (B-x)/(B-A)
else THEORALPHA = ((q/p)^B - (q/p)^x)/((q/p)^B - (q/p)^A)
end
BETA = 1-ALPHA                            % Same for betas
if (q == p)
   THEORBETA = (x-A)/(B-A)
else THEORBETA = 1-THEORALPHA
end
meanTAU = mean(TAU)                       % Law of large numbers for great N's
if (q == p)
   THEORTAU = (B-x)*(x-A)
else THEORTAU = 1/(p-q)*(B*THEORBETA+A*THEORALPHA-x)
end

Отметим, что при небольших n не все частицы вылетают из коридора, поэтому здесь надо подчеркнуть, что теория говорит: «при достаточно больших n вероятность \beta_n(x) близка к \beta(x)».

Тестирование[править | править исходный текст]

Нижеследующие данные рассчитаны для n=3000, N = 3000.

№ теста q A B x ALPHA \alpha(x) BETA \beta(x) meanTAU m(x)
1 0{,}49 -6 5 0 0{,}4020 0{,}4006 0{,}5980 0{,}5994 30{,}9307 29{,}6856
2 0{,}6 -60 6 -3 0{,}9733 0{,}9740 0{,}0267 0{,}0260 278{,}2200 276{,}4159
3 0{,}6 -20 2 -1 0{,}7040 0{,}7038 0{,}2960 0{,}2962 62{,}2680 62{,}4178
4 0{,}54 -10 50 10 0{,}9990 0{,}9984 0{,}0010 0{,}0016 251{,}3587 248{,}8205
5 0{,}5 -10 20 0 0{,}6580 0{,}6667 0{,}3420 0{,}3333 202{,}3007 200{,}0000
6 0{,}35 -3 90 0 0{,}1457 0{,}1561 0{,}8543 0{,}8439 256{,}4557 251{,}6022

В экспериментах 2 и 3 продемонстрировано свойство: если игра проигрышная для первого игрока, то увеличение ставки в модели эквивалентно сокращению A, B и x в одно и то же число раз относительно нуля. Ставка увеличилась втрое — вероятность выскочить из коридора со значением B выросла в 11 раз!

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. Ширяев А. Н. Вероятность—1, Вероятность—2 // Москва, МЦНМО. — 2007.