немного о тасовке карт
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:01 pm (UTC)Re:
Date: 2002-10-26 03:07 pm (UTC)1 634 780 361 427 637 211 832 917 276 278 628 352
; как видите, мизерное число по сравнению с 52!.
no subject
Date: 2002-10-26 03:23 pm (UTC)Я тут прикинул на калькуляторе, вероятность не получить эту самую аномальную пермутацию получается примерно 0.99999999999999999999999999999997973
Для математика, конечно, это не единица, но для меня - вполне :)
Хотя 1-1/52! покрасивше: 0.999999999999999999999999999999999999999999999999999999999999999999987602000
Re:
Date: 2002-10-26 03:11 pm (UTC)170 676 555 274 132 171 974 277 914 691 501 574 771 358 362 295 975 962 674 353 045 737 940 041 855 191 232 907 575 296
и на это надо делить значение Q_52, которое я привёл выше ;-)
no subject
Date: 2002-10-26 03:27 pm (UTC)no subject
Date: 2002-10-26 03:29 pm (UTC)no subject
Date: 2002-10-26 03:42 pm (UTC)Не в 100 раз, а в 1Е15 (квинтильон?). Да, громадная разница, то ли 1Е-53, то ли 1Е-68 :-)
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)no subject
Date: 2002-10-26 05:38 pm (UTC)Нет под рукой Кнута -- там, кажется, именно этот алгоритм.
Вот еще, может пригодится:
http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz
Re:
Date: 2002-10-26 05:45 pm (UTC)То, что равновероятны, сразу следует из того, что пространство выбора 52!, и любую перестановку можно получить таким образом (просто строя её по позициям), поэтому каждая перестановка должна встречаться ровно один раз.
Вопрос
Date: 2002-10-27 03:36 am (UTC)Re: Вопрос
Date: 2002-10-27 03:41 am (UTC)Это легко.
В принципе и на сети есть всякие arbitrary precision calculators, просто лень искать было. И, конечно, всякие маткады/математики такое могут, но у меня их нет, незачем.
Re: Вопрос