WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

На правах рукописи

УДК 519.217

Петров Леонид Александрович

МАРКОВСКИЕ ЦЕПИ НА РАЗБИЕНИЯХ

И БЕСКОНЕЧНОМЕРНЫЕ ДИФФУЗИОННЫЕ ПРОЦЕССЫ

Специальность 05.13.17 – теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2010 г.

Работа выполнена в Институте Проблем Передачи Информации им.

А.А. Харкевича РАН.

Научный руководитель – доктор физико-математических наук Г.И. Ольшанский

Официальные оппоненты – доктор физико-математических наук Г.А. Кошевой, доктор физико-математических наук С.А. Пирогов

Ведущая организация – Санкт–Петербургское отделение Математического института им.

В.А. Стеклова РАН

Защита состоится на заседании диссертационного совета Д.002.077.01 при ИППИ РАН по адресу: 127994, г. Москва, ГСП-4, Большой Каретный переулок, 19, стр.1, конференц–зал.

С диссертацией можно ознакомиться в библиотеке ИППИ РАН.

Автореферат разослан.

Ученый секретарь диссертационного совета Д.002.077.01 при ИППИ РАН доктор физико-математических наук, доцент И.И. Цитович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В последние несколько лет в области машинного обучения без учителя активно развиваются методы анализа и классификации по темам большого корпуса текстов на естественном языке, основанные на непараметрических байесовских моделях (см., например, работы2,3,4, а также обширную библиографию в последней работе). Многие вероятностные модели, рассматриваемые в связи с этими задачами, основаны на распределениях Пуассона–Дирихле. Вероятностные распределения Пуассона–Дирихле зависят от двух параметров 0 < и > и описывают закон распределения последовательности невозрастающих неотрицательных случайных величин с суммой единица. В исследование распределений Пуассона–Дирихле внесли вклад Бертуан, Биллингсли, Блиновский, Вершик, Гончаров, Гримметт, Гриффитс, Дикман, Доннелли, Игнатов, Йор, Карлтон, Керов, Куртц, Кингман, Ллойд, Ольшанский, Питман, Уоттерсон, Цилевич, Шепп, Шмидт, Этье, Ювенс, и другие. Более подробно о распределениях Пуассона–Дирихле см. недавнюю монографию5. Однопараметрическое семейство распределений Пуассона–Дирихле (соответствующее случаю = 0) было введено Кингманом (1975) в связи с задачами, возникающими в популяционной генетике. Двухпараметрическое обобщение принадлежит Питману (1992). Вероятностные модели машинного обучения, основанные на распределениях Пуассона–Дирихле, существенно используют специфику второго параПрикладная статистика: классификация и снижение размерности / С. Айвазян, В. Бухштабер, И. Енюков, Л. Мешалкин. — М.: Финансы и статистика, 1989. — 608 С.

Johnson, M., Griths, T., Goldwater, S. Adaptor grammars: A framework for specifying compositional nonparametric bayesian models // Advances in neural information processing systems. — 2007. — V. 19. — P. 641–649.

Teh, Y. A hierarchical Bayesian language model based on Pitman-Yor processes // Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics. — 2006. — P. 985–992.

4 Blei, D., Griths, T., Jordan, M. The nested chinese restaurant process and bayesian nonparametric inference of topic hierarchies // J. ACM. — 2010. — V. 57, № 2. — P. 1–30.

Feng, S. The Poisson-Dirichlet Distribution and Related Topics. — Springer, 2010. — 216 P.

метра. Это связано с тем, что случайные величины в последовательности, имеющей распределение Пуассона–Дирихле, при = 0 с вероятностью единица убывают показательным образом, а при 0 — степенным образом; как известно, для естественных языков характерно степенное убывание частот (см., например, работу6 ).

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

Использование распределений Дирихле приводит к ограничениям на число возможных тем в задаче классификации. Поэтому возникает потребность в динамических моделях (связанных с двухпараметрическими распределениями Пуассона–Дирихле), которые могли бы снять это ограничение.

Динамические модели, связанные с однопараметрическим семейством распределений Пуассона–Дирихле, широко изучались в контексте популяционной генетики. Изучение динамических моделей в популяционной генетике началось с дискретных моделей Райта–Фишера (рассматривалась, начиная с 1920-30-х гг.) и Морана (была введена в 1950-е гг.). Эти модели можно трактовать как последовательности марковских цепей на разбиениях (пространство состояний n-й цепи есть множество всех разбиений числа n).



Разбиения — фундаментальный математический объект. Основные сведения о них можно найти в книге Стенли8. Разбиения широко применяются в теоретической информатике, например, в различных методах сортировки (в частности, при сортировке слияниями), которым посвящена фундаментальная монография Кнута9.

Предельное поведение некоторых классов моделей Райта–Фишера и Морана исследовано в работе Этье и Куртца10, в которой построено семейство бесконечномерных диффузионных процессов, сохраняющих однопараметричеШрейдер, Ю. О возможности теоретического вывода статистических закономерностей текста (к обоснованию закона Ципфа) // Проблемы передачи информации. — 1967. — Т. 3, № 1. — С. 57–63.

Wang, C., Blei, D., Heckerman, D. Continuous time dynamic topic models // Uncertainty in Articial Intelligence [UAI]. — 2008.

