про алису, боба, орла и решку-2
Продолжая предыдущую запись.
Третий вопрос. 3. Кто в среднем наберет больше очков? То есть, в среднем за все 100 бросков Алиса наберет X очков, Боб наберет Y очков. Какие отношения между X и Y? Бонус-вопрос: можете ли вы найти точные значения X и Y?
Правильный ответ - в среднем каждый наберет одинаковое число очков, а именно 24.75 (99/4). Для хорошо знающих теорию вероятностей это очень простой вопрос, показывающий силу очень важного принципа - аддитивности математического ожидания даже зависимых друг от друга событий. Говоря простыми словами, спросим себя, сколько в среднем очков получит Алиса *на втором броске*? Ответ 1/4, потому что из 4 возможных равновероятных исходов первых двух бросков только один дает ей 1 очко. Сколько очков в среднем получит Алиса на третьем, четвертом итд. броске? Ответ всегда 1/4 по той же причине. Несмотря на то, что события "получила очко на 2-м броске" и "получила очко на третьем броске" очень сильно зависят друг от друга, ВСЕ РАВНО (и это крайне контринтуитивно поначалу, но очень важно понимать и уметь пользоваться) число очков в среднем по всем броскам - это простая сумма этих 1/4 за каждый возможный бросок, на котором можно получить очко. То есть, 1/4 умножить на 99 таких бросков. Для Боба ситуация абсолютно такая же и ответ такой же. Вот и все.
Для тех, кого не убеждает использование этого принципа, могу предложить аргумент с подсчетом. Ведь среднее число очков за игру - это просто-напросто общее число очков во всех возможных играх, поделенное на количество возможных игр. Это и значит "среднее". Сколько всего возможных игр? Число последовательностей из О и Р длиной 100, т.е. 2^100. Сколько в них всего очков Боба, например? Посчитаем отдельно по позициям: есть 2^98 игр, в которых Боб получает очко на второй позиции (после второго броска), потому что нам необходимо зафиксировать ОР в позициях 1,2, а остальные 98 могут быть любыми. Значит, 2^98 очков Боба, полученных на втором броске; столько же на третьем, четвертом итд., всего 99*2^98 очков Боба, и поделив на 2^100 игр, получаем те же 99/4 очков в среднем. То же самое у Алисы.
(Подумать как следует над решением с подсчетом может помочь поверить в принцип аддитивности матожидания)
И наконец, самый сложный вопрос.
Четвертый вопрос. Что более вероятно: что Алиса победит Боба, или что Боб победит Алису?
Правильный ответ: несмотря на равенство среднего числа очков в третьем вопросе, более вероятна победа Боба, с вероятностью примерно 51%.
Это легко проверить опытным путем, если запустить симуляцию достаточно большого числа игр. Но как это объяснить?
Почти все, кто написал правильный ответ, дали следующее логичное объяснение (и я тоже его для себя придумал). Хотя общее число очков у Алисы и Боба по всем играм одинаковое, очки Алисы более "скученные". Например, Алиса может в одной игре получить даже 99 очков, если все О, а Боб максимум 50. Значит, во многих играх Алиса как бы "зря расходует" свои очки на создание большего перевеса, чем нужен для победы, и поэтому выигрывает в меньшем количестве игр, чем Боб, и в целом шанс победить у нее немного меньше.
Это очень логичное объяснение. Но оно совершенно неверно. У Алисы немного меньше шанс победить, но не поэтому. Почему я в этом уверен, будет понятно из правильного объяснения, к которому я в итоге пришел (ну не только я, конечно, в твиттере это многие обсуждали). Вот оно.
Будем вести счет игре, давая +1 за каждое очко Алисы и -1 за каждое очко Боба. Если в конце счет положительный/отрицательный, то победила Алиса/победил Боб. Мы начинаем со счета 0. Представим себе вначале, что мы играем игру неопределенно долго, тогда счет будет блуждать случайным образом, начиная с 0, потом переходя, например, в положительный район, покружив там, через 0 в отрицательный, и так далее. Чтобы быть точнее, поделим всю запись игры на "экскурсии" в + или -, каждая из которых начинается после броска О с нулевым счетом. Если после такого О идет О, мы идем в +1, и блуждаем там какое-то время, пока опять не окажемся в О со счетом 0. Если Р, то -1 и опять блуждаем до следующего О при нулевом счете.
Если именно так определить "экскурсии", то оказывается, что средняя длина положительных и отрицательных экскурсий одинакова. Это можно доказать, выписав вероятности переходов и увидев симметрию, но есть более остроумный способ: если прочитать экскурсию от конца к началу, то положительная превращается в отрицательную и наоборот. Например: ОООРООРОРРРРО это положительная экскурсия, в течение которой счет был: 1, 2, 1, 2, 1, 0. А теперь перевернем ее, прочитаем от конца к началу: ΟРРРРОРООРООО, здесь счет идет: -1, -2, -1, -2, -1, 0.
Таким образом, число положительных экскурсий любой данной длины строго равно числу отрицательных такой же длины. А это значит, что всю игру можно представить как череду экскурсий, каждая из которых случайным образом положительная или отрицательная, и вот после 100-го броска внезапно игру обрывают, и внутри какой экскурсии мы остановились, тот игрок и победил. Поскольку длина экскурсии не зависит от знака, очевидно, что шанс оказаться внутри положительной экскурсии после 100-го броска равен шансу оказаться внутри отрицательной. Но почему же тогда шансы Алисы и Боба победить не равны 50% у каждого?
Потому что есть крохотная асимметрия в подсчете очков. Посмотрите на пример двух экскурсий выше. В отрицательной экскурсии ОРРРРОРООРООО мы все время, кроме начального и последнего О, имеем отрицательный счет, и если игра оборвется в середине этой экскурсии, победит Боб. А в ее положительном двойнике ОООРООРОРРРРО счет положительный до последнего блока РРРРО, в течение которого он уже 0, но мы еще не дошли до О с этим нулевым счетом. Если игра оборвется на этом блоке, будет ничья. Оказывается, эта крохотная разница и есть причина победы Боба. Последовательности из одних Р при нулевом счете должны "по-честному" (кроме самой первой в начале игры) считаться за Алису, потому что они стоят в конце положительных экскурсий, но по правилам игры они не засчитываются ни за кого. И те случаи, когда 100-й бросок оказывается внутри таких последовательностей, и дают перевес Бобу. Если изменить правила так, что "если конец игры падает на Р при нулевом счете, но при этом не все вообще броски Р, то победа засчитывается Алисе", то оказывается, что вероятность победы ровно 50% у каждого. Причем *ровно* 50% - если посчитать число выигрышных игр у Алисы и Боба, они совпадают один к одному (я посчитал для 25 бросков, не для 100).
Обратите внимание, что при таком изменении правил игры, когда мы "ничейные" (нулевой счет) блоки Р записываем в пользу Алисе, все равно остается верным, что у Алисы больше скученность очков, что у нее есть игры с числом очков больше 50, а у Боба таких не бывает - все аргументы того объяснения, что я дал первым, остаются верными, но шансы победить тем не менее равны. Вот почему я написал выше, что уверен, что то объяснение неверно.
Вроде все.
Третий вопрос. 3. Кто в среднем наберет больше очков? То есть, в среднем за все 100 бросков Алиса наберет X очков, Боб наберет Y очков. Какие отношения между X и Y? Бонус-вопрос: можете ли вы найти точные значения X и Y?
Правильный ответ - в среднем каждый наберет одинаковое число очков, а именно 24.75 (99/4). Для хорошо знающих теорию вероятностей это очень простой вопрос, показывающий силу очень важного принципа - аддитивности математического ожидания даже зависимых друг от друга событий. Говоря простыми словами, спросим себя, сколько в среднем очков получит Алиса *на втором броске*? Ответ 1/4, потому что из 4 возможных равновероятных исходов первых двух бросков только один дает ей 1 очко. Сколько очков в среднем получит Алиса на третьем, четвертом итд. броске? Ответ всегда 1/4 по той же причине. Несмотря на то, что события "получила очко на 2-м броске" и "получила очко на третьем броске" очень сильно зависят друг от друга, ВСЕ РАВНО (и это крайне контринтуитивно поначалу, но очень важно понимать и уметь пользоваться) число очков в среднем по всем броскам - это простая сумма этих 1/4 за каждый возможный бросок, на котором можно получить очко. То есть, 1/4 умножить на 99 таких бросков. Для Боба ситуация абсолютно такая же и ответ такой же. Вот и все.
Для тех, кого не убеждает использование этого принципа, могу предложить аргумент с подсчетом. Ведь среднее число очков за игру - это просто-напросто общее число очков во всех возможных играх, поделенное на количество возможных игр. Это и значит "среднее". Сколько всего возможных игр? Число последовательностей из О и Р длиной 100, т.е. 2^100. Сколько в них всего очков Боба, например? Посчитаем отдельно по позициям: есть 2^98 игр, в которых Боб получает очко на второй позиции (после второго броска), потому что нам необходимо зафиксировать ОР в позициях 1,2, а остальные 98 могут быть любыми. Значит, 2^98 очков Боба, полученных на втором броске; столько же на третьем, четвертом итд., всего 99*2^98 очков Боба, и поделив на 2^100 игр, получаем те же 99/4 очков в среднем. То же самое у Алисы.
(Подумать как следует над решением с подсчетом может помочь поверить в принцип аддитивности матожидания)
И наконец, самый сложный вопрос.
Четвертый вопрос. Что более вероятно: что Алиса победит Боба, или что Боб победит Алису?
Правильный ответ: несмотря на равенство среднего числа очков в третьем вопросе, более вероятна победа Боба, с вероятностью примерно 51%.
Это легко проверить опытным путем, если запустить симуляцию достаточно большого числа игр. Но как это объяснить?
Почти все, кто написал правильный ответ, дали следующее логичное объяснение (и я тоже его для себя придумал). Хотя общее число очков у Алисы и Боба по всем играм одинаковое, очки Алисы более "скученные". Например, Алиса может в одной игре получить даже 99 очков, если все О, а Боб максимум 50. Значит, во многих играх Алиса как бы "зря расходует" свои очки на создание большего перевеса, чем нужен для победы, и поэтому выигрывает в меньшем количестве игр, чем Боб, и в целом шанс победить у нее немного меньше.
Это очень логичное объяснение. Но оно совершенно неверно. У Алисы немного меньше шанс победить, но не поэтому. Почему я в этом уверен, будет понятно из правильного объяснения, к которому я в итоге пришел (ну не только я, конечно, в твиттере это многие обсуждали). Вот оно.
Будем вести счет игре, давая +1 за каждое очко Алисы и -1 за каждое очко Боба. Если в конце счет положительный/отрицательный, то победила Алиса/победил Боб. Мы начинаем со счета 0. Представим себе вначале, что мы играем игру неопределенно долго, тогда счет будет блуждать случайным образом, начиная с 0, потом переходя, например, в положительный район, покружив там, через 0 в отрицательный, и так далее. Чтобы быть точнее, поделим всю запись игры на "экскурсии" в + или -, каждая из которых начинается после броска О с нулевым счетом. Если после такого О идет О, мы идем в +1, и блуждаем там какое-то время, пока опять не окажемся в О со счетом 0. Если Р, то -1 и опять блуждаем до следующего О при нулевом счете.
Если именно так определить "экскурсии", то оказывается, что средняя длина положительных и отрицательных экскурсий одинакова. Это можно доказать, выписав вероятности переходов и увидев симметрию, но есть более остроумный способ: если прочитать экскурсию от конца к началу, то положительная превращается в отрицательную и наоборот. Например: ОООРООРОРРРРО это положительная экскурсия, в течение которой счет был: 1, 2, 1, 2, 1, 0. А теперь перевернем ее, прочитаем от конца к началу: ΟРРРРОРООРООО, здесь счет идет: -1, -2, -1, -2, -1, 0.
Таким образом, число положительных экскурсий любой данной длины строго равно числу отрицательных такой же длины. А это значит, что всю игру можно представить как череду экскурсий, каждая из которых случайным образом положительная или отрицательная, и вот после 100-го броска внезапно игру обрывают, и внутри какой экскурсии мы остановились, тот игрок и победил. Поскольку длина экскурсии не зависит от знака, очевидно, что шанс оказаться внутри положительной экскурсии после 100-го броска равен шансу оказаться внутри отрицательной. Но почему же тогда шансы Алисы и Боба победить не равны 50% у каждого?
Потому что есть крохотная асимметрия в подсчете очков. Посмотрите на пример двух экскурсий выше. В отрицательной экскурсии ОРРРРОРООРООО мы все время, кроме начального и последнего О, имеем отрицательный счет, и если игра оборвется в середине этой экскурсии, победит Боб. А в ее положительном двойнике ОООРООРОРРРРО счет положительный до последнего блока РРРРО, в течение которого он уже 0, но мы еще не дошли до О с этим нулевым счетом. Если игра оборвется на этом блоке, будет ничья. Оказывается, эта крохотная разница и есть причина победы Боба. Последовательности из одних Р при нулевом счете должны "по-честному" (кроме самой первой в начале игры) считаться за Алису, потому что они стоят в конце положительных экскурсий, но по правилам игры они не засчитываются ни за кого. И те случаи, когда 100-й бросок оказывается внутри таких последовательностей, и дают перевес Бобу. Если изменить правила так, что "если конец игры падает на Р при нулевом счете, но при этом не все вообще броски Р, то победа засчитывается Алисе", то оказывается, что вероятность победы ровно 50% у каждого. Причем *ровно* 50% - если посчитать число выигрышных игр у Алисы и Боба, они совпадают один к одному (я посчитал для 25 бросков, не для 100).
Обратите внимание, что при таком изменении правил игры, когда мы "ничейные" (нулевой счет) блоки Р записываем в пользу Алисе, все равно остается верным, что у Алисы больше скученность очков, что у нее есть игры с числом очков больше 50, а у Боба таких не бывает - все аргументы того объяснения, что я дал первым, остаются верными, но шансы победить тем не менее равны. Вот почему я написал выше, что уверен, что то объяснение неверно.
Вроде все.