Случайные замощения и стохастическая динамика на графе Гельфанда-Цетлина

• Автор: Горин, Вадим Евгеньевич
• Шифр специальности: 01.01.05
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 111 с. : ил.

Содержание
Введение

1 Случайные замощения и марковские цепи

1.1 Базовая модель

1.2 Простейшие числовые характеристики

1.3 Стохастические матрицы

1.4 Переходные вероятности 5 н-► 51 ±

1.5 Алгоритмическое описание

1.5.1 Алгоритм для перехода 5 5 +

1.5.2 Алгоритм для перехода 5 ь->

1.6 Численные эксперименты

2 Корреляционные функции
2.1 Одномерные распределения и многочлены Хана
2.2 Многомерные корреляционные функции
2.3 Двумерная динамика и ее корреляционные функции
3 Предельный переход в корелляционных ядрах
3.1 Формулировка результата
3.2 Статический случай
3.3 Общий случай
3.4 Анализ полученных результатов
4 Марковские цепи на графе Гельфанда—Цетлина
4.1 Граф Гельфанда-Цетлина
4.2 Когерентные системы, возникающие из теории представлений
4.3 Свойства марковских цепей Хр,г',ц/(£)
4.4 Детерминантная форма записи переходных вероятностей
4.5 Предельный процесс
4.6 Марковская полугруппа предельного процесса
4.7 Интерпретация построенного процесса как к-
преобразования Дуба

Введение
Диссертация посвящена исследованию стохастических моделей, связанных со случайными замощениями и простейшими случайными поверхностями — с одной стороны, и с теорией представлений бесконечномерной унитарной группы — с другой. Замечательным свойством, объединяющим вес изучаемые вероятностные модели, является то, что с помощью несложных комбинаторных биекций их можно отождествить с некоторыми ансамблями нспсрссекающихся ломаных на двумерной решетке.
Для любых целых а,Ь,с> 1 рассмотрим нарисованный на правильной треугольной решетке шестиугольник со сторонами а, Ь, с, а, Ь, с. Обозначим через Г2ахЬхс множество всех замощений этого шестиугольника ромбами, полученными склейкой двух соседних элементарных треугольников. Эквивалентно, Г2ахг>хС — это множество всех паросочетаний (димеров) на части двойственной гсскагональной решетки, ограниченной нашим (а, 6, с)-шестиуголышком. Элемент множества $Х5х5 изображен на рис.

Рис. 1: Замощение, ступенчатая поверхность или ограниченное плоское разбиение. Линии, разделяющие “горизонтальные” ромбы, удалены.
Элементы множества !Захбхс имеют различные комбинаторные интерпретации, многие из которых приведены в первой главе диссертации. В частности, на них можно смотреть как на плоские разбиения (трехмерные диагаммы Юнга) или же ступенчатые поверхности в трехмерной коробке размера ахЬхс. В такой интерпретации равномерно

распределенный элемент Пах{,хс задает простейшую модель случайной поверхности. Эта модель, ее вариации и обобщения интенсивно изучались начиная с конца 90-х годов, когда был обнаружен феномен “предельных форм” — аналог классического закона больших чисел. Оказывается, при измельчении шага решетки случайная ступенчатая поверхность стремится (здесь можно, например, говорить о сходимости по вероятности) к неслучайной кусочно-гладкой поверхности в М3. Существование таких предельных поверхностей было впервые анонсировано Вершиком [67] в 1997 году в модели плоских разбиений (без ограничений) с мерой qvo1, где vol — объем плоского разбиения. Позже Кеннон и Серф [28] привели полное доказательство сходимости и описали возникающую предельную форму. В 1998 году Кон, Ларсен и Пропп [30] доказали аналогичный закон больших чисел для плоских разбиений в коробке размера а х Ь х с и дали описание предельной поверхности для этой модели.
В дальнейшем существование предельных форм было доказано Коном, Кенионом н Проппом [29] (см. также работы [32], [31]) для произвольных кусочно-гладких граничных условий (т.е. для ступенчатых поверхностей, отвечающих равномерно распределенным замощениям не простейшего шестиугольника, а более сложных областей). А в работах Кениона, Окунькова и Шеффилда [47], [48] было получено описание возникающих предельных форм, а также была обнаружена интересная связь последних с алгебраическими кривыми.
Интересной особенностью предельных поверхностей является наличие в них фазового перехода: наряду с частью предельной формы, которая является нетривиальной гладкой поверхностью (так называемая “жидкая фаза”), есть и “замороженные области”, в которых предельная поверхность является частью плоскости.
Основной целью первой главы диссертации является введение марковских цепей на плоских разбиениях в коробке, которые сохраняют равномерные меры.
Обозначим через р.ахЬхс равномерную вероятностную меру на

Мы начинаем с единственного семейства непересекающихся путей 7о £
ВДг,о).
Далее мы совершаем 5 шагов. На г-ом шаге мы конструируем % £ 0(ЛГ, Т,?’), распределенное в соответствии с вероятностной мерой д(ЛГ, Т, г), используя уже построенное на предыдущем шаге семейство путей £ Г2(ДГ, Г, г — 1). Теорема 1.8 гарантирует, что тогда Т$ является искомым случайным элементом £1{Ы, Т, 5).
Оценим количество операций, необходимое для случайной выборки, с использованием этого алгоритма. Каждое обновлением требует О(-У) операций. Для каждого шага 5 —► <5 + 1 мы выполняем Т
последовательных обновлений. Следовательно, для построения случайного элемента множества Г2(АТ, 5) нам требуется 0(ЛГГ5) арифметических операций.
На рис. 5 изображена случайная поверхность, построенная с помощью приведенного выше алгоритма. Здесь N = 1000, Т = 2000, 5 = 1000. Для построения этого замощения потребовалось менее 4 минут работы нашего ноутбука (1п1е1 Соге2 Био 2.2СНг, 2СЪ Дат). Теоретически предсказанный “замороженный эллипс” (см. статыо Кона, Ларсена и Проппа [30]) отчетливо виден на нашей картинке.
С помощью наших переходных вероятностей также можно сконструировать равновесную динамику Б 5' + 1 н-> К или
Б ь-> 5 — 1 н-> Б. При этом динамика будет получаться существенно разной в зависимости от того, в каком порядке мы будет делать последовательное обновление. Упомянем здесь только два из множества возможных вариантов.
1. Сначала делаем шаг 51 и й + 1, а затем шаг Б >—> 5 — 1. В обоих случаях используем последовательное обновление от ^ = 0 до ^ = Т.
2. Сначала делаем шаг 5 >—> 5+1, используя последовательное обновление от t = 0 до t = Т; затем шаг 5 н-> 5 — 1, используя последовательное обновление от ^ = Т до t = 0.
На рис. 6 показана эволюция замощения “заполненный ящик” при последней из приведенных динамик. Здесь N = 50, Т = 50, 5 = 20.