Стенли, Р. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции. — М.: Мир, 2005. — 767 С.

Кнут, Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. — СПб.: Вильямс, 2000. — 824 С.

Ethier, S. N., Kurtz, T. G. The Innitely-Many-Neutral-Alleles Diusion Model // Advances in Applied Probability. — 1981. — V. 13, № 3. — P. 429–452.

ские распределения Пуассона–Дирихле. Построенные процессы исследовались и обобщались в работах, принадлежащих Вио, Доннелли, Гриффитс, Куртц, Таваре, Уоттерсон, Флеминг, Шмуланд, Этье, и др.

Для построения бесконечномерных диффузионных процессов Этье и Куртц использовали их аппроксимацию конечномерными диффузиями на симплексах растущей размерности. Данный метод неприменим в случае двухпараметрических распределений Пуассона–Дирихле. Поэтому для построения бесконечномерных диффузий, обобщающих процессы Этье–Куртца10 на двухпараметрический случай, требуется применение других методов. В диссертации найдена алгебро-комбинаторная интерпретация модели Морана на разбиениях, которая позволяет обобщить эту модель на двухпараметрический случай, а также построить диффузии, сохраняющие двухпараметрические распределения Пуассона–Дирихле.

Алгебро-комбинаторная интерпретация модели Морана включает её (и её двухпараметрическое обобщение) в широкий класс марковских цепей на разбиениях, рассматриваемый Фульманом, Бородиным и Ольшанским (см., например, работу11 ). Возникает вопрос об анализе асимптотического поведения других марковских цепей на разбиениях, входящих в этот класс. В диссертации проводится исследование одного семейства марковских цепей из этого класса на строгих разбиениях (то есть, разбиениях, все части которых различны). О некоторых приложениях строгих разбиений в теоретической информатике (в задачах сортировки) см., например, монографию Кнута9. Соответствие Робинсона–Шенстеда–Кнута для обычных разбиений9 обобщается и на случай строгих разбиений12. Это комбинаторное соответствие делает возможным применение различных ансамблей случайных разбиений в задачах, связанных со случайными матрицами, а также в теории массового обслуживания (см., например, работу13 ). Модель марковских цепей на строгих разбиениях возникает в связи с ансамблем случайных строгих разбиений, введенном Бородиным14.

Этот ансамбль связан с теорией проективных представлений симметрических Borodin, A., Olshanski, G. Innite-dimensional diusions as limits of random walks on partitions // Prob. Theor. Rel. Fields. — 2009. — V. 144, № 1. — P. 281–318.

Sagan, B. Shifted tableaux, Schur Q-functions, and a conjecture of Stanley // J. Comb. Theo. A. — 1987. — V. 45. — P. 62–103.

Baryshnikov, Y. GUEs and queues // Probability Theory and Related Fields. — 2001. — V. 119, № 2. — P. 256–274.

Бородин, А. Мультипликативные центральные меры на графе Шура // Зап. научн. сем. ПОМИ. — 1997. — Т. 240. — С. 44–52.

групп (эта теория развивалась в работах Иванова, Назарова, Сергеева, Стембриджа, Шура, и др.). Стоит отметить, что этот ансамбль приводит к новым моделям точечных процессов, которые отличаются от традиционно рассматриваемых в статистической физике. Изучение предельного поведения указанных марковских цепей на строгих разбиениях позволяет построить новые примеры бесконечномерных диффузионных процессов.

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

Научная новизна. В диссертации построены новые примеры бесконечномерных диффузионных процессов, среди которых — семейство процессов, сохраняющих двухпараметрические распределения Пуассона–Дирихле. Данные процессы могут использоваться в динамических задачах классификации в тех моделях машинного обучения, где ранее использовались распределения Дирихле. Кроме того, введены и исследованы новые примеры марковских цепей на разбиениях, в пределе приводящие к указанным бесконечномерным диффузионным процессам.

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

Теоретическая и прикладная ценность. Диссертация носит теоретический характер. Полученные результаты могут найти применение в теоретической информатике, теории машинного обучения (в динамических задачах классификации), непараметрической байесовской статистике, популяционной генетике, комбинаторике и теории случайных процессов. Некоторые из полученных в диссертации результатов имеют продолжение в недавних работах Фенга и Саи Руггиеро и Уолкера 16.

Апробация работы. Результаты диссертации неоднократно докладывались автором на семинаре «Комбинаторные и вероятностные аспекты теории представлений» (Независимый Московский Университет, руководитель — д.ф.-м.н., г.н.с. Г.И. Ольшанский), на семинаре Добрушинской математической лаборатории (ИППИ РАН, 2010 г., руководитель — профессор Р.А. Минлос), на семинаре «Теория вероятностей и эргодическая теория» (МГУ, 2007 и 2010 гг., руководители — профессор Б.М. Гуревич, профессор В.И. Оселедец, доцент С.А. Пирогов), на семинаре «Математические модели в биологии» (МГУ, 2007 г., руководитель — профессор В.А. Малышев), на петербургском семинаре по теории представлений и динамическим системам (ПОМИ РАН, 2008 г., руководитель — профессор А.М. Вершик), на семинаре «Асимптотический анализ случайных процессов и полей» (МГУ, 2008 г., руководители — профессор А.В. Булинский и доцент А.П. Шашкин), на международной школе «Large N Limits» (Биш, Франция, 2008 г.), на международной школе Тихоокеанского Института Математических Наук и Университета Британской Колумбии (Ванкувер, Канада, г.).

