Как стать автором
Обновить

Случайные перестановки и случайные разбиения

Математика *
Из песочницы
Я много лет читаю курсы по комбинаторике и графам для студентов-математиков и computer scientists (как это по-русски, компьютерных научников?), раньше в Академическом университете, а теперь в СПбГУ. Программа у нас построена так, что эти темы проходят как часть «теоретической информатики» (другие темы в ней — алгоритмы, сложность, языки и грамматики). Не могу сказать, насколько это оправдано метафизически или исторически: всё же комбинаторные объекты (графы, системы множеств, перестановки, клетчатые фигуры и др.) начали изучали задолго до появления компьютеров, и сейчас последние хотя и важная, но далеко не единственная причина интереса к ним. Но так посмотреть на самых спецов по комбинаторике и по theoretical computer science — это удивительно часто одни и те же люди: Ловас, Алон, Семереди, Разборов и далее. Наверно, есть на то свои причины. На моих уроках часто очень нетривиальные решения сложных задач предлагают чемпионы олимпиадного программирования (их перечислять не буду, кому любопытно посмотрите топ codeforces.) В общем, думаю, что некоторые вещи из комбинаторики могут быть интересны сообществу. Говорите, если что так или не так.

Пусть вам надо построить случайную перестановку чисел от 1 до $n$, чтобы все перестановки были равновероятны. Это можно сделать многими способами: например, сначала выбрать случайно первый элемент, потом из оставшихся второй и так далее. А можно поступить иначе: выбрать случайно точки $t_1,t_2,\ldots,t_n$ в отрезке $[0,1]$, и посмотреть как они упорядочены. Заменяя наименьшее из чисел на 1, второе на 2 и так далее получаем случайную перестановку. Легко видеть, что все $n!$ перестановок равновероятны. Можно и не в отрезке $0,1$ выбирать точки, а, например, среди чисел от 1 до $N$. Тут возможны совпадения (для отрезка тоже возможны, но с нулевой вероятностью, так что нас они не волнуют) — с ними можно бороться по-разному, например, дополнительно переупорядочивая совпадающие числа. Или взять N побольше, чтобы вероятность совпадения была маленькой (хорошо известен случай, когда $N=365$, а $n$ есть число учеников в вашем классе, и речь о совпадении двух дней рождения.) Вариация этого метода: отметить случайно $n$ точек в единичном квадрате и посмотреть, как упорядочены их ординаты относительно абсцисс. Другая вариация: отметить в отрезке $n-1$ точку и посмотреть, как упорядочены длины отрезочков, на которые он разбился. Ключевой момент в этих подходах — независимость испытаний, по результатам которых строится случайная перестановка. Андрей Николаевич Колмогоров говорил, что теория вероятностей это теория меры плюс независимость — и это подтвердит всякий кто имел дело с вероятностью.

Покажу, как это помогает, на примере формулы крюков для деревьев:



Пусть $\tau$ — подвешенное за корень $r$ дерево с $n$ вершинами, растущее вниз как на картинке. Наша цель — вычислить число $S(\tau)$ нумераций вершин дерева $\tau$ числами от 1 до $n$ таких, что для каждого ребра число в его верхней вершине больше чем в нижней. Одна из таких нумераций приведена на средней картинке. Ответ формулируется с помощью размеров крюков . Крюком $H(v)$ вершины $v$ назовём поддерево, растущее из этой вершины, а его размером просто число вершин в нём. Длины крюков написаны на правой картинке рядом с соответствующими вершинами. Так вот, число нумераций равно $n!$ делить на произведение размеров крюков, так для нашего примера

$S(\tau) = \, \frac{8!}{8\cdot 4 \cdot 3 \cdot 2\cdot 1 \cdot 1\cdot 1\cdot 1} = 210.$


