![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
green_frЗамечательная статья с очередным контринтуитивным результатом, из которой я было сделал экзамен по программированию для студентов, но потом узнал, что у них будет всего час, для часа выходит многовато.
Игра с бросанием монетки. Играют двое. Каждый загадывает последовательность, например «орёл-орёл» (ОО) или «орёл-решка» (ОР). Затем начинаем кидать монетку. Чья последовательность выпадет первой, тот и выиграл.
Очевидно, что вероятность выпадания последовательности одинаковая зависит только от её длины. Но из этого не следует, что вероятность выигрыша в нашей игре будет 50% при условии равенства длин последовательностей.
Например, «ОР» с «ОО» действительно дают 50% на 50%, но тот же «ОР» у «РР» выигрывает с вероятностью в 75%.
Доказательство второго результата на пальцах: если первые два броска были «РР» (25%), то «РР» выиграл, в любом другом случае выпал как минимум один «О», а следовательно выиграет «ОР» — «РР» без впереди него идущего «ОР» стал невозможным.
Напоминает историю с поездами — если поезда VICK и SARA ходят раз в 15 минут, то почему вероятность случайно попасть на первый поезд вдвое выше, чем на второй? Потому что SARA ходит всегда через 5 минут после VICK’а.
К слову, есть совершенно чумовая формула Конвея (того, что «игра жизнь» и пр.), позволяющая по виду последовательностей посчитать вероятность выигрыша каждой. Считается на пальцах, нет никаких свидетельств о том, что Конвей знал доказательство, самое простое доказательство даже в общих чертах далеко от понимания широкой публики (а журнал регулярно печатает такие вещи, на которых я спотыкаюсь).
А ещё можно посчитать среднее время, необходимое для того, чтобы выпала какая-то последовательность. Например, чтобы выбросить «ОРОР» нужно сделать в среднем 20 бросков монетки, а чтобы «РОРР» — 18. «Логично» было бы предположить, что вторая последовательность выигрывает в определённой выше игре — но нет, первая выигрывает с вероятностью в 64%.
Над этим фактом я завис на какое-то время. Но потом тоже придумал интуитивное объяснение, как с поездами. Можно представить, что поезда SARA ходят парами, то есть среднее время ожидания их резко снижается. Но при этом эти пары проходят сразу же после одинокого VICK, который уверенно выигрывает.
Третий парадокс — следствие отсутствия транзитивности. «ООР» выигрывает у «ОРР» с вероятность 2/3, «ОРР» у «РРО» — 3/4, «РРО» у «РОО» — 2/3, а «РОО» у «ООР» — 3/4. Сам по себе факт не удивителен, таких примеров множество. Что зацепило меня, это то, что если все 4 последовательности играют вместе, то у каждой из них вероятность выиграть 25%.
По отдельности эти факты вполне понятны, но вот вместе с мою голову лезут со скрипом.
Игра с бросанием монетки. Играют двое. Каждый загадывает последовательность, например «орёл-орёл» (ОО) или «орёл-решка» (ОР). Затем начинаем кидать монетку. Чья последовательность выпадет первой, тот и выиграл.
Очевидно, что вероятность выпадания последовательности одинаковая зависит только от её длины. Но из этого не следует, что вероятность выигрыша в нашей игре будет 50% при условии равенства длин последовательностей.
Например, «ОР» с «ОО» действительно дают 50% на 50%, но тот же «ОР» у «РР» выигрывает с вероятностью в 75%.
Доказательство второго результата на пальцах: если первые два броска были «РР» (25%), то «РР» выиграл, в любом другом случае выпал как минимум один «О», а следовательно выиграет «ОР» — «РР» без впереди него идущего «ОР» стал невозможным.
Напоминает историю с поездами — если поезда VICK и SARA ходят раз в 15 минут, то почему вероятность случайно попасть на первый поезд вдвое выше, чем на второй? Потому что SARA ходит всегда через 5 минут после VICK’а.
К слову, есть совершенно чумовая формула Конвея (того, что «игра жизнь» и пр.), позволяющая по виду последовательностей посчитать вероятность выигрыша каждой. Считается на пальцах, нет никаких свидетельств о том, что Конвей знал доказательство, самое простое доказательство даже в общих чертах далеко от понимания широкой публики (а журнал регулярно печатает такие вещи, на которых я спотыкаюсь).
А ещё можно посчитать среднее время, необходимое для того, чтобы выпала какая-то последовательность. Например, чтобы выбросить «ОРОР» нужно сделать в среднем 20 бросков монетки, а чтобы «РОРР» — 18. «Логично» было бы предположить, что вторая последовательность выигрывает в определённой выше игре — но нет, первая выигрывает с вероятностью в 64%.
Над этим фактом я завис на какое-то время. Но потом тоже придумал интуитивное объяснение, как с поездами. Можно представить, что поезда SARA ходят парами, то есть среднее время ожидания их резко снижается. Но при этом эти пары проходят сразу же после одинокого VICK, который уверенно выигрывает.
Третий парадокс — следствие отсутствия транзитивности. «ООР» выигрывает у «ОРР» с вероятность 2/3, «ОРР» у «РРО» — 3/4, «РРО» у «РОО» — 2/3, а «РОО» у «ООР» — 3/4. Сам по себе факт не удивителен, таких примеров множество. Что зацепило меня, это то, что если все 4 последовательности играют вместе, то у каждой из них вероятность выиграть 25%.
По отдельности эти факты вполне понятны, но вот вместе с мою голову лезут со скрипом.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2011-12-13 12:10 pm (UTC)Это серьезно? В случайной последовательности нулей и единиц, начиная со случайного места, 011 встречается обычно раньше, чем 110?
no subject
Date: 2011-12-13 12:51 pm (UTC)если 110 начинаеется не с 1 знакоместа (возможно предшествующей последовательности единиц) то все, проиграл
no subject
Date: 2011-12-13 01:09 pm (UTC)no subject
Date: 2011-12-13 01:12 pm (UTC)в смысле, без него все было бы еще хуже - в бесконечной последовательности каждая 110 имеет предшествующую 011
no subject
Date: 2011-12-13 01:24 pm (UTC)no subject
Date: 2011-12-13 01:32 pm (UTC)no subject
Date: 2011-12-13 01:38 pm (UTC)no subject
Date: 2011-12-13 01:40 pm (UTC)Не работает тут теорвер, видать...
no subject
Date: 2011-12-13 01:44 pm (UTC)no subject
Date: 2011-12-13 01:08 pm (UTC)no subject
Date: 2011-12-13 01:11 pm (UTC)no subject
Date: 2011-12-13 01:22 pm (UTC)no subject
Date: 2011-12-13 01:25 pm (UTC)no subject
Date: 2011-12-14 07:17 am (UTC)no subject
Date: 2011-12-14 08:35 am (UTC)Вот его предыдущие статьи в моих пересказах, чтобы примерно представить круг интересов: Ngrams (http://green-fr.livejournal.com/226478.html?style=mine), описательная сложность (http://green-fr.livejournal.com/221493.html?style=mine), задача о перестановке переменных (http://green-fr.livejournal.com/217633.html?style=mine), сборка кубика Рубика (http://green-fr.livejournal.com/211921.html?style=mine) и т.д.
no subject
Date: 2011-12-14 09:07 am (UTC)no subject
Date: 2012-06-02 04:29 am (UTC)no subject
Date: 2012-06-02 09:26 am (UTC)no subject
Date: 2012-06-02 09:46 am (UTC)