Публикации. Основные результаты диссертации опубликованы в 3 статьях автора в научных журналах, входящих в перечень ВАК. Список работ приведен в конце автореферата.

Структура диссертации. Диссертация состоит из введения, двух глав, заключения и списка литературы, насчитывающего 93 наименования. В текст включены 5 рисунков. Общий объем работы составляет 103 страницы.

Feng, S., Sun, W. Some diusion processes associated with two parameter Poisson–Dirichlet distribution and Dirichlet process // Probability Theory and Related Fields. — 2009.

Ruggiero, M., Walker, S. Countable representation for innite dimensional diusions derived from the two-parameter Poisson-Dirichlet process // Electronic Communications in Probability. — 2009. — V. 14. — P. 501–517.

КРАТКОЕ

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

В первом параграфе приводятся необходимые сведения о разбиениях и распределениях Пуассона–Дирихле. Приводится определение модели Морана на разбиениях и дается ее алгебро-комбинаторная интерпретация, а также вводится двухпараметрический аналог модели Морана.

Под разбиением понимается невозрастающая последовательность неотрицательных целых чисел = (1, 2,..., ), в которой лишь конечное число ненулевых компонент (это число обозначается ()). Число = i назы- i= вается весом разбиения. Разбиения обозначаются буквами,,,.... Пусть Kn — множество разбиений веса n Z0 = {0, 1, 2,... } (множество K0 состоит из пустого разбиения ), и K = Kn — множество всех разбиений.

Разбиения изображаются диаграммами Юнга (см., например, гл. I книги Макдональда17 ), мы отождествляем эти два объекта и обозначаем их одинаково.

Если диаграмма получена из диаграммы путем добавления одной клетки, то это обозначается (или, эквивалентно, ). Это возможно только если обозначается через [m]. Для всех m N = {1, 2,... } если в диаграмме есть строка длины m, то диаграмма [m] определяется единственным образом, а если в нет такой строки, считаем, что [m] не определено. Через [ k] (k N) обозначим число компонент в разбиении, равных k. Это неотрицательное целое число.

Определение 1.1.1. Пусть, — разбиения и. Переходной функцией вниз называется величина p (, ) = i [i ], где = (1,..., ) и Макдональд, И. Симметрические функции и многочлены Холла. / — Москва, Мир, 1984. — 221 С.

Для всех разбиений Kn (где n N) выполнено Kn1 p (, ) = 1.

Поэтому ограничение p на Kn Kn1 (обозначаемое через p n,n1 ) является марковским переходным ядром.

Определение 1.1.3. Семейство {Mn }, где Mn — вероятностная мера на Kn, называется структурой разбиений, если оно согласовано с переходной функцией вниз: Kn+1 Mn+1 ( )p (, ) = Mn () для всех n Z0 и Kn, где Mn ( ) обозначает меру одноточечного множества { }.

Рассмотрим вложения n Kn, при которых разбиение = (1,..., ) переходит в точку симплекса 1,...,, 0, 0,....

Теорема 1.1.4. (Кингман) Структуры разбиений {Mn } находятся во взаимно-однозначном соответствии с вероятностными мерами P на. Мера P получается как слабый предел мер n (Mn ) при n, и обратно, меры {Mn } можно восстановить по P с помощью определенной процедуры случайной выборки.

Определение 1.1.5. Пусть 0 < 1 и >. Рассмотрим следующее семейство вероятностных мер Mn на Kn :

Здесь — число ненулевых компонент в, а ()n = ( + 1)... ( + n 1) — символ Похгаммера. Это действительно семейство вероятностных мер. Кроме того, меры {Mn } образуют структуру разбиений. Она была введена Ювенсом при = 0 и обобщена Питманом на случай > 0.

Определение 1.1.6. Вероятностные меры на, соответствующие (в смысле теоремы 1) структурам разбиений {Mn }, называются распределениями Пуассона–Дирихле и обозначаются PD(, ).

Перейдем к описанию модели Морана и ее алгебро-комбинаторной интерпретации. Пусть {Mn } — структура разбиений, такая, что Mn () > 0 для всех Определение 1.1.7. Переходной функцией вверх для, K, таких, что, называется величина p (, ) = Mn+1 ( ) p (, ), где n = и p — переходная функция вниз. Если неверно, что, положим p (, ) = 0.

Переходная функция вверх уже зависит от выбора структуры разбиений.

Ограничение p на Kn Kn+1 (обозначаемое через p n,n+1 ) является марковским переходным ядром. Семейство мер {Mn } согласовано с p, то есть, Определение 1.1.8. Пусть переходная функция вверх p построена по структуре разбиений {Mn } (здесь = 0). Рассмотрим последовательность марковских цепей на Kn (n N) с переходными операторами Morann = p n1,n pn,n1, или, подробнее, Morann (, ) = Kn1 p (, )p (, ). Данная последовательность марковских цепей называется однопараметрической моделью Морана.

