§ 4. Приложение к перемешиванию карт

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

Тасование представляет собой просто перестановку карт в колоде; иными словамп, каждому тасованию соответствует подстановка

где — место, на котором оказывается после тасования карта, находившаяся до тасования на месте. Последовательности тасований соответствует последовательность подстановок из элементов; общее чпсло таких возможных подстановок равно Полнота перемешивания зависит от того, как эти подстановки меняются при переходе от каждого тасования к следующему. Например, если все подстановки идентичны, то каждая карта будет пробегать циклически некоторую последовательность положений в колоде и ее положение можно будет определить, если знать число тасований. Точно так же циклическим образом будет изменяться и совместный порядок всех карт колоды. Конечно, такое положение не совместимо ни с каким разумным образом определенным полным перемешиванием. С другой стороны, изменения положения карты в колоде будут иметь такой же циклический характер, если использовать последовательно все возможных подстановок, расставленных в некотором порядке, и повторять такую процедуру неограниченное число раз.

Ни один из этих примеров не отвечает естественному представлению о полном перемешивании, при котором невозможно предсказать положение карты, зная начальное расположение колоды и число тасований. Необходимо ввести вероятностные идеи. Чтобы сделать это, предположим, что подстановка индуцируемая тасованием, является случайной величиной. Мы занумеруем все подстановок, так что возможными значениями будут числа Характер перемешиваний зависит теперь от свойств процесса процесса тасования.

При исследовании перемещения отдельных карт или групп карт удобнее анализировать не сам процесс тасования, а некоторые процессы, тесно с ним связанные. Пусть -любые различных действительных чисел не превосходящих и пусть

— совокупность положений после тасований карт, занимавших вначале соответственно положения (под «положением» здесь подразумевается, скажем, номер карты, если считать все карты по порядку, начиная с верха колоды). Тогда процесс полностью определяется начальными положениями и процессом Процесс и является естественным средством для изучения перемещений наборов из карт.

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

любого целого положительного равенство

справедливо при любой совокупности из наборов каждый из которых состоит из целых чисел, заключенных между 1 и В некоторых случаях оказывается совершенно достаточным и менее полное перемешивание, чем только что описанное. Например, если чародей (теперь их называют телепатами) предлагает своей жертве перетасовать колоду карт и вынуть одну карту, а затем угадывает, какова эта карта, то для того, чтобы испытать могущество чародея, жертва вовсе не должна быть уверена в полном перемешивании колоды. Здесь будет достаточным значительно более слабое требование, состоящее в том, чтобы для любого положительного и любого целого к, заключающегося между 1 и при всех целых выполнялось равенство

Если это верно, то все возможных положений данной карты становятся равновероятными после длинной серии тасований, независимо от первых у положений этой карты. И вообще, мы будем говорить, что процесс тасования приводит к полному перемешиванию наборов из карт, если для каждого положительного целого и для всех совокупностей из наборов каждый из которых состоит из целых чисел, заключенных между 1 и выполняется равенство

Полное перемешивание колоды совпадает при такой терминологии с полным перемешиванием наборов из карт. Легко проверить, что если то полное перемешивание наборов из карт влечет за собой полное перемешивание также наборов из карт.

Гипотеза Случайные величины задающие процесс тасования, взаимно независимы и одинаково распределены.

Предположение, что величины соответствуют повторным независимым испытаниям, является, вероятно, наиболее естественным. Пусть

и пусть

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

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

Таким образом, процесс является однородной цепью Маркова, у которой суммы элементов матрицы вероятностей перехода по столбцам (так же, как и по строкам) равны 1. Выводы из этого факта были рассмотрены нами в § 2, случае ).

Так как процесс является цепью Маркова, то условие (4.2) для полного перемешивания переходит в условие

причем, поскольку цепь однородная, не будет ограничением предположить, что

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

Гипотеза Выполнена гипотеза и множество наборов из (1 положений карт нельзя разбить на два непересекающихся подмножества так, чтобы не существовало подстановки с положительной вероятностью переводящей хотя бы один набор из первого подмножества в набор из второго подмножества.

Очевидно, если то из вытекает

Если гипотеза выполнена, то цепь х имеет только один эргодический класс, так что [см. § 2, случай д)]

т. е. можно сказать, что в смысле средних здесь имеет место полное перемешивание наборов из карт. Гипотеза не будет выполняться, если, например, при всех подстановках с положительными верхние карт переходят в верхние же карт. С другой стороны, предположим, что каждая из подстановок с положительными переставляет друг с другом верхнюю и нижнюю половины колоды (этот пример нужно слегка видоизменить, если нечетно) и производит, кроме того, какие-то перемещения внутри каждой из половин колоды. Тогда могут быть выполнены все гипотезы однако в этом случае не удовлетворяется одна из следующих гипотез.

Гипотеза Выполнена гипотеза и для всех достаточно больших по крайней мере один из наборов из положений карт с положительной вероятностью может перейти сам в себя за тасований.

Гипотеза влечет за собой если

Если выполнено то процесс х имеет только один эргодический класс и не имеет циклических подклассов. Следовательно,

а это и есть в точности условие (4.2) полного перемешивания наборов из карт.

Гипотезы и ограничивают обращение в вероятностей Если все положительны, тасовании возможны все перестановки, то гипотеза будет удовлетворяться при всех следовательно, будет иметь место полное перемешивание. В этом случае стохастические матрицы не будут содержать нулевых элементов.

Гипотезы и принимают особенно простую форму для эквивалентно утверждению, что выполнено и что можно

перейти от любого расположения карт в колоде к любому другому расположению при помощи последовательности подстановок с положительными что подстановки с положительной вероятностью порождают группу всех подстановок). Гипотеза добавляет к этому условие, состоящее в том, чтобы для всех достаточно больших можно было перейти от любого расположения карт колоды к любому другому расположению (или назад к тому же самому расположению) последовательным применением подстановок, имеющих положительную вероятность. Это добавочное условие будет, например, удовлетворяться, если тождественная подстановка (соответствующая тому, что колода вообще не тасуется) имеет положительную вероятность.

Естественно попытаться расширить гипотезу Один из способов сделать это состоит в том, чтобы наложить ограничения на вспомогательный процесс х, обеспечивающие полное перемешивание наборов из карт, и затем вывести соответствующие гипотезы для процесса Предположим, например, что процесс является однородным марковским процессом. Если то отсюда следует, что на вероятность подстановки с номером при тасовании не влияют результаты предыдущих тасований. Другими словами, при эта гипотеза совпадает просто с гипотезой При эта гипотеза слабее гипотезы однако ее формулировка в терминах процесса является не особенно прозрачной.

Другой способ ослабить гипотезу состоит в том, чтобы предположить лишь, что процесс является однородной цепью Маркова. Эта гипотеза позволяет процессу тасования «обладать некоторой памятью», что, конечно, вполне разумно. Если процесс является сложной -связной цепью Маркова, то процесс х оказывается сложной -связной цепью, и к анализу перемешивания могут быть применены общие теоремы о сложных цепях Маркова (см. § 3). Однако вспомогательный процесс х при может и не оказаться сложной цепью Маркова.