?

Log in

No account? Create an account
немного о тасовке карт - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

немного о тасовке карт [окт. 26, 2002|10:37 pm]
Anatoly Vorobey
Предположим, у нас есть колода из 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-го года, которая доступна полностью по данному адресу.
СсылкаОтветить

Comments:
[User Picture]From: lev
2002-10-26 02:01 pm
Хотелось бы узнать количественную оценку вероятности получения идентичной перестановки для колоды из 52 карт? Стар я уже через формулы продираться :-)
(Ответить) (Thread)
[User Picture]From: avva
2002-10-26 03:07 pm

Re:

Эта вероятность равна Q_52/52!, где Q_n равно числу инволюций на множестве из n элементов. Инволюция = перестановка порядка 2, т.е. если повторить её два раза, получим исходную комбинацию. Всякие формулы для Q_n и другую информацию можно прочитать здесь, это страница именно этой последовательности. Q_52 в точности равна

1 634 780 361 427 637 211 832 917 276 278 628 352

; как видите, мизерное число по сравнению с 52!.
(Ответить) (Parent) (Thread)
[User Picture]From: lev
2002-10-26 03:23 pm
Нифига ж себе, мизерное, 37 знаков.
Я тут прикинул на калькуляторе, вероятность не получить эту самую аномальную пермутацию получается примерно 0.99999999999999999999999999999997973
Для математика, конечно, это не единица, но для меня - вполне :)

Хотя 1-1/52! покрасивше: 0.999999999999999999999999999999999999999999999999999999999999999999987602000
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-10-26 03:11 pm

Re:

Простите, фигню спорол по невнимательности. Делить надо не на 52!, а на 5252 (количество различных путей перетасовать колоду данным способом). 5252 равно

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, которое я привёл выше ;-)
(Ответить) (Parent) (Thread)
[User Picture]From: lev
2002-10-26 03:27 pm
Ха, в этом случае вероятность всего в 100 раз больше
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-10-26 03:29 pm
Не понял. Не в 100 раз больше, а примерно в 1032 раз меньше (чем если делить на 52!). 52! - 68-разрядное число, а 5252 - 90-разрядное.
(Ответить) (Parent) (Thread)
[User Picture]From: lev
2002-10-26 03:42 pm
Ошибся с copy/paste :-)
Не в 100 раз, а в 1Е15 (квинтильон?). Да, громадная разница, то ли 1Е-53, то ли 1Е-68 :-)

(Ответить) (Parent) (Thread)
[User Picture]From: motya
2002-10-26 02:28 pm
Прости, лень копаться в статье... А какова неравномерность распределения? Ну, какая-нибудь дисперсия, скажем? Я видел, такой алгоритм реально используется в жизни как раз для тасовки карт, вот я и думаю, насколько оно не рандомально.
(Ответить) (Thread)
[User Picture]From: avva
2002-10-26 02:33 pm

Re:

Дык я как раз и сам ещё в статье не копался, одним глазом взглянул. Кроме того, они работают с чисто комбинаторными методами, переводя это в проблему в теории графов, так что про дисперсию итп. у них ничего не найти - надо рыться в ссылках, к-е у них есть, на другие статьи, в к-х это изучали.
(Ответить) (Parent) (Thread)
[User Picture]From: lev
2002-10-26 02:37 pm
Для колоды из 52 карт число перестановок 52!
то есть, вероятность одной комбинации 1/52! (при равномерном распределении).
Вероятность неполучения исходной комбинации 1 - 1/52!
Допустим, есть аномалия, и исходная комбинация встречается гораздо чаще. В сто тысяч миллионов раз :-) Пусть будет 1/40! Ну и что? Верятность неповторения исходной колоды будет 1 - 1/40! Для меня, как инженера, это единица :-)
Математик, конечно, с этим не согласится :)
(Ответить) (Parent) (Thread)
[User Picture]From: motya
2002-10-26 02:48 pm