Модель Морана используется для моделирования динамики популяции с постоянным числом особей под воздействием процессов воспроизводства и мутации (интенсивность мутации регулируется параметром > 0), при этом разбиение описывает распределение типов особей в популяции (1 — число особей самого частого типа, и т.д.). Предельное поведение модели Морана описано в Из данного определения модели Морана видна ее алгебро-комбинаторная интерпретация. В общем двухпараметрическом случае удобнее использовать несколько другие марковские цепи. При = 0 их предельное поведение совпадает с поведением модели Морана. Приведем общее определение из работы Определение 1.1.10. Пусть {Mn } — структура разбиений, такая, что Mn () > 0 для всех n Z0 и Kn. Марковская цепь на Kn с переходным n+1,n pn,n+1 называется марковской цепью вверх/вниз.

Мера Mn является инвариантной для марковской цепи вверх/вниз на Kn, и цепь обратима относительно этой меры. Пусть Tn обозначает переходный оператор n-й марковской цепи вверх/вниз, построенной по структуре разбиений Ювенса–Питмана {Mn }. Ставится вопрос об изучении предельного поведения марковских цепей Tn при n.

Во втором параграфе вычисляется действие операторов Tn на симметрические функции от компонент разбиений.

Определение 1.2.1. Пусть y1, y2,... — формальные переменные. Алгебра симметрических функций состоит из всех формальных степенных рядов от y1, y2,..., которые симметричны по y1, y2,... и имеют ограниченную степень (то есть, степени всех мономов в формальном степенном ряде равномерно ограничены). Максимальная степень монома называется степенью симметрической функции.

Алгебра свободно порождена (как коммутативная алгебра с единицей) суммами Ньютона pk = yi, k N. Мономиальные функции определяются как m = i1,...,i yi11... yi, где = (1,..., ) K и сумма ведется по всем наборам попарно различных индексов i1,..., i 1. Факториальные аналоги функций m (обозначаемые m ) получаются из обычных функций заменой каждой степени yi на факториальную степень yi = yi (yi 1)... (yi k + 1).

Каждая из систем функций {m } и {m } (где пробегает все разбиения) является линейным базисом алгебры.

Отождествим (абстрактную) алгебру симметрических функций с алгеброй симметрических функций на разбиениях, полагая pk () = i=1 i, k N.

Алгебра симметрических функций на множестве K разделяет точки. Пусть f. Через fn обозначим ограничение функции f на подмножество Kn K.

Так как Kn конечно, то пространство всех функций на Kn (обозначаемое Fun(Kn )) исчерпывается функциями вида fn, где f. Переходный оператор Tn действует в пространстве Fun(Kn ) и однозначно определяется своим действием на симметрические функции (m )n. Это действие дается следующей теоремой.

Теорема 1.2.2. Пусть n N. Для всех разбиений имеем Здесь 1 обозначает тождественный оператор.

Отметим, что если в разбиении нет части, равной m (здесь m N), то [ m] = 0, и слагаемого с [m] не возникает. В частности, выше сумма по i фактически конечна.

В третьем параграфе для всех значений параметров 0 < 1 и > устанавливается сходимость марковских цепей Tn к диффузионному процессу X, (t) на, который сохраняет меру Пуассона–Дирихле PD(, ). Исследуются некоторые важные свойства полученных процессов.

Бесконечномерный симплекс — компактное пространство в топологии покоординатной сходимости. Через C() обозначим банахову алгебру всех непрерывных функций на с поточечными операциями и супремум-нормой. Рассмотрим плотную подалгебру F C(), порожденную (как коммутативная алгебра с единицей) алгебраически независимыми функциями qk (x) = xk+1, k N, x. Отметим, что функция xi не является непрерывной на. Ясi= но, что F (p1 1), где (p1 1) — идеал в алгебре, порожденный p1 1.

Пусть n C() Fun(Kn ) — соответствующие вложениям n Kn проекции пространств функций, то есть, (n g)() = g(n ()), Kn, g C().

Теорема 1.3.4. Существует оператор A F F, такой, что при n операторы n2 (Tn 1) сходятся к A в алгебре F. Более формально, Оператор A может быть записан как формальный дифференциальный оператор в коммутативной алгебре полиномов от q1, q2,... :

а также как дифференциальный оператор в естественных координатах:

Оператор A, записанный в естественных координатах, может применяться только к функциям g F. Чтобы применить его к такой функции, следует сначала вычислить Ag(x) для тех x, для которых xi = 1 (такие x составляют плотное подмножество в ) путем применения правой части к функции g(x) напрямую, а затем продолжить полученную функцию на весь симплекс по непрерывности.

Теорема 1.3.9. (1) Оператор A замыкаем в C(), и его замыкание порождает сильно непрерывную полугруппу сжимающих операторов {T (t)}t в C(), которая сохраняет положительность и единицу. Дискретные полугруппы 1, Tn, Tn,... сходятся к непрерывной {T (t)}:

причем эта сходимость равномерна на конечных интервалах по t.

(2) Для всех значений параметров полугруппа {T (t)} является полугруппой строго марковского процесса X, (t) на, который может начинаться с любой точки и любого вероятностного распределения.

(3) Процесс X, (t) на симплексе сохраняет распределение Пуассона–Дирихле PD(, ). Это единственная инвариантная мера процесса, он обратим и эргодичен относительно нее.

(4) Будем считать, что X, (t) и все марковские цепи вверх/вниз Tn начинаются с инвариантного распределения. Тогда при n все конечномерные распределения цепей Tn сходятся к конечномерным распределениям процесса X, (t), если сделать масштабное преобразование времени, при котором один шаг n-й марковской цепи соответствует малому интервалу времени порядка 1 n2.

