ML: Некоторые задачи теории вероятностей
Мир Вампуса
Рассмотрим неплохой пример принятия решения в модельном мире Вампуса.
Этот мир состоит из клеток по которым перемещается интеллектуальный агент.
Пусть в любой клетке, независимым образом, с вероятностью $P(h)=0.2$ может находиться яма (hole).
В этом случае в каждой из четырёх соседних с ямой клетках обязательно будет чувствоваться ветерок (breeze).
Предположим, что агент исследовал три угловые клетки своего мира. В них нет ям,
но в двух есть ветер (тильда на рисунке справа). Необходимо определить вероятности ям в клетках (серого цвета),
прилегающих к исследованной области.
Обозначим известную информацию о ямах и ветре в виде двух множеств: $\mathbb{H}=\{\bar{h}_{11},\,\bar{h}_{12},\,\bar{h}_{21}\}$ (нет ям) и $\mathbb{B}=\{\bar{b}_{11},\,b_{12},\,b_{21}\}$ (в ячейке $[1,1]$ ветра нет, а в $[1,2]$ и $[2,1]$ - есть). Мы хотим вычислить, например, вероятность ямы в верхней ячейке границы $H_{3,1}:\,\{h_{3,1},\,\bar{h}_{3,1}\}$, где значение $h_{3,1}$ случайной величины $H_{3,1}$ означает, что яма есть, а значение $\bar{h}_{31}$ - что её нет: $$ P(\mathbb{H}, \mathbb{B}\to H_{31}) ~\sim~ P(H_{31},\mathbb{H},\mathbb{B}) = \sum_{H_{22},H_{13}} P(H_{31}, H_{22},H_{13}, \mathbb{H},\mathbb{B}). $$ Выше знак "$\sim$" означает, что мы опускаем множитель не зависящий от искомой переменной $H_{1,3}$, равный, по определению, условной вероятности $P(\mathbb{H}, \mathbb{B})$. Затем мы расширяем совместную вероятность на соседние клетки по формуле полной вероятности. Сумма состоит из четырёх слагаемых для всех возможных значений $H_{2,2}:\,\{h_{2,2},\,\bar{h}_{2,2}\}$ и $H_{1,3}:\,\{h_{1,3},\,\bar{h}_{1,3}\}$. Воспользовавшись снова определением условной вероятности и независимостью $H_{ij}$, имеем: $$ P(\mathbb{H}, \mathbb{B}\to H_{31}) ~\sim~ \sum_{H_{22},H_{13}} \, P(H_{31})P(H_{22})P(H_{13})\, P(H_{31}, H_{22},H_{13}, \mathbb{H}\to \mathbb{B}). $$ Совместная вероятность была расширена на всю границу, так как вероятность наличия ветра (доступная агенту информация $\mathbb{B}$) зависит от факта наличия или отсутствия ям во всех ячейках, приведенных на рисунке. Теперь можно провести вычисления, расписав явно суммы: $$ \begin{array}{lcl} P(\mathbb{H}, \mathbb{B}\to h_{31}) &\sim& \, P(h_{31})P(h_{22})P(h_{13})\,P(h_{31}, h_{22},h_{13}, \mathbb{H}\to \mathbb{B})~+~P(h_{31})P(\bar{h}_{22})P(h_{13})\,P(h_{31}, \bar{h}_{22},h_{13}, \mathbb{H}\to \mathbb{B})\\ & +& \, P(h_{31})P(h_{22})P(\bar{h}_{13})\,P(h_{31}, h_{22},\bar{h}_{13}, \mathbb{H}\to \mathbb{B})~+~\, P(h_{31})P(\bar{h}_{22})P(\bar{h}_{13})\,P(h_{31}, \bar{h}_{22},\bar{h}_{13}, \mathbb{H}\to \mathbb{B}), \\ P(\mathbb{H}, \mathbb{B}\to \bar{h}_{31}) &\sim& \, P(\bar{h}_{31})P(h_{22})P(h_{13})\,P(\bar{h}_{31}, h_{22},h_{13}, \mathbb{H}\to \mathbb{B})~+~P(\bar{h}_{31})P(\bar{h}_{22})P(h_{13})\,P(\bar{h}_{31}, \bar{h}_{22},h_{13}, \mathbb{H}\to \mathbb{B})\\ & +& \,P(\bar{h}_{31})P(h_{22})P(\bar{h}_{13})\,P(\bar{h}_{31}, h_{22},\bar{h}_{13}, \mathbb{H}\to \mathbb{B})~+~ P(\bar{h}_{31})P(\bar{h}_{22})P(\bar{h}_{13})\,P(\bar{h}_{31}, \bar{h}_{22},\bar{h}_{13}, \mathbb{H}\to \mathbb{B}). \\ \end{array} $$ Учтём что $P(h_{ij})=0.2$ и $P(\bar{h}_{ij})=0.8$. Вероятность $P(h_{31}, h_{22},h_{13}, \mathbb{H}\to \mathbb{B})=1$ так как ямы на границе есть везде, что гарантированно приводит к ветру, а $P(h_{31}, \bar{h}_{22},\bar{h}_{13}, \mathbb{H}\to \mathbb{B})=0$ так как отсутствие ям в ячейках $[2,2]$ и $[1,3]$ не согласуется с наличием ветра в $[1,2]$. Аналогично в остальных случаях: $$ \begin{array}{lcl} P(\mathbb{H}, \mathbb{B} \to h_{31} ) &\sim& 0.2^3 + 0.2^2\,0.8 + 0.2^2\,0.8, \\ P(\mathbb{H}, \mathbb{B} \to \bar{h}_{31} ) &\sim& 0.2^2\,0.8 + 0.2\,0.8^2. \end{array} $$ Этот результат можно представит в виде вектора, с двумя компонентами: $$ P(\mathbb{H}, \mathbb{B}\to H_{31})~\sim \bigr\{0.2^3 + 2\cdot 0.2^2\cdot 0.8,~~~ 0.2^2\cdot 0.8 + 0.2\cdot 0.8^2\bigr \} \sim \bigr\{1 + 2\cdot 4,~~~ 4 + 4\cdot 4\bigr \}. $$ Теперь его необходимо отнормировать на единицу (восстановив опущенные множители): $$ P(\mathbb{H}, \mathbb{B}\to H_{31}) = \bigr\{9,~ 20\bigr \}/(9+20) = \bigr\{0.31,~ 0.69 \}. $$ Таким образом, вероятность обнаружить яму в ячейке $[3,1]$ равна $0.31$. Стоит аналогично проверить, что вероятность ямы в ячейке $[2,2]$ равна $0.86$. Следовательно, агенту стоит (при необходимости) двигаться, либо в ячейку $[3,1]$, либо в ячейку $[1,3]$.
Бесчестная игра Шеня
Два игрока бросают монету, на сторонах которой написаны $0$ и $1$. В результате получается последовательность типа $00110101...$. Перед началом игры, первый игрок выбирает и озвучивает любую последовательность длины три, например $001$. После этого, второй игрок выбирает свою последовательность такой же длины. Выигрывает тот, чья последовательность выпадет раньше. Эта игра является примером случайного процесса с терминальными состояниями.
Так как у первого игрока есть возможность выбрать оптимальную комбинацию, на первый взгляд, он имеет преимущество в этой игре. Однако это не так и у второго игрока существенно больше шансов на победу!
Пусть первый игрок выбрал $001$. Какую комбинацию стоит выбрать второму игроку? Очевидно такую, которая по-возможности блокирует выигрышную комбинацию первого игрока. Перед потенциальной победой первого игрока $001$ могут быть такие истории: $...\underline{000}1$ или $...\underline{100}1$. Поэтому второму игроку стоит выбирать $000$ или $100$. Вариант $000$ хуже, так как он "блокирует" сам себя. Рассмотрим вариант $100$.
Выше на первом графе показаны все переходы для случайного процесса, в котором состояние определяется последними тремя значениями. Например, пусть последние три результата броска монеты равны $...000$ (три герба). Следующее бросание равновероятно даст две новые последовательности $...000$ (петля в узле) или $...001$. На втором рисунке граф расщепляется на два подграфа из-за наличия терминальных узлов (красный, в котором побеждает первый игрок и синий - победный для второго). Из этих узлов стрелки не выходят (конец игры). Есть $6$ равновероятных узлов, ведущих в победный узел второго игрока (включая сразу этот узел, полученный при первых трёх бросках). Поэтому вероятность победы второго игрока равна $6/8=3/4$.
Этот же результат можно получить при помощи следующих вычислений. Обозначим условную вероятность победы второго игрока через $p_{00}$, если последние две цифры последовательности равны $00$. После этого равновероятно может идти $0$ или $1$, что приводит к $000$ или $001$. В первом случае опять получается $p_{00}$, а во втором - второй игрок проигрывает. Аналогичны рассуждения для остальных четырёх вариантов: $$ p_{00}=\frac{1}{2}\,p_{00}+\frac{1}{2}\,0,~~~~~~~~~~~~ p_{01}=\frac{1}{2}\,p_{10}+\frac{1}{2}\,p_{11},~~~~~~~~~~~~ p_{10}=\frac{1}{2}\,1+\frac{1}{2}\,p_{01},~~~~~~~~~~ p_{11}=\frac{1}{2}\,p_{10}+\frac{1}{2}\,p_{11}. $$ Решая эту систему, получаем $p_{00}=0$, $p_{10}=p_{01}=p_{11}=1$. Так как все варианты предыстории равновероятны, вероятность победы второго игрока равна $(0+1+1+1)/4=3/4$.
| 000 | 001 | 100 | 010 | 101 | 011 | 110 | 111 |
| 100 | 100 | 110 | 001 | 110 | 001 | 011 | 011 |
| 7/8 | 3/4 | 2/3 | 2/3 | 2/3 | 2/3 | 3/4 | 7/8 |
Обратим внимание, что четыре комбинации $000$, $010$, $101$, $111$ второму игроку не выгоды в любом случае. Графы переходов расщепляются, давая максимальную вероятность выигрыша, только в чётырёх случаях из восьми. В оставшихся четырёх случаях преимущество второго игрока также легко видеть:
На первом рисунке в красный узел $010$ (первого игрока) можно попасть только из 4-х узлов ($101$, $011$, $111$, $110$), тогда как в синий (второго), можно попасть из шести узлов.