Можно доказывать ту формулу по-разному, например индукцией по числу вершин, но наш взгляд на случайные перестановки позволяет провести доказательство вообще без вычислений. Оно лучше не только элегантностью, но и тем что хорошо обобщается на более тонкие вопросы о нумерациях с предписанными неравенствами, но об этом не сейчас. Так вот, возьмём n различных вещественных чисел и расставим их случайно в вершины дерева, в каждую по одному числу, все $n!$ перестановок равновероятны. Какова вероятность того, что для каждого ребра число в верхней вершине ребра больше числа в его нижней вершине? Ответ: $S(\tau)/n!$, и от набора чисел он не зависит. А раз не зависит, то давайте считать числа тоже выбранными случайно — для определённости, в отрезке $[0,1]$. Вместо того, чтобы сначала случайно выбирать числа, а потом случайно расставлять их в вершины дерева, мы можем просто случайно и независимо выбрать число в каждой вершине: их перестановка окажется случайной автоматически. Таким образом, $S(\tau)/n!$ это вероятность того, что для случайных независимых чисел $\xi(v)$, выбранных по одному для каждой вершины $v$ дерева $\tau$, выполняются все неравенства вида $\xi(v)>\xi(u)$ для всех рёбер $v\to u$, $v$ — верхняя вершина ребра, а $u$ — нижняя. Сформулируем эти условия в равносильном виде, но немного иначе: для каждой вершины $v$ должно происходить такое событие — обозначу его

$Q(v)$: число $\xi(v)$ — максимальное среди всех чисел в вершинах поддерева-крюка $H(v)$.

Заметим, что $\frac{1}{|H(v)|}$ это вероятность события $Q(v)$. В самом деле, в крюке $H(v)$ имеется $|H(v)|$ вершин и максимальное по крюку число сопоставлено каждой из них с равной вероятностью $\frac{1}{|H(v)|}$. Таким образом, формула крюков $S(\tau)/n!=\prod_v \frac{1}{|H(v)|}$ может быть сформулировано так: вероятность того, что происходят сразу все события $Q(v)$, равна произведению вероятностей этих событий. Причин на то может быть много разных, но тут работает первая, приходящая в голову: эти события независимы. Чтобы это понять, посмотрим, например, на событие $Q( r)$ (соответствующее корню). Оно состоит в том, что число в корне больше всех остальных чисел в вершинах, а прочие события касаются сравнений между собой чисел, написанных не в корне. То есть $Q( r)$ касается числа $\xi( r)$ и множества чисел в остальных вершинах, а все остальные события — порядка чисел в вершинах, отличных от корня. Как мы уже обсуждали, «порядок» и «множество» независимы, поэтому событие $Q( r)$ не зависит от прочих. Спускаясь далее по дереву, получим, что все эти события независимы, откуда и следует требуемое.

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

Раз уж пришлось к слову, не могу не рассказать о модели случайной диаграммы Юнга. Диаграмма Юнга это вот такая фигура из $n$ единичных квадратиков, длины её строк возрастают снизу вверх, а длины столбцов слева направо. Количество диаграмм Юнга площади $n$ обозначается $p(n)$, эта важная функция ведёт себя интересно и необычно: например, она растёт быстрее любого многочлена, но медленнее любой экспоненты. Поэтому, в частности, генерировать случайную диаграмму Юнга (если мы хотим, чтобы все диаграммы площади $n$ имели равную вероятность $1/p(n)$) дело нетривиальное. Например, если добавлять клеточки по одной, выбирая место добавления случайно, разные диаграммы будут иметь разные вероятности (так, вероятность однострочечной диаграммы получается равной $1/2^{n-1}$.) Выходит занимательная мера на диаграммах, но не равномерная. Равномерную можно получить так. Возьмём число $t\in (0,1)$, для наших целей лучше всего годятся числа в районе $1-\mathrm{const}/\sqrt{n}$. Для каждого $k=1,2,\ldots$
рассмотрим геометрическое распределение на целых неотрицательных числах со средним $t^k$ (то есть вероятность числа $m=0,1,\ldots$ равна $t^{km}(1-t^k)$). Выберем согласно нему случайную величину $m_k$ (есть много способов как это организовать). При больших $k$ скорее всего 0. Посмотрим на диаграмму Юнга, в которой $m_k$ строк имеют длину $k$ при каждом $k=1,2,\ldots $. Я называю это методом кораблей, потому что общая площадь иногда равна $n$. Если не равна, то повторяем эксперимент. На самом деле равна $n$ она достаточно часто, если умно выбрать $t\in (0,1)$. Предлагаю читателю самостоятельно доказать, что все диаграммы данной площади равновероятны и оценить число шагов.
Теги:
Хабы:
Всего голосов 12: ↑11 и ↓1 +10
Просмотры 3.8K
Комментарии Комментарии 3