(5) Траектории процесса X, (t) непрерывны с вероятностью единица.

(6) Спектр генератора процесса X, (t) в L2, PD(, ) имеет следующий вид: {0} {m(m 1 + ) m = 2, 3,... }. Собственное значение 0 простое, а кратность m-го равна числу разбиений веса m без единичных частей, то есть, числу решений уравнения 2r2 + 3r3 + = m в неотрицательных целых числах.

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

В первом параграфе устанавливаются новые комбинаторные свойства строгих разбиений, приводится определение семейства мер Бородина на строгих разбиениях и определяются соответствующие цепи вверх/вниз.

Под строгим понимается разбиение, все части которого различны. Строгое разбиение можно изобразить сдвинутой диаграммой Юнга, которая получается из обычной диаграммы Юнга этого разбиения сдвигом каждой i-й строки на (i1) клеток вправо, см. §7 главы III в книге Макдональда17. Строгие разбиения отождествляются со сдвинутыми диаграммами Юнга и обозначаются одинаково буквами, µ,,.... Через Sn Kn обозначим множество строгих разбиений веса n Z0, а через S = Sn — множество всех строгих разбиений. Если сдвинутая диаграмма получена из сдвинутой диаграммы µ путем добавления одной клетки, то это обозначается µ (или, эквивалентно, µ). Пусть эта клетка добавляется к строке в µ, которая (до добавления) имеет длину x Z (случай x = 0 соответствует добавлению к µ новой строки). Тогда обозначается через µ + (x). Эквивалентно, µ обозначается через [x].

Пусть — сдвинутая диаграмма Юнга. Через X() обозначим множество тех x Z0, для которых существует диаграмма +(x). Аналогично через Y () обозначим множество тех y Z0, для которых существует диаграмма [y].

Если диаграммы + (x) и [y] существуют, то они определяются единственным образом. Считаем, что элементы множеств X() и Y () перечислены в возрастающем порядке.

Определение 2.1.1. Числа [X(); Y ()] называются координатами Керова сдвинутой диаграммы (или, что то же самое, строгого разбиения ).

Координаты Керова сдвинутых диаграмм Юнга аналогичны перемежающимся координатам обычных диаграмм Юнга, введенным Керовым Предложение 2.1.2. (свойства координат Керова сдвинутых диаграмм) (1) Координаты Керова [X(); Y ()] однозначно определяют сдвинутую диаграмму Юнга.

(2) Если содержит строку длины 1, то для некоторого d 1 выполнено Если не содержит строки длины 1, то для некоторого d 0 выполнено (3) Для всех выполнено xX() x(x + 1) yY () y(y + 1) = 2.

Положим X () = X() {0}. Легко видеть, что в X () и в Y () всегда одинаковое число элементов.

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

Пусть S, 1, и v — комплексная переменная. Рассмотрим следующую функцию и ее разложение в сумму простейших дробей:

Определение 2.1.3. Пусть, µ S и µ. Это значит, что µ = [y] для некоторого y Y (). Число 2 называется переходной функцией вниз и обозначается через p (, µ).

Ограничение p на Sn Sn1 является марковским переходным ядром и обозначается pn,n1. Переходная функция вниз p возникла при анализе ветвления проективных представлений симметрических групп. Первоначально (например, в 14 ) она определялась без использования перемежающихся координат сдвинутых диаграмм.

Определение 2.1.5. Семейство вероятностных мер {Mn на Sn } называется когерентным, если оно согласовано с переходной функцией вниз, то есть, Sn+1 Mn+1 ()p (, ) = Mn () для всех n Z0 и Sn.

Для когерентных семейств {Mn на Sn } существует предельная теорема, аналогичная теореме Кингмана для структур разбиений. Эта теорема, установКеров, С. Анизотропные диаграммы Юнга и симметрические функции Джека // Функц. анализ и его прил. — 2000. — Т. 34, № 1. — С. 51–64.

ленная Назаровым, дает взаимно-однозначное соответствие между когерентными семействами {Mn } и вероятностными мерами P на. При этом P получается как слабый предел мер n (Mn ) на (при n ), где вложения n Sn Определение 2.1.6.14 Пусть a > 0 — параметр. Рассмотрим следующее семейство вероятностных мер на Sn :

Через Wn, n N, обозначим переходный оператор марковской цепи вверх/вниз на Sn, построенной по семейству {Mn }. Ставится вопрос об исa следовании предельного поведения марковских цепей Wn при n +.

Во втором параграфе проводится основное техническое вычисление действия переходных операторов Wn в алгебре дважды симметрических функций.

При этом широко используются установленные в первом параграфе комбинаторные свойства строгих разбиений.

Определение 2.2.1. Алгеброй дважды симметрических функций называется подалгебра = R [p1, p3,... ], порожденная суммами Ньютона с нечетными номерами. В алгебре можно ввести фильтрацию, полагая deg p2k+1 = 2k + 1, k N. Говорят, что оператор R имеет степень r, где r Z, если для всех f выполнено deg(Rf ) deg f + r.

