Математики на примере «пятнашек» вычисляют, как возникает случайность

Original author: Marcus Woo
  • Translation
image

Задача головоломки «пятнашки» — упорядочить пронумерованные плитки. Сегодня математики решили обратную задачу — как перепутать головоломку.

Вероятно, вы играли в «пятнашки». Это расстраивающая, но аддиктивная игра, состоящая из 15 плиток и одного пустого пространства, выстроенных в сетку 4 на 4. Задача заключается в перемещении плиток и выстраивании их в порядке возрастания чисел или, в некоторых версиях, сборке из них изображения.

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

Сегодня появилось новое доказательство решения «игры в 15», но в обратном порядке. Математики Юн Чу и Роберт Хоу из Университета Стони Брук определили количество ходов, необходимое для превращения упорядоченного поля в случайное.

Версия задачи «пятнашек» с рандомизаций была предложена Перси Диаконисом в 1988 году. Он предположил, что для рандомизации головоломки любого размера требуется примерно n3 ходов. То есть для поля 4 на 4 потребуется 43, или 64 хода, а для поля 10 на 10 — 103, или 1 000 ходов. (Хотя они всё равно называются «пятнашками», поля могут иметь любое количество пространств, составляющих правильный квадрат.)

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

Диаконис надеялся, что разобравшись с задачей запутывания «пятнашек» мы сможем понять, как упорядоченные системы в целом превращаются в равномерно перемешанное состояние.

В ситуациях наподобие «пятнашек» случайность развивается по одному шагу за раз. Представьте полностью упорядоченное поле, с единицей в левом верхнем углу и пустым пространством в правом нижнем. Сдвинем плитки так, чтобы пустое пространство переместилось на один квадрат в любом из четырёх возможных направлений: вверх, вниз, влево или вправо. (Ради математической изящности Чу и Хоу рассматривали поле, края которого соединены друг с другом в кольцо, поэтому плитки никогда не застревают в углах.) Сделаем случайный выбор. Теперь поле находится в новой конфигурации — не совсем в упорядоченной, но недалеко от неё. Повторим этот процесс. Если продолжить перемещать пустой квадрат, то поле всё сильнее будет отдаляться от исходного упорядоченного расположения.

Важной особенностью этого процесса является то, что на каждом шаге последующая конфигурация поля зависит только от текущей конфигурации. Это напоминает игру в Monopoly: вероятность бросить кубики и переместиться на две клетки из Park Place в Boardwalk не зависит от бросков, которые привели нас в клетку Park Place.

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

«Цепи Маркова находятся в „золотой середине“ — с одной стороны, мы всё ещё можем их анализировать, с другой, они описывают многие интересующие нас явления», — рассказывает математик Ювал Перес, провёдший важную работу в теории вероятностей.

В своей новой работе Чу и Хоу работали с рандомизацией «пятнашек» как с цепью Маркова. В частности, они рассматривали набор чисел, называемый «матрицей перехода» цепи Маркова. Матрица перехода — это обширное множество чисел, определяющее вероятность того, что «игра в 15» перейдёт из одной конфигурации в другую, если мы решим перемещать пустое пространство случайным образом.

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

«Собрав достаточно информации о собственных числах, мы сможем получить очень точную информацию о перемешивании», — говорит Хоу.

Матрица перехода для «пятнашек» содержит огромное количество информации, отражающей триллионы различных конфигураций, которые может создавать даже небольшое поле 4 на 4. Это больше информации, чем математики способны обработать напрямую. Поэтому вместо анализа матрицы перехода на каждом шаге пути поля к рандомизации, Чу и Хоу выяснили, как характеризовать усреднённое поведение всей матрицы перехода на протяжении всего путешествия.

Их подход похож на то, как можно узнать, где мы вероятнее всего окажемся на поле Monopoly после 1000 бросков кубиков: можно на самом деле столько раз бросить кубик, или просто взять среднее значение нескольких бросков и экстраполировать их.

При помощи этой техники Чу и Хоу вычислили собственные значения матрицы перехода, которое сообщили им, сколько ходов нужно сделать для рандомизации «пятнашек». Они даже получили два ответа, основанных на двух разных определениях случайности.

