немного о тасовке карт
Oct. 26th, 2002 10:37 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaПредположим, у нас есть колода из n игральных карт, и мы хотим её перетасовать перед игрой. Рассмотрим следующую процедуру тасовки. Выбираем случайным образом число от 1 до n, и меняем местами первую карту в колоде с картой с выбранным местом (например, если мы выбрали число 15, меняем первую карту в колоде с 15-й). Потом ещё раз выбираем случайное число от 1 до n, и меняем вторую карту в колоде с этим выбранным местом. И так далее, до карты номер n. Причём на каждом шагу может оказаться, что нам нужно менять карту с самой собой, и тогда мы просто её не трогаем.
Это выглядит как довольно интересный и эффективный (с математической, не практической, точки зрения) метод рандомизации расположения карт. Вот один замечательный результат про него. Предположим, мы "перетасовали" этим методом колоду. Какой из множества возможных результатов перетасовки (а возможных результатов ровно n! -- эн-факториал, количество пермутаций n элементов; например, для колоды из 52 карт число возможных пермутаций равно 80 658 175 170 943 878 571 660 636 856 403 766 975 289 505 440 883 277 824 000 000 000 000) будет самым вероятным? Так вот, оказывается, что если n >= 18 (в частности, для обычной колоды, в которой n = 52) самой вероятной будет идентичная перестановка -- то есть, самым вероятным результатом будет то, что колода вообще не изменится!
(это утверждение легко понять неправильно. Это не значит, что если мы перетасуем таким образом колоду, то с большой вероятностью получим то же самое. Вовсе нет. Мы получим то же самое с очень маленькой вероятностью, но любой другой фиксированный результат - с ещё меньшей. Вообще же, конечно, учитывая то, что "такой же" результат только один, а "других" - огромное количество, ясно, что почти наверняка мы "такой же" не получим).
То есть мы получаем здесь по сути дела очень красивую симметрию в вероятностном распределении результатов тасовки. Этот красивый результат доказывается в статье Гольдштейна и Моуза 2000-го года, которая доступна полностью по данному адресу.
Это выглядит как довольно интересный и эффективный (с математической, не практической, точки зрения) метод рандомизации расположения карт. Вот один замечательный результат про него. Предположим, мы "перетасовали" этим методом колоду. Какой из множества возможных результатов перетасовки (а возможных результатов ровно n! -- эн-факториал, количество пермутаций n элементов; например, для колоды из 52 карт число возможных пермутаций равно 80 658 175 170 943 878 571 660 636 856 403 766 975 289 505 440 883 277 824 000 000 000 000) будет самым вероятным? Так вот, оказывается, что если n >= 18 (в частности, для обычной колоды, в которой n = 52) самой вероятной будет идентичная перестановка -- то есть, самым вероятным результатом будет то, что колода вообще не изменится!
(это утверждение легко понять неправильно. Это не значит, что если мы перетасуем таким образом колоду, то с большой вероятностью получим то же самое. Вовсе нет. Мы получим то же самое с очень маленькой вероятностью, но любой другой фиксированный результат - с ещё меньшей. Вообще же, конечно, учитывая то, что "такой же" результат только один, а "других" - огромное количество, ясно, что почти наверняка мы "такой же" не получим).
То есть мы получаем здесь по сути дела очень красивую симметрию в вероятностном распределении результатов тасовки. Этот красивый результат доказывается в статье Гольдштейна и Моуза 2000-го года, которая доступна полностью по данному адресу.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2002-10-26 02:28 pm (UTC)Re:
Date: 2002-10-26 02:33 pm (UTC)no subject
Date: 2002-10-26 02:37 pm (UTC)то есть, вероятность одной комбинации 1/52! (при равномерном распределении).
Вероятность неполучения исходной комбинации 1 - 1/52!
Допустим, есть аномалия, и исходная комбинация встречается гораздо чаще. В сто тысяч миллионов раз :-) Пусть будет 1/40! Ну и что? Верятность неповторения исходной колоды будет 1 - 1/40! Для меня, как инженера, это единица :-)
Математик, конечно, с этим не согласится :)
Для инженеров...
Date: 2002-10-26 02:48 pm (UTC)Во-первых, аномалия однозначно не единична, а просто распределение не равномерно.
Во-вторых, дело не в единице и не в неповторении исходной колоды, а в том, что вероятность появления определенной комбинации больше в, скажем, те же самые сто тысяч миллионов раз, чем какой-то другой. Это принципиальнейшим образом влияет на стратегию вообще всех карточных игр.
Re: Для инженеров...
Date: 2002-10-26 03:06 pm (UTC)Re: Для инженеров...
Date: 2002-10-26 03:24 pm (UTC)Возьмем такой конкретный пример, близкий мне - из преферанса. У меня четыре козыря, соответственно еще четыре у партнеров. От того, как они распределнеы, зависит, сколько взаток я возьму. Идеальный случай 2:2, наихудший 4:0. Для того, чтоб правильно предсказать количество взяток, что я возьму, и соответственно этому пргнозу заказать игру, мне надо знать вероятность различных распределений козырей на руках партнеров. При рандомальной тасовке колоды вероятность 4:0 (и 0:4) равна 28/323 - чуть меньше 9%. При неравномерном распределении карт эта цифра будет другой. Далее считается оптимальное число вхзяток с учетом именно этих (и других) вероятностей и стоимости той или иной игры - оптимизация по одной дискретной переменной, простая задачка. Так вот распределение карт в колоде влияет на прогноз количества взяток, то есть влияет на игру, которую мне надо заказать.
Re: Для инженеров...
Date: 2002-10-26 03:29 pm (UTC)Заметная разница?
no subject
Date: 2002-10-26 03:12 pm (UTC)