Алгебру можно рассматривать как алгебру функций на строгих разбиениях, полагая p2k+1 () = i=1 2k+1, S, k N. Для f обозначим через fn сужение f на подмножество Sn S. Алгебра разделяет точки множества S, поэтому конечномерное пространство Fun(Sn ) всех функций на Sn исчерпывается функциями вида fn, где f.

Теорема 2.2.29. Существует единственный оператор B, такой, что (n+a 2)(n+1) Wn 1 fn = (Bf )n для всех f. Степень оператора B равна нулю, и он имеет вид В третьем параграфе для всех a > 0 устанавливается сходимость марковских цепей вверх/вниз Wn к бесконечномерному диффузионному процессу Xa (t) на, а также исследуются некоторые свойства этого процесса. Исследование сходимости цепей Wn и полученных диффузионных процессов во многом аналогично случаю, рассмотренному в главе 1.

Пусть алгебра G C() порождена функциями qk (x) с четными номерами.

Отображение F (p1 1) в ограничении на дает G (p1 1).

Теорема 2.3.3. Существует оператор B G G, такой, что при n операторы n2 (Wn 1) сходятся к B в алгебре G (определение сходимости такое же, как в теореме 3). Он может быть записан как оператор в алгебре полиномов от q2, q4,... :

Теорема 2.3.5. (1) Оператор B замыкаем в C(), и его замыкание порождает сильно непрерывную полугруппу сжимающих операторов {W (t)}t в C(), которая сохраняет положительность и единицу. Дискретные полугруппы 1, Wn, Wn,... сходятся к непрерывной {W (t)}, причем эта сходимость равномерна на конечных интервалах по t.

(2) Для всех значений параметра a > 0 полугруппа {W (t)} является полугруппой строго марковского процесса Xa (t) на, который может начинаться с любой точки и любого вероятностного распределения.

(3) Процесс Xa (t) на симплексе сохраняет вероятностную меру P (a). Это единственная инвариантная мера процесса, он обратим и эргодичен относительно нее.

(4) Марковские цепи вверх/вниз на Sn, построенные по {Mn }, сходятся к Xa (t) аналогично п.(4) теоремы 4.

(5) Траектории процесса Xa (t) непрерывны с вероятностью единица.

(6) Спектр генератора процесса Xa (t) в L2, P (a) имеет следующий вид:

{0}{m(m 1 + a 2) m = 2, 3,... }. Собственное значение 0 простое, а кратность m-го равна числу разбиений m на нечетные слагаемые, большие единицы.

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

1. Дана алгебро-комбинаторная интерпретация однопараметрической классической модели Морана и построено ее обобщение на двухпараметрический случай.

2. Доказана сходимость последовательности марковских цепей на разбиениях (двухпараметрического аналога модели Морана) к бесконечномерным диффузионным процессам, которые сохраняют двухпараметрические распределения Пуассона–Дирихле.

3. Введены перемежающиеся координаты строгих разбиений и исследованы их важные комбинаторные и алгебро-комбинаторные свойства.

4. Установлена сходимость марковских цепей на строгих разбиениях (связанных с ансамблем Бородина случайных строгих разбиений14 ) к бесконечномерным диффузионным процессам.

5. Исследованы такие свойства построенных семейств бесконечномерных диффузионных процессов, как явный вид предгенератора процесса, структура его спектра, и др.

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Л.А. Петров, Двухпараметрическое семейство бесконечномерных диффузий на симплексе Кингмана, Функциональный анализ и его приложения, 2009, 43(4), 45–66.

[2] Л.А. Петров, Предельное поведение некоторых случайных блужданий на строгих разбиениях, Успехи математических наук, 2009, 64(6), 177–178.

[3] Л.А. Петров, Случайные блуждания на строгих разбиениях, Записки научных семинаров ПОМИ, 2009, 373, 226–272.





Похожие работы:

«ЗАЛЕНСКАЯ Наталья Самуиловна СПЕЦИФИКА ФИЛОСОФСКОЙ АРГУМЕНТАЦИИ Специальность: 09.00.01 – онтология и теория познания АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата философских наук Тюмень 2011 Работа выполнена на кафедре культурологии ФГБОУ ВПО Тюменская государственная академия культуры, искусств и социальных технологий. доктор философских наук, профессор Научный руководитель : Селиванов Федор Андреевич доктор философских наук, профессор Официальные оппоненты...»

«Ткачев Александр Иванович ВОЗВРАЩЕНИЕ УГОЛОВНОГО ДЕЛА ПРОКУРОРУ СО СТАДИИ ПОДГОТОВКИ К СУДЕБНОМУ ЗАСЕДАНИЮ 12.00.09 – уголовный процесс, криминалистика и судебная экспертиза; оперативно-розыскная деятельность Автореферат диссертации на соискание ученой степени кандидата юридических наук Томск–2007 2 Работа выполнена в государственном образовательном учреждении высшего профессионального образования Томский государственный университет на кафедре уголовного процесса,...»

«Антипина Любовь Юрьевна ИССЛЕДОВАНИЕ ПРОЦЕССОВ БИОЛЮМИНЕСЦЕНЦИИ Са2+-РЕГУЛИРУЕМОГО ФОТОПРОТЕИНА ОБЕЛИНА Специальность 01.04.07 физика конденсированного состояния АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Красноярск 2010 Работа выполнена в Институте физики им. Л.В. Киренского СО РАН Научный руководитель : доктор физико-математических наук, профессор, Овчинников Сергей Геннадьевич Официальные оппоненты : доктор...»