Сначала они рассматривали рандомизируемое поле, на котором каждая плитка с равной вероятностью может находиться в любом квадрате поля. При таком определении они выяснили, что для рандомизации поля n на n понадобится n4 ходов (то есть 256 шагов для поля 4 на 4 и 10 000 шагов для поля 10 на 10). Это больше, чем предсказывал Диаконис (как мы помним, он предположил n3 шагов).

Второе определение случайности Чу и Хоу было более строгим. Они рассматривали рандомизируемое поле, которое с равной вероятностью может находиться в любом из своего множества возможных конфигураций. Они доказали, что для достижения такого определения случайности потребуется немного больше шагов — не более чем примерно n4 log n ходов.

Чу и Хоу продемонстрировали, что рандомизировать «игру в 15» сложнее, чем предсказывал Диаконис; в определённом смысле это позволяет предположить, что для полного устранения порядка в системе требуется больше времени, чем ожидалось. Благодаря их работе «пятнашки» теперь стали одной из немногих задач рандомизации, в которых, по словам Хоу, «по сути, известно количество необходимых для рандомизации шагов».

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

«Мы не понимаем полностью, какие цепи Маркова демонстрируют такую внезапность», — говорит Перес. «Это одна из самых больших загадок в данной области».

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 10

    +1
    После своего появления в 1870-х годов она вошла в стандартный набор игр.

    Разрешите поинтересоваться, что за набор?
      0
      Сапёр, Солитёр и прочие игры.
        +1
        Сапер с 1870 года??
      0
      N в четвёртой степени это как-то очень много.
      На практике для маленьких размеров от исходного состояния невозможно уйти дальше фиксированного количества шагов. Для «пятнашки» 3х3 это всего 31 ход.
      Можно проверить полным перебором 9! состояний.
        0
        Это если целенаправленно разбирать. А у них случайным образом.
        +2
        … как возникает случайность?
        Сделаем случайный выбор.

        Так как всё-таки как возникает случайность? Получается, что случайность поля зависит только лишь от алгоритма случайного выбора и количества ходов (при упорядоченной начальной конфигурации).

        для рандомизации поля n на n понадобится n4 ходов

        Какой критерий рандомизационности поля они выбрали? И с какой вероятность должен выполняться этот критерий?

        каждая плитка с равной вероятностью может находиться в любом квадрате поля
        поле… с равной вероятностью может находиться в любом из своего множества возможных конфигураций

        Откуда взялись эти определения? Начальная задача имеет совсем другое определение. Как они доказали, что случайное (неизвестное) передвижение пустой плитки при 256 (а не 100500) повторениях даёт нам именно равномерное распределение (а, например, не нормальное)?

        Доказали
        понадобится n4 ходов
        не более чем примерно n4 log n ходов

        Как доказали? Как проверили? Какие результаты?
          0
          Как они доказали, что случайное (неизвестное) передвижение пустой плитки при 256 (а не 100500) повторениях даёт нам именно равномерное распределение (а, например, не нормальное)?

          В статье пропущено решение уравнений Колмогорова для марковского процесса, это просто большая СЛАУ, по которой можно вычислить финальные вероятности состояний.
          Учитывая что они «Ради математической изящности» выкинули спец. условия на краях и в углах — скорее всего финальные вероятности состояний распределены равномерно.

          По мере увеличения числа переходов вероятности будут стремиться к своим финальным значениям, вопрос лишь насколько быстро это произойдёт (ну и с какой точностью).

          Однако вопросов действительно много.
          Если рассмотреть шахматную доску (чётное N), то любое перемещение «пустого пространства» будет чередовать белые и чёрные клетки, что сделает часть состояний невозможными для любого фиксированного количества шагов. А это сложно назвать «случайным».
          0

          ЕМНИП, в пятнашках нельзя получить все возможные конфигурации. Существуют два сета. Один, который можно решить до "1..2....14..15" и второй, (зеркальный, что ли?) который можно решить до "1..2....15..14" (но не до "1..14..15").

            0
            Ну так очевидно, рассматривали только достижимые состояния.
              0

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

          Only users with full accounts can post comments. Log in, please.