Помимо краткого курса по теории игр я записался еще на курс, который называется «Probabilistic Graphical Models», что можно перевести как «Вероятностные графические модели». На самом деле речь там идет в основном о Байесовских и Марковских сетях. В этом курсе также встречаются очень простые модели, которые тем не менее хорошо описывают окружающую действительность. Об одном таком примере, который меня очень впечатлил, хочу вам рассказать.
В качестве иллюстрации возьмем известную историю о племяннице губернатора Кубани. Суть ее в том, что молодая девушка, студентка, является владелицей крупного бизнеса, при этом дядя ее – губернатор Краснодарского края. Одни скажут: что такого, может, она очень умная и имеет недюжие предпринимательские способности? Но большинство говорят: это ей дядя подсобил. Но если спросить большинство, почему они отметают идею о ее уме, они только пожмут плечами: это ведь очевидно!
А на самом деле у этой интуитивной уверенности есть строгое математическое обоснование. Итак, допустим, у нас есть случайная величина, показывающая, имеет ли произвольная молодая девушка крупный бизнес. Эта величина зависит от двух других случайных величин (на самом их число конечно больше, но в нашей модели их будет две): «девушка умна» и «ее дядя губернатор». Ведь если девушка умна, то вероятность того, что у ней есть крупный бизнес выше, чем вероятность того, что бизнеса у ней нет. И если ее дядя губернатор, то (во всяком случае в современной России) вероятность того, что бизнес у нее есть много выше вероятности обратного. Мы только что построили простейшую Байесовскую сеть. Изобразим ее графически, ведь это графическая вероятностная модель!
Для моделирования я использовал специальную программу SamIam, она бесплатная и прилагалась к курсу. Стрелками показаны зависимости между переменными. Проставим вероятности у наших переменных.
С первыми двумя переменными все понятно. Вероятность родиться умной 10%, глупой 90%. Это конечно взято с потолка, но суть отражает. Аналогично с вероятностью иметь дядю губернатора. А вот последняя вероятность выглядит сложнее. Это так называемая условная вероятность. Она показывает, какая вероятность иметь или не иметь бизнес при разных условиях. Например, если ты умная, но у тебя нет дяди губернатора, то вероятность иметь бизнес равна 70%. А если ты глупая, но дядя твой губернатор, то вероятность 80%. Если умная и с дядей – 90%, глупая и без дяди – 10%. Числа опять же произвольные, но между собой более или менее согласованные.
Теперь начинается самое интересное. Фигура, когда две стрелочки сходятся книзу в одну переменную, называется V-структура (потому что похожа на латинскую V). Известно, что если нижняя переменная («Имеет бизнес») неизвестна, то две другие переменные не зависят друг от друга. То есть, мы не можем ничего сказать о предпринимательских способностях девушки, зная, что ее дядя губернатор, и наоборот. Но если эта переменная известна, то две другие переменные становятся зависимыми, то есть коррелируют друг с другом. Этот эффект называется probabilistic influence. Посмотрим, как он проявляется.
Зададим в нашей модели, что бизнес имеется.
Видно, что вероятность того, что девушка умна около 30%. Теперь зададим, что помимо этого дядя у девушки губернатор.
Вероятность наличия предпринимательской жилки уменьшилась и стала около 10% (все вероятности программа рассчитывает сама, решая уравнения, так что там все довольно строго). То есть наша уверенность в том, что девушка честно заработала свои миллионы уменьшилась в три раза от того, что мы узнали, кто ее дядя. Это и есть эффект зависимости родительских переменных в V-структуре, если значение дочерней переменной известно.
Таким образом получается, что наша уверенность в том или ином берется не с потолка, мы в голове строим такие же вероятностные модели. Формальное изучение механики таких моделей позволяет понять, почему мы принимаем те или иные решения.
машин в час. Допустим также, что пропускная способность падает линейно и равна 
(конкретные значения констант сейчас не важны, важна сама идея). В нашем случае 
. Тогда из каждого потока за час проедет 
, где 
– другой поток. Каждый поток будет стараться максимизировать свое количество проехавших машин. Приравняем производную по 
:
, тогда число машин, проехавших через слияние будет
и приравняем к нулю для поиска максимума:
. Опять-таки в силу симметричности ситуации для все участников
, где 
– оптимальный поток из каждого рукава.
. Видим, что в этом случае интенсивность каждого потока меньше. Посмотрим, как изменилось количество проехавших через слияние машин для каждого потока:
, причем действительная часть показывает количество белых шаров, а мнимая — черных. Если вынули два белых шара и затем один вернули, то в корзине останется 
. Если вынули два черных и вернули белый, то в корзине будет 
. И, наконец, если вынули белый и черный и вернули черный, в корзине останется 
. Видно, что третий случай эквивалентен первому. Кроме того, общее число шаров 
на каждом шаге уменьшается ровно на единицу, то есть в конечном итоге действительно останется только один шар. Таким образом, при очередной выемке к текущему числу шаров прибавляют либо число 
, либо 
.
выемок по 
и 
выемок по 
(
— неотрицательные целые). Тогда возможно два варианта: 
, если последний шар белый, и 
, если последний шар черный.
— вектор, задающий начальное состояние корзины. Тогда конечное состояние можно представить в виде суммы начального вектора и линейной комбинации векторов 
и 
.
, если последний шар белый, и
, если последний шар черный.
для белого шара и 
для черного. То есть если начальное число черных шаров четное, то последним останется белый шар, если нечетное — то черный. Это и есть ответ.