«Селиванова Татьяна Игоревна ГЕОГРАФИЧЕСКИЕ ОСОБЕННОСТИ ГОРОДCКОГО АГЛОМЕРИРОВАНИЯ В ПОСТСОВЕТСКОЙ РОССИИ Специальность 25.00.24 – Экономическая, социальная, политическая и рекреационная география АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата географических наук Москва - 2011 Работа выполнена в Учреждении Российской академии наук Институте географии РАН Научный руководитель : доктор географических наук, профессор Полян Павел Маркович Официальные оппоненты :...»

«ГРЕБНЕВ АЛЕКСЕЙ ВЛАДИМИРОВИЧ УЛУЧШЕНИЕ ЭФФЕКТИВНЫХ ПОКАЗАТЕЛЕЙ ДИЗЕЛЯ С ПРОМЕЖУТОЧНЫМ ОХЛАЖДЕНИЕМ НАДДУВОЧНОГО ВОЗДУХА 4ЧН 11,0/12,5 ПРИ РАБОТЕ НА ПРИРОДНОМ ГАЗЕ ПУТЕМ СОВЕРШЕНСТВОВАНИЯ ПРОЦЕССОВ СГОРАНИЯ И ТЕПЛОВЫДЕЛЕНИЯ Специальность 05.04.02 – Тепловые двигатели Автореферат диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург 2009 2 Работа выполнена в ФГОУ ВПО Вятская государственная сельскохозяйственная академия Научный руководитель : доктор...»

«БУХАРБАЕВА АСИЯ РАДОЛЕВНА Политическая коммуникация в условиях легитимации и делегитимации власти в современной России Специальность 23.00.02 – Политические институты, процессы и технологии АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата политических наук Москва – 2013 2 Диссертация выполнена на кафедре политологии и политического управления Факультета государственного управления Федерального государственного бюджетного образовательного учреждения высшего...»

«РАХИМОВА МУБАШИРХОН КОМПЛЕКСООБРАЗОВАНИЕ ИОНОВ Fe, Co, Mn и Cu С ОДНО- И МНОГООСНОВНЫМИ ОРГАНИЧЕСКИМИ КИСЛОТАМИ, НЕЙТРАЛЬНЫМИ ЛИГАНДАМИ В ВОДНЫХ РАСТВОРАХ 02.00.04 – физическая химия 02.00.01 - неорганическая химия АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора химических наук Душанбе 2013 2 Работа выполнена в лаборатории Физическая химия гомогенных равновесий им. Х. М. Якубова научно-исследовательского института и на кафедре физической и коллоидной химии...»

«Парыгина Наталья Александровна ГЕНДЕРНЫЙ АСПЕКТ НАСИЛИЯ В СОЦИАЛЬНОМ ИЗМЕРЕНИИ 22.00.04 – Социальная структура, социальные институты и процессы Автореферат диссертации на соискание ученой степени кандидата социологических наук Хабаровск – 2009 Работа выполнена в Государственном образовательном учреждении высшего профессионального образования Тихоокеанский государственный университет Научный руководитель кандидат социологических наук, доцент Лях Павел Петрович Официальные...»

«Кузин Павел Вячеславович ПОВЫШЕНИЕ ДОЛГОВЕЧНОСТИ ПЛУНЖЕРНЫХ ПАР ТОПЛИВНОЙ АППАРАТУРЫ ДИЗЕЛЕЙ ПУТЕМ СОВЕРШЕНСТВОВАНИЯ ОЧИСТКИ ТОПЛИВА ОТ ВОДЫ Специальность 05.20.03 – Технологии и средства технического обслуживания в сельском хозяйстве АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Саратов 2012 Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Саратовский государственный...»

«ГНЕЗДИЛОВА Светлана Александровна МЕТОДЫ И СРЕДСТВА АВТОМАТИЗАЦИИ ТЕХНОЛОГИЧЕСКОЙ ПОДГОТОВКИ ВИРТУАЛЬНОГО ПРЕДПРИЯТИЯ ИНСТРУМЕНТАЛЬНОГО ПРОИЗВОДСТВА Специальность 05.11.14 – Технология приборостроения АВТОРЕФЕРАТ диссертации на соискание учной степени кандидата технических наук Санкт-Петербург -2013 2 Работа выполнена на кафедре Технологии приборостроения СанктПетербургского национального университета информационных технологий, механики и оптики. Научный руководитель : Падун...»

«ДУДУКИНА Дарья Александровна А.Н.Бекетов (1862–1941). Творческая деятельность и вклад в развитие архитектуры юга России и Украины конца XIX – первой трети XX веков 18.00.01 – Теория и история архитектуры, реставрация и реконструкция историко-архитектурного наследия Автореферат диссертации на соискание ученой степени кандидата архитектуры Москва Работа выполнена в Московском...»

«Никоноров Василий Владимирович ПОЛУЧЕНИЕ ГИДРОГЕЛЕЙ ХИТОЗАНА, МОДИФИЦИРОВАННОГО ДИАЛЬДЕГИДАМИ, С ИСПОЛЬЗОВАНИЕМ ТЕХНОЛОГИИ КРИОТРОПНОГО ГЕЛЕОБРАЗОВАНИЯ Специальности: 05.17.06 – Технология и переработка полимеров и композитов 02.00.06 – Высокомолекулярные соединения АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата химических наук Москва – 2010 www.sp-department.ru Работа выполнена на кафедре аналитической, физической и коллоидной химии Государственного...»

