Эффективность тасования колоды.

[Morkonwen]

Здравствуйте такая вероятностьная задачка заинтересовала.
Есть упорядоченная колода И нужно экспериментально определить насколько эффективен тот или иной способ ее тасования. То есть найти какой то хороший понятный параметр или несколько.

Первое что приходит на ум функция корреляции двух последовательностей причем функция бинарная если карты совпадают, то это +1 к ряду, если нет, то +0. Тогда например если просто сдвинуть колоду в любом месте и положить верхнюю часть под нижнюю, то максимум функции корреляции не измениться по сравнению с упорядоченной колодой, а только сместится.

Максимум функции корреляции может служить тогда неким параметром. Кроме того хорошим параметром будет острота максимума функции корреляции, поскольку для совершено случайно колоды по сравнинию с упорядоченной функция корреляции должны быть примерно постоянна.

Какие есть мысли и предложения?

[Sonic86]

Нам когда-то на лекциях рассказывали, что у случайной перестановки доля поворотных точек (т.е. троек $a_{i-1},a_{i},a_{i+1}$ таких, что $(a_{i+1}-a_i)(a_i-a_{i-1})<0$, где $\pi : i \to a_i$ - перестановка) равна $\frac{2}{3}$ (ну в смысле стремится к этой доле по вероятности). Если на перетасовку колоды смотреть как на перестановку, то можно использовать и этот критерий. Кстати, хотелось бы увидеть и его доказательство, если оно короткое.

[Morkonwen]

Sonic86
Кстати ваш параметр не плох! Для намеренно плохо перемешанной колоды он заметно <0.5 для хорошо перемешанной заметно > 0.5

В принципе если смотреть на функцию автокорреляции, то все видно еще лучше: для плохо перемешанной колоды будет несколько отдельностоящих высоких пиков , а для хорошо перемешанной колоды почти равномерное распределение.

[--mS--]

Sonic86 в сообщении #500042 писал(а):

Кстати, хотелось бы увидеть и его доказательство, если оно короткое.

А чего тут доказывать - вероятность указанного события (для случайной перестановки различных чисел) есть $2/3$, поскольку любые из шести вариантов взаименого расположения $a_{i-1}$, $a_i$, $a_{i+1}$$ равновозможны, а нас устроят 4 из них. Случайные величины, равные индикаторам этих событий

$$\xi_i =I(a_i > \max\{a_{i-1}, a_{i+1}\})+I(a_i < \min\{a_{i-1}, a_{i+1}\}) , \quad i=2,\ldots,n-1,$$

являются 2-зависимыми (т.е. $\xi_i$ и $\xi_j$ зависимы при $|i-j| \leqslant2$, и независимы при $|i-j| >2$), поэтому удовлетворяют закону больших чисел. Проверяется хоть через неравенство Чебышёва, хоть разбиением всей суммы на три суммы, в которых суммирование идёт через три слагаемых.

[Morkonwen]

на практике ни параметр с точками поворота ни функция автокорреляции эффективность перемешивания почти не отражают.

Но вот чего удалось придумать:
Пускай колода сначало упорядочена карты идут друг за другом и так для всех четырех мастей.
Дело в том что когда мы тщательно перетасовали колоду расстояния между любыми элементами становятся случайными.Расстояние между 5 пик и 6 пик должно быть случайным, но для плохо смешанной колоды это будет не так. 5 и 6 пик могут быть где то рядом если они слиплись или если между ними попала только 1-2 карты. Так вот если взять среднее новое расстояние изначально последовательных элементов получится весьма неплохой параметр. Он будет лучше если брать не само расстояние а его логарифм. Тогда малые расстояния (как когда карты слиплись) будут влиять сильнее всего.

Для упорядоченной колоды из 52 карт параметр равен 0. поскольку все расстояния равны 1
Для полностью случайной он в среднем равен 2.53 (плюс минус 0,3)

для классического способа перемешивания который используется почти всеми с простым перекладыванием стопок (время мешани 30 сек) 2.01

Если примерно то же время мешать но при этом еще использовать перелистывания колоды(две стопки перелистывать в одну) то параметр примерно 2.12

Если просто разбросать карты по столу стол и смешивать их секунд 10, то параметр будет 2.38

как видите последний способ лучше всего и за меньшее время смешивает колоду. Только этот способ,кстати , и используется в казино крупье.

[Sonic86]

--mS--, спасибо