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