немного о тасовке карт
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}
Вопрос
Date: 2002-10-27 03:36 am (UTC)Re: Вопрос
Date: 2002-10-27 03:41 am (UTC)Это легко.
В принципе и на сети есть всякие arbitrary precision calculators, просто лень искать было. И, конечно, всякие маткады/математики такое могут, но у меня их нет, незачем.
Re: Вопрос