«Прохоров Кирилл Вячеславович РАЗВИТИЕ СИСТЕМЫ ОРГАНОВ ИСПОЛНИТЕЛЬНОЙ ВЛАСТИ В РОССИЙСКОЙ ФЕДЕРАЦИИ: КОНСТИТУЦИОННО-ПРАВОВОЕ ИССЛЕДОВАНИЕ Специальность 12.00.02 – конституционное право; муниципальное право Автореферат диссертации на соискание ученой степени кандидата юридических наук Москва 2012 Работа выполнена на кафедре публичного права ФГБОУ ВПО Российский государственный гуманитарный университет. Научный руководитель : доктор юридических наук, профессор Лапина Марина...»

«КАПШУТАРЬ Марина Анатольевна АКСИОЛОГИЗАЦИЯ СОЦИАЛЬНО-ГУМАНИТАРНОГО ОБРАЗОВАНИЯ СТАРШЕКЛАССНИКОВ НА ОСНОВЕ ЛИЧНОСТНО-РАЗВИВАЮЩЕГО ОБУЧЕНИЯ 13.00.01 – общая педагогика, история педагогики и образования АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата педагогических наук Екатеринбург – 2006 Работа выполнена в ГОУ ВПО Уральский государственный университет имени А.М. Горького на кафедре педагогики Научный руководитель : доктор педагогических наук, профессор Дудина...»

«Флоринский Игорь Васильевич ТЕОРИЯ И ПРИЛОЖЕНИЯ МАТЕМАТИКО-КАРТОГРАФИЧЕСКОГО МОДЕЛИРОВАНИЯ РЕЛЬЕФА Специальность 25.00.33 – картография АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук Москва – 2010 Работа выполнена в Учреждении Российской академии наук Институте математических проблем биологии РАН Официальные оппоненты : доктор технических наук, старший научный сотрудник Флегонтов Александр Валентинович доктор технических наук, профессор Лисицкий...»

«Ахманов Олег Юрьевич ЖАНРОВАЯ СТРАТЕГИЯ ДЕТЕКТИВА В ТВОРЧЕСТВЕ ПИТЕРА АКРОЙДА Специальность 10.01.03 – Литература народов стран зарубежья (английская литература) Автореферат диссертации на соискание ученой степени кандидата филологических наук Казань – 2011 Работа выполнена на кафедре русской, зарубежной литературы и методики преподавания ГОУ ВПО Татарский государственный гуманитарно-педагогический университет Научный руководитель : кандидат филологических наук, доцент...»

«ГАЛИМОВА ЭЛЬМИРА ИРЕКОВНА УПРАВЛЕНИЕ ДЕЯТЕЛЬНОСТЬЮ РОЗНИЧНОЙ ТОРГОВОЙ СЕТИ НА ОСНОВЕ ПРОЦЕССНО-ЛОГИСТИЧЕСКОГО ПОДХОДА Специальность 08.00.05-Экономика и управление народным хозяйством (1.6 Сфера услуг) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата экономических наук Москва 2013 Диссертация выполнена на кафедре экономики и управления на предприятии Казанского кооперативного института (филиала) автономной некоммерческой организации высшего профессионального...»

«УДК 316.47 Слинькова Татьяна Владимировна ВЗАИМОСВЯЗЬ ОБРАЗОВ ПАРТНЕРОВ И ВЗАИМООТНОШЕНИЙ В ДИАДНОМ ВЗАИМОДЕЙСТВИИ Специальность: 19.00.05 – социальная психология АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата психологических наук Санкт - Петербург 2002 г. Работа выполнена на кафедре психологии человека Российского государственного педагогического университета имени А.И. Герцена Научный руководитель : доктор психологических наук, профессор ПАНФЕРОВ В.Н....»

«Резниченко Анна Игоревна ГЕНЕЗИС И АРТИКУЛЯЦИОННЫЕ ФОРМЫ ЯЗЫКА РУССКОЙ ФИЛОСОФИИ (С.Л. ФРАНК, С.Н. БУЛГАКОВ, А.С. ГЛИНКА-ВОЛЖСКИЙ, П.П. ПЕРЦОВ, С.Н. ДУРЫЛИН): ИСТОРИКО-ФИЛОСОФСКИЙ АНАЛИЗ Специальность 09. 00. 03 – история философии АВТОРЕФЕРАТ ДИССЕРТАЦИИ НА СОИСКАНИЕ УЧЁНОЙ СТЕПЕНИ ДОКТОРА ФИЛОСОФСКИХ НАУК Москва 2013 2 Работа выполнена на кафедре истории отечественной философии философского факультета ФГБОУ ВПО Российский государственный гуманитарный университет Научный...»

«Кулакова Елена Александровна Россия в сочинении маркиза Лондондерри Воспоминания о путешествии на север Европы в 1836–1837 гг. Специальность 07.00.09 Историография, источниковедение и методы исторического исследования АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата исторических наук Санкт-Петербург 2011 Работа выполнена в Отделе источниковедения Санкт-Петербургского института истории РАН и на...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.