Для инженеров...

Это, уж простите, какое-то очень странное рассуждение.
Во-первых, аномалия однозначно не единична, а просто распределение не равномерно.
Во-вторых, дело не в единице и не в неповторении исходной колоды, а в том, что вероятность появления определенной комбинации больше в, скажем, те же самые сто тысяч миллионов раз, чем какой-то другой. Это принципиальнейшим образом влияет на стратегию вообще всех карточных игр.
(Ответить) (Parent) (Thread)
[User Picture]From: lev
2002-10-26 03:06 pm

Re: Для инженеров...

И каково же влияние, если не секрет?
(Ответить) (Parent) (Thread)
[User Picture]From: motya
2002-10-26 03:24 pm

Re: Для инженеров...

Такого влияния нет, разве что, в пьянице, ну так там и игры, как таковой, нет.
Возьмем такой конкретный пример, близкий мне - из преферанса. У меня четыре козыря, соответственно еще четыре у партнеров. От того, как они распределнеы, зависит, сколько взаток я возьму. Идеальный случай 2:2, наихудший 4:0. Для того, чтоб правильно предсказать количество взяток, что я возьму, и соответственно этому пргнозу заказать игру, мне надо знать вероятность различных распределений козырей на руках партнеров. При рандомальной тасовке колоды вероятность 4:0 (и 0:4) равна 28/323 - чуть меньше 9%. При неравномерном распределении карт эта цифра будет другой. Далее считается оптимальное число вхзяток с учетом именно этих (и других) вероятностей и стоимости той или иной игры - оптимизация по одной дискретной переменной, простая задачка. Так вот распределение карт в колоде влияет на прогноз количества взяток, то есть влияет на игру, которую мне надо заказать.
(Ответить) (Parent) (Thread)
[User Picture]From: lev
2002-10-26 03:29 pm

Re: Для инженеров...

ОК, вместо 28/323 будет 28.000000000000000000000000000000000000000000001/323
Заметная разница?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-10-26 03:12 pm
См. впрочем вышенасчёт максимальной вероятности выпадения одной пермутации (идентичной, собственно) для колоды из 52 карт.
(Ответить) (Parent) (Thread)
[User Picture]From: snyders
2002-10-26 05:38 pm
Правильнее, кажется, на i-ом шаге менять i-ое число со случайным числом в [i..n] ( а не [1..n]). Тогда все перестановки равновероятны?

Нет под рукой Кнута -- там, кажется, именно этот алгоритм.

Вот еще, может пригодится:
http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz
(Ответить) (Thread)
[User Picture]From: avva
2002-10-26 05:45 pm

Re:

Тогда просто не так интересно, именно потому что все перестановки равновероятны ;)

То, что равновероятны, сразу следует из того, что пространство выбора 52!, и любую перестановку можно получить таким образом (просто строя её по позициям), поэтому каждая перестановка должна встречаться ровно один раз.
(Ответить) (Parent) (Thread)
[User Picture]From: rydel23
2002-10-27 03:36 am

Вопрос

Вот вы, Авва, с такой точностью даёте n! и Q_n, мне аж завидно стало. :) Это у вас готовая программка какая-то? Или что-то типа Mathcad or Mathematica?
(Ответить) (Thread)
[User Picture]From: avva
2002-10-27 03:41 am

Re: Вопрос

Зашёл в юникс, запустил bc (стандартный калькулятор), написал в нём функцию за пол-минуты.
Это легко.

В принципе и на сети есть всякие arbitrary precision calculators, просто лень искать было. И, конечно, всякие маткады/математики такое могут, но у меня их нет, незачем.
(Ответить) (Parent) (Thread)
[User Picture]From: rydel23
2002-10-27 04:13 am

Re: Вопрос

Ясно. Я и не догадался. Всё гениальное, как всегда, оказалось очень простым. :)
(Ответить) (Parent) (Thread)