автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Марковские цепи на разбиениях и бесконечномерные диффузионные процессы

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

УДК 519.217

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

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 7 ИЮН 2010

Москва 2010 г.

004604133

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

Научный руководитель

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

Официальные оппоненты

доктор физико-математических наук Г.А. Кошевой,

доктор физико-математических наук С.А. Пирогов

Ведущая организация

Санкт-Петербургское отделение Математического института им. В.А. Стеклова РАН

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

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

Автореферат разослан ¿И— мая 2010 г.

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

И.И. Цитович

Общая характеристика работы

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

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

1 Прикладная статистика: классификация и снижение размерности / Айвазян С., Бухштабер В., Енюков И., Мешалкин Л. — М.: Финансы и статистика, 1989. — 608 С.

2Johiison, М., Griffiths, Т., Goldwater, S. Adaptor grammars: A framework for specifying compositional nonparametric bayesian models // Advances in neural information processing systems. — 2007.-V. 19,-P. 641-649.

3Teh, 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.

4Blei, D., Griffiths, Т., Jordan, M. The nested Chinese restaurant process and bayesian nonparametric inference of topic hierarchies // J. ACM. - 2010. - V. 57, № 2. - P. 1-30.

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

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

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

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

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

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

6Шрейдер Ю. О возможности теоретического вывода статистических закономерностей текста (к обоснованию закона Ципфа) // Проблемы передачи информации. — 1967. — Т. 3, № 1. — С. 57-63.

1Wang, С, Blei, D., Heckerman, D. Continuous time dynamic topic models // Uncertainty in Artificial Intelligence [UAI].-2008.

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

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

wEthier, S. N., Kurtz, Т. G. The Inflnitely-Many-Neutral-Alleles Diffusion Model II Advances in Applied Probability.- 1981.-V. 13, № 3.-P. 429-452.

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

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

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

11 Borodin, A., Olshanski, G. Infinite-dimensional diffusions as limits of random walks on partitions // Prob. Theor. Rel. Fields. - 2009. - V. 144, № 1. - P. 281-318.

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

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

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

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

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

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

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

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

на 15 и Руггиеро и Уолкера 16.

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

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

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

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

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

Краткое содержание диссертации

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

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

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

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

Под разбиением понимается невозрастающая последовательность неотрицательных целых чисел р - {р\,р2, ■ ■ ■, Ре), в которой лишь конечное число ненулевых компонент (это число обозначается ¿(р)). Число \р\ ■= рг называется весом разбиения. Разбиения обозначаются буквами р,(т,т,____Пусть К„

— множество разбиений веса п е Z>o := {0,1,2,...} (множество Ко состоит из пустого разбиения 0), и К := |_1~=0 К„ — множество всех разбиений.

Разбиения изображаются диаграммами Юнга (см., например, гл. I книги Макдональда17), мы отождествляем эти два объекта и обозначаем их одинаково. Если диаграмма р получена из диаграммы а путем добавления одной клетки, то это обозначается а / р (или, эквивалентно, р \ а). Это возможно только если р = (р\,..., ре) и <т = (рг,..., р{ - 1,..., ре) для некоторого г. Если # = тп, то а обозначается через Для всех т € N := {1,2,...} если в диаграмме р есть строка длины тп, то диаграмма р^ определяется единственным образом, а если в р нет такой строки, считаем, что р^ не определено. Через [р: (к е К) обозначим число компонент в разбиении р, равных к. Это неотрицательное целое число.

Определение 1.1.1. Пусть р,а — разбиения и а ? р. Переходной функцией вниз называется величина р1(р,а) •■= где р = (ри ■ ■■ ,Р() и а = (рг,--. - 1,... ,ре). Если неверно, что а / р, положим р1(р,а) := 0.

11Макдональд И. Симметрические функции и многочлены Холла. /— Москва, Мир, 1984. — 221 С.

Для всех разбиений р € К„ (где п е М) выполнено £стекп_1 Р1(Р>°~) = 1-Поэтому ограничение р1 на Кп х Кп_1 (обозначаемое через п_1) является марковским переходным ядром.

Определение 1.1.3. Семейство {Мп}, где Мп — вероятностная мера на К„, называется структурой разбиений, если оно согласовано с переходной функцией вниз: Ет€Кп+1 Мп+1(т)р1(т, р) = Мп(р) для всех п е 2г0 и р е К„, где Мп(т) обозначает меру одноточечного множества {т}.

Рассмотрим вложения гп:Кп -> Е, при которых разбиение р = (р\,. ■ ■ ,ре) переходит в точку симплекса 0,0,...).

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

Определение 1.1.5. Пусть 0$а<1и#> -а. Рассмотрим следующее семейство вероятностных мер М"'в на К„:

Мп \р) 7д\---псе г М! п<--НПО-!-»)-

П[Р• Л]!' П<=1 Р;! «=13=2

Здесь £ — число ненулевых компонент в р, а (в)п ■= в (в + 1) ...(& + п - 1) — символ Похгаммера. Это действительно семейство вероятностных мер. Кроме того, меры образуют структуру разбиений. Она была введена Ювенсом

при а = 0 и обобщена Питманом на случай а > 0.

Определение 1.1.6. Вероятностные меры на Е, соответствующие (в смысле теоремы 1) структурам разбиений {М£,е>}, называются распределениями Пуассона-Дирихле и обозначаются РО(а,0).

Перейдем к описанию модели Морана и ее алгебро-комбинаторной интерпретации. Пусть {Мп} — структура разбиений, такая, что Мп(р) > 0 для всех П € 2^0 и р € Кп.

Определение 1.1.7. Переходной функцией вверх для р, т е К, таких, что р / г, называется величина р*(р, т) := нд^у^рЧт> р)> гДе п-\р\ир1 — переходная функция вниз. Если неверно, что р / т, положим рЦр,т) := 0.

Переходная функция вверх уже зависит от выбора структуры разбиений. Ограничение на К„ х К„+1 (обозначаемое через п+1) является марковским переходным ядром. Семейство мер {Мп} согласовано с р\ то есть, ЕР€К„ Мп{р)р\р,т) = М„+1 (т) для всех п е Ъ>Л и г € Кп+1.

Определение 1.1.8. Пусть переходная функция вверх построена по структуре разбиений (здесь а = 0). Рассмотрим последовательность марковских цепей на Kn (п е N) с переходными операторами Moran„ := pl_l n j, или, подробнее, Morann(р, р) = р1(р,сг)р1(гг,р). Данная последовательность марковских цепей называется однопараметрической моделью Мора-на.

Модель Морана используется для моделирования динамики популяции с постоянным числом особей под воздействием процессов воспроизводства и мутации (интенсивность мутации регулируется параметром в > 0), при этом разбиение р описывает распределение типов особей в популяции (р\ — число особей

самого частого типа, и т.д.). Предельное поведение модели Морана описано в ю

Из данного определения модели Морана видна ее алгебро-комбинаторная интерпретация. В общем двухпараметрическом случае удобнее использовать несколько другие марковские цепи. При а = 0 их предельное поведение совпадает с поведением модели Морана. Приведем общее определение из работы 11

Определение 1.1.10. Пусть {Мп} — структура разбиений, такая, что Мп(р) > 0 для всех n е Z?o и ре Кп. Марковская цепь на Кп с переходным оператором р|,+1|„ л+1 называется марковской цепью вверх/вниз.

Мера М„ является инвариантной для марковской цепи вверх/вниз на 1&п> и цепь обратима относительно этой меры. Пусть Тп обозначает переходный оператор п-й марковской цепи вверх/вниз, построенной по структуре разбиений Ювенса-Питмана {М",е}. Ставится вопрос об изучении предельного поведения марковских цепей Тп при п-* оо.

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

Определение 1.2.1. Пусть j/i, 2/2, • • ■ — формальные переменные. Алгебра симметрических функций Л состоит из всех формальных степенных рядов от Уъ 2/2) • • •, которые симметричны по i/ь J/2, • • ■ и имеют ограниченную степень (то есть, степени всех мономов в формальном степенном ряде равномерно ограничены). Максимальная степень монома называется степенью симметрической функции.

Алгебра Л свободно порождена (как коммутативная алгебра с единицей) суммами Ньютона рь := y¡, к е N. Мономиальные функции определяются

как rrip := ........у?', где р = (pi,--.,pt) € К и сумма ведется по всем

наборам попарно различных индексов ii,...,i¿ 2 1. Факториальные аналоги функций Шр (обозначаемые ш*) получаются из обычных функций заменой каждой степени i/f на факториальную степень у\к = y,(y¿ - 1) • ■ • (j/i - к + 1). Каждая из систем функций {т^} и {т*} (где р пробегает все разбиения) является линейным базисом алгебры Л.

Отождествим (абстрактную) алгебру симметрических функций Л с алгеброй симметрических функций на разбиениях, полагая рк(а) := > <rf, А; € N. Алгебра симметрических функций на множестве К разделяет точки. Пусть / е Л. Через /п обозначим ограничение функции / на подмножество К„ с К. Так как Кп конечно, то пространство всех функций на Кп (обозначаемое Fun(K„)) исчерпывается функциями вида /„, где / е Л. Переходный оператор Тп действует в пространстве Fun(Kn) и однозначно определяется своим действием на симметрические функции (т*)„. Это действие дается следующей теоремой.

Теорема 1.2.2. Пусть п е N. Для всех разбиений р имеем

(п+в)(п+1){тп - i)(m;)„ = -|ЖН -1 + 0)Ю„+

+(n + 1 - И) Г Z [pñ] г (i - 1 + a)(m;w)n + [р: 1] (9 + а(((р) - 1)) (m^J. i=2

Здесь 1 обозначает тождественный оператор.

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

В третьем параграфе для всех значений параметров 0^а<1и#>-а устанавливается сходимость марковских цепей Тп к диффузионному процессу Xa¡e(t) на Е, который сохраняет меру Пуассона-Дирихле PD(«, в). Исследуются некоторые важные свойства полученных процессов.

Бесконечномерный симплекс Е — компактное пространство в топологии покоординатной сходимости. Через С(Е) обозначим банахову алгебру всех непрерывных функций на Е с поточечными операциями и супремум-нормой. Рассмотрим плотную подалгебру Т с С(£), порожденную (как коммутативная алгебра с единицей) алгебраически независимыми функциями qfc(x) := xf+1, к e N, х е Е. Отметим, что функция xi не является непрерывной на Е. Ясно, что Т = A/(pi -1 )Л, где (pi - 1)Л — идеал в алгебре Л, порожденный р\ -1. Пусть 7г„:С(£) -» Furi(Kn) — соответствующие вложениям г„:К„ Е проек-

ции пространств функций, то есть, (7гпу)(сг) := д(г„(<т)), а е К„, д е С(Е).

Теорема 1.3.4. Существует оператор А-Т -* Т, такой, что при п -* оо операторы п2(Т„ -1) сходятся к А в алгебре Т. Более форматно,

Jim шах|(п2(Г„ - l)nng)(a) - (itnAg)(o)\ = 0 для всех д е Т.

п-«о сгеК„

Оператор А может быть записан как формальный дифференциальный оператор в коммутативной алгебре полиномов от qi, Чг, • • •

ОО Q2

а = Z +1)0'+ i)(q»+j - q¿qj)Яя я

Í,j=i oq.oqj

ОО Q

+ £ [-(i + 1)(* + + (* + 1)(г - o)4i-i] ТГ-. 40 ••= 1,

¿=i oqi

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

оо ^2 оо 02 оо Q

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

Теорема 1.3.9. (1) Оператор А замыкаем в С(Е), и его замыкание порождает сильно непрерывную полугруппу сжимающих операторов {Т(0}(гп в С(£), которая сохраняет положительность и единицу. Дискретные полугруппы {l, Тп, ... } сходятся к непрерывной {T(í)}:

Ит тах|(г|"2<]7гпд)(ст) - (irnT(Jt)g)(<r)\ = 0 для всех дч С(£),

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

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

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

(4) Будем считать, что Xa,e(t) и все марковские цепи вверх/вниз Тп начинаются с инвариантного распределения. Тогда при п -* оо все конечномерные распределения цепей Тп сходятся к конечномерным распределениям процесса Xa ß{t), если сделать масштабное преобразование времени, при котором один шаг п-й марковской цепи соответствует малому интервалу времени порядка 1/п2.

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

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

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

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

Под строгим понимается разбиение, все части которого различны. Строгое разбиение можно изобразить сдвинутой диаграммой Юнга, которая получается из обычной диаграммы Юнга этого разбиения сдвигом каждой г-й строки на (г-1) клеток вправо, см. §7 главы III в книге Макдональда17. Строгие разбиения отождествляются со сдвинутыми диаграммами Юнга и обозначаются одинаково буквами ____Через §„ с К„ обозначим множество строгих разбиений

веса п е Z?o, а через S := U^Lo^n — множество всех строгих разбиений. Если сдвинутая диаграмма А получена из сдвинутой диаграммы р путем добавления одной клетки, то это обозначается р # А (или, эквивалентно, А % fi). Пусть эта клетка добавляется к строке в р, которая (до добавления) имеет длину х € Zjo (случай х = 0 соответствует добавлению к ¡л новой строки). Тогда А обозначается через р+(х). Эквивалентно, р обозначается через А - [х].

Пусть А — сдвинутая диаграмма Юнга. Через АТ(А) обозначим множество тех х е Zjo, для которых существует диаграмма А+(а;). Аналогично через Y(А) обозначим множество тех у е Z?o, для которых существует диаграмма А - [г/]. Если диаграммы А + (х) и А - [у] существуют, то они определяются единственным образом. Считаем, что элементы множеств Х(Х) и У(А) перечислены в возрастающем порядке.

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

Координаты Керова сдвинутых диаграмм Юнга аналогичны перемежающимся координатам обычных диаграмм Юнга, введенным Керовым18

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

(2) Если А содержит строку длины 1, то для некоторого (1^1 выполнено Х(Х) = У(А) = {0,У2, --,Уа} и 0 = ух < XI <•■■< уа < ха-Если А не содержит строки длины 1, то для некоторого <1 0 выполнено Х(Х) = {О, XI,... У(А) = {2/1,... ,ув) и 0 = хо <г/1 <Х1 < ••• <у<г <х<г.

(3)Для всех А выполнено £хех(Л) х(х + 1) - у(у + = 21А1-Положим Х'(Х) := Х(Х) \ {0}. Легко видеть, что в Х'(А) и в У(А) всегда

одинаковое число элементов.

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

Д|(ц.л) - П,сХ'(А)("-»0с+1)) _1 у ^(Л) П„сУ(А)(»-У(» + 1)) +

Определение 2.1.3. Пусть Х,ц € § и /х # X. Это значит, что ц = X - [у] для некоторого «/ е У(А). Число называется переходной функцией вниз и обозначается через р"(А,^).

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

Определение 2.1.5. Семейство вероятностных мер {Мп на §„} называется когерентным, если оно согласовано с переходной функцией вниз, то есть, Мп+1{у)р*{у, А) = Л/„(А) для всех п е Ъ>а и А е 5„. Для когерентных семейств {М„нৄ} существует предельная теорема, аналогичная теореме Кингмана для структур разбиений. Эта теорема, установ-

1%Керов С. Анизотропные диаграммы Юнга и симметрические функции Джека // Функц. анализ и его прт. - 2000. - Т. 34, № 1. - С. 51-М.

ленная Назаровым, дает взаимно-однозначное соответствие между когерентными семействами {М„} и вероятностными мерами Р на Е. При этом Р получается как слабый предел мер ]п(Мп) на £ (при п -* оо), где вложения -+ Е определяются как Л = (Ль..., А*) 7„(А) := ..., ^,0,0,...) е Ё.

Определение 2.1.6.14 Пусть а > 0 — параметр. Рассмотрим следующее семейство вероятностных мер на §п:

2-<(*)П1 /г . Ч2 ^

М"(Л):=(а/2) (А,' П т ПП(Ю-1) + а).

В работе14 было показано, что {М®} — когерентное семейство вероятностных мер на строгих разбиениях. Пусть Р^ — вероятностные меры на Е, соответствующие (в смысле предельной теоремы Назарова) когерентному семейству {М°}.

Переходная функция вверх для когерентного семейства мер на строгих разбиениях определяется так же, как и для структур разбиений. Переходные функции вверх для мер Планшереля и для мер {М°} выражаются через перемежающиеся координаты сдвинутых диаграмм Юнга. Пусть А е §, г> — комплексная переменная. Рассмотрим следующую функцию и ее разложение в сумму простейших дробей:

1 = Пуеу(А)("-у(г/+1)) у т?|(А)

Предложение 2.1.7. Для любой сдвинутой диаграммы А и всех х е _Х"(А) выполнено рЦ(А, А + (ж)) = х(А) для всех А е 8 и х е -Х(А), где — переходные функции вверх для {Л/™}, а > 0.

Через Х¥п, п € М, обозначим переходный оператор марковской цепи вверх/вниз на §„, построенной по семейству {М°}. Ставится вопрос об исследовании предельного поведения марковских цепей \¥п при п -> +оо.

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

Определение 2.2.1. Алгеброй дважды симметрических функций называется подалгебра Г = К [рг,рз, ■ • • ] с Л, порожденная суммами Ньютона с нечетными номерами. В алгебре Г можно ввести фильтрацию, полагая с^р2к+1 = 2к +1,

к 6 N. Говорят, что оператор R: Г -* Г имеет степень < г, где г € Z, если для всех / € Г выполнено dcg(Rf) ^ dcg / + г.

Алгебру Г можно рассматривать как алгебру функций на строгих разбиениях, полагая p2k+i(A) := A¿fc+1, Л е S, к е N. Для / е Г обозначим через /п сужение / на подмножество с §. Алгебра Г разделяет точки множества §, поэтому конечномерное пространство Fun(§„) всех функций на Sn исчерпывается функциями вида /„, где / е Г.

Теорема 2.2.29. Существует единственный оператор В: Г Г, такой, что (n+a/2)(n+l)(W„-l)/n = (Bf)n для всех f е Г. Степень оператора В равна нулю, и он имеет вид

~ 00 д2 В = X) (2¿ - 1)(2j - l)(pip2i+2j-3 ~P2i-iP2j-i)n-я-

i,j=2 Op2i-ldp2j-l

oo Q

+2 (2i + 2j - l)piP2i-iP2j-i-z-

i,j=1 OP2i+2j-l

~ ч / a\ д

- y,(2 i -1) 12i - 2 + - )í»2¿-i д-+ операторы степени ^ -1.

i=2 V 2/ dp2i-i

В третьем параграфе для всех а > 0 устанавливается сходимость марковских цепей вверх/вниз Wn к бесконечномерному диффузионному процессу Xa(t) на а также исследуются некоторые свойства этого процесса. Исследование сходимости цепей Wn и полученных диффузионных процессов во многом аналогично случаю, рассмотренному в главе 1.

Пусть алгебра Q с С(Е) порождена функциями qfc(x) с четными номерами. Отображение Л -> Т = A/(pi - 1)Л в ограничении на Г с Л дает Г -» б = Г/(рх-1)Г.

Теорема 2.3.3. Существует оператор В. Я -+ Q, такой, что при п -* оо операторы n2(W„ - 1) сходятся к В в алгебре Q (определение сходимости такое же, как в теореме 3). Он может быть записан как оператор в алгебре полиномов о/я q2, Я4, • • •:

оо q2

В = Е (2¿ + + Х) (42¿+2j - q2¿q2j) дцгдц2.

'J°° д °° ( а\ д

+2 ^ (2i + 2j + 3)ЪЪд^ ~ 1(2i + 1) (2Í

Теорема 2.3.5. (1) Оператор В замыкаем в С(Е), и его замыкание порождает сильно непрерывную полугруппу сжимающих операторов {W(í)}(so

в С(Е), которая сохраняет положительность и единицу. Дискретные полугруппы {l, Wn, ...} сходятся к непрерывной {W(t)}, причем эта сходимость равномерна на конечных интервалах по t.

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

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

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

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

(6) Спектр генератора процесса Xa(t) в L2(E,Р^) имеет следующий вид: {0}и{-т(т - 1 + а/2): т = 2,3,...}. Собственное значение О простое, а кратность т-го равна числу разбиений т на нечетные слагаемые, большие единицы.

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

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

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

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

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

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

Публикации автора по теме диссертации

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

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

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

Подписано в печать 20.05.2010 г. Объем 1,5 усл.печ.л. Тираж 100 экз. Заказ № 25677 Отпечатано в типографии «Реглет» 119526, г. Москва, пр-т Вернадского, 39 (495) 363-78-90; www.reglet.ru

Введение

Глава 1. Диффузии и распределения Пуассона-Дирихле.

1.1. Распределения Пуассона-Дирихле и модель Морана.

1.2. Марковские цепи на разбиениях и симметрические функции

1.3. Построение и свойства предельного процесса.

Глава 2. Марковские цепи на строгих разбиениях.

2.1. Строгие разбиения и перемежающиеся координаты.

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

2.3. Сходимость марковских цепей на строгих разбиениях.

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

Теория машинного обучения изучает методы построения и анализа алгоритмов, способных обучаться в процессе своей работы. К области машинного обучения без учителя относятся алгоритмы, в ходе выполнения которых система спонтанно обучается выполнять поставленную задачу без вмешательства со стороны экспериментатора. Общие сведения о задачах машинного обучения см. в книгах [1], [9], [57]. В последние несколько лет в области машинного обучения без учителя активно развиваются методы анализа и классификации по темам большого корпуса текстов на естественном языке, основанные на непараметрических байесовских моделях (см., например, работы [32], [61], [89], [66], [29], а также обширную библиографию в последней работе). Многие вероятностные модели, рассматриваемые в связи с этими задачами, основаны на распределениях Пуассона-Дирихле.

Вероятностные распределения Пуассона-Дирихле PD(a,0) зависят от двух параметров 0 ( а < 1 и 0 > -а и описывают закон распределения последовательности невозрастающих неотрицательных случайных величин (Xl, Х2,. ■ ■ ), таких, что Х\ ^ Хч ^ . ^ 0 и = 1. В исследование распределений Пуассона-Дирихле внесли вклад Бертуан, Биллингсли, Бли-новский, Вершик, Гончаров, Гримметт, Гриффите, Дикман, Доннелли, Игнатов, Йор, Карлтон, Керов, Куртц, Кингман, Ллойд, Ольшанский, Питман, Уоттерсон, Цилевич, Шепп, Шмидт, Этье, Ювенс, и другие. Однопарамет-рическое семейство распределений Пуассона-Дирихле PD(0,0) (соответствующее случаю а = 0) было введено Кингманом [69] в связи с задачами, возникающими в популяционной генетике. Двухпараметрическое обобщение принадлежит Питману [76]. О мотивации введения второго параметра в распределения Пуассона-Дирихле, а также о свойствах двухпараметри-ческих распределений PD(a,#) см. работу Питмана и Йора [79]. Семейство распределений Пуассона-Дирихле является одним из фундаментальных законов в теории вероятностей и теории случайных процессов. Более подробно об этих распределениях см. книгу Питмана [78] и недавнюю монографию Фенга [52], в которой описаны некоторые популяционно-гене-тические модели, приводящие к мерам Пуассона-Дирихле. О различных популяционно-генетических моделях см. также [49], [70], [51], [46] й главу 10 книги [47]. Стоит отметить, что распределения Пуассона-Дирихле также используются в комбинаторике [78], теории чисел [39], [8], [27], [7], [40], математической физике [36], [37], Существуют экономико-математические модели, приводящие к распределениям Пуассона-Дирихле [24].

Модели машинного обучения, основанные на распределениях Пуассона-Дирихле, существенно используют специфику второго параметра а. Это связано с тем, что случайные величины в последовательности, имеющей распределение Пуассона-Дирихле PD(a;,#), ПРИ cl = 0 с вероятностью единица убывают показательным образом, а при а Ф 0 — степенным образом; как известно, для естественных языков' характерно степенное убывание частот (см., например, работу Шрейдера [21]). Опишем одну из общих постановок задач классификации в теории машинного обучения. Пусть задано конечное множество слов, называемое словарем. Вероятностное распределение на этом множестве слов называется темой (англ. topic). Текст — это некоторая последовательность слов, а набор текстов принято называть корпусом. На вход алгоритма классификации подается некоторый (обычно весьма большой) корпус текстов. В качестве корпуса текстов, подаваемого на вход, может, например, выступать набор аннотаций к статьям в некотором научном журнале, или подшивка новостных газетных материалов за определенный период времени. Различают статическую и динамическую постановку задачи классификации. В статистической задаче классификации все тексты входного корпуса рассматриваются как равноправные, и задача алгоритма классификации состоит в выборе тем и расположении текстов по темам так, чтобы это наилучшим образом соответствовало входным данным. В динамической задачи классификации постановке каждому тексту корпуса приписывается определенная временная отметка (время выхода журнала или газетного материала в примерах, приведенных выше). Помимо распределения текстов по темам, в задачу алгоритма классификации при динамической постановке входит отслеживание зависимости распределения тем от времени. Статические задачи классификации исследовались в уже упомянутых работах [32], [61], [89], [66], [29]. Исследованию некоторых динамических задач классификации посвящены работы [30], [31], [91].

В теории машинного обучения в статических и динамических задачах классификации в основном используется непараметрический байесовский подход, который состоит в следующем. Сначала строится априорная модель, которая порождает случайный корпус текстов с заданными свойствами. Затем по входному корпусу текстов вычисляется (а чаще моделируется, так как явно вычислить не удается) апостериорное распределение при заданных входных данных, по которому уже строится искомый набор тем и распределение текстов по темам, другими словами, производится статистический вывод. Априорная модель здесь зависит от некоторых параметров, которые обычно принадлежат бесконечномерному пространству (например, в качестве параметров модели могут выступать вероятностные распределения на прямой или на множестве натуральных чисел). Применение методов параметрической байесовской статистики в данной ситуации невозможно, поэтому используются другие подходы, называемые непараметрическими. О непараметрической байесовской статистике см., например, книги [38], [60]. Изучение (и в-некоторых случаях явное вычисление) апостериорных распределений, связанных с распределениями Пуассона-Дирихле PD(a, в), проводилось в работах Фергюсона [54], Антоняка [23], Блэкуэлла и Мак-Куина [28], Питмана [77]. Первые три работы рассматривают однопара-метрический случай, а четвертая работа посвящена двухпараметрическим распределениям Пуассона-Дирихле. Важные задачи статистического оценивания и проверки гипотез, связанные с двухпараметрическими распределениями Пуассона-Дирихле, исследовались в диссертации Карлтона [34]. Близкие проблемы исследовались также в работах [64], [65].

Опишем простейшую процедуру построения одного случайного текста на основе распределения Пуассона-Дирихле PD(o:, в). Данный пример представляет собой упрощенный частный случай иерархической модели классификации из работы [29]. Для анализа реальных данных требуются гораздо более сложные априорные модели, также основанные на распределениях Пуассона-Дирихле (см., например, библиографию в работе [29]). Зададим длину текста N € N := {1,2,.} (впоследствии N можно также рандомизировать, например, с помощью распределения Пуассона). Выберем последовательность величин (Х\,Х2,. ■.), где Х± ^ Хч ^ . ^ 0 и Y^i Xi = 1, из распределения PD(a, 9). Набор (Xi, Х2,.) можно рассматривать как вероятностное распределение на натуральных числах N, которое приписывает вероятность Х^ числу к. Предположим, что для каждого натурального к задан закон распределения темы (обозначим его через Topic(fc)) на множестве всех допустимых тем. Теперь для кажого г = 1,.N выберем случайно число кг из распределения (Xi,Xo, ■ ■ ■) на множестве N. Затем выберем тему из распределения Topic(ki). Наконец, по теме Topic(ki) случайно выберем слово из нашего словаря. Это и будет слово номер г в нашем построенном случайном тексте. Таким образом будет построен весь случайный текст длины N. Статистический вывод в этой ситуации (то есть, результат, работы алгоритма классификации) представляет собой некоторый набор тем, которым лучше всего отвечает поданный на вход текст. Видно, что использование распределения Пуассона-Дирихле позволяет не ограничивать заранее число возможных тем в тексте. Также отметим, что текст строится последовательно, что позволяет добавлять новые данные после статистической обработки уже имеющихся.

Динамические задачи теории машинного обучения, которые начинают активно исследоваться (см. работы [30], [31], [91]), связаны с распределениями Дирихле, которые являются конечномерными аналогами распределений Пуассона-Дирихле. Использование распределений Дирихле приводит к ограничениям на число возможных тем в задаче классификации. Поэтому возникает потребность в динамических моделях, связанных с двухпарамет-рическими распределениями Пуассона-Дирихле, которые могли бы снять это ограничение.

Динамические модели, связанные с однопараметрическим семейством распределений Пуассона-Дирихле PD(0, в), широко изучались в контексте популяционной генетики. Изучение динамических моделей в популяцион-ной генетике началось с дискретных моделей Райта-Фишера (рассматривалась, начиная с 1920-30-х гг.) и Морана (была введена в 1950-е гг.). О различных дискретных моделях популяционной генетики см. работы [71], [50], [92], §3 работы [46], главу 10 книги [47], а также книгу [52]. Дискретные модели Райта-Фишера и Морана можно трактовать как последовательности марковских цепей на разбиениях (пространство состояний п-й цепи есть множество всех разбиений числа п).

Разбиения — фундаментальный математический объект. Основные сведения о них можно найти, например, в книгах Стенли [19] и Фултона [20]. Разбиения широко применяются в теоретической информатике, например, в различных методах сортировки (в частности, при сортировке слияниями), которым посвящена фундаментальная монография Кнута [13]. В контексте алгебраической комбинаторики разбиения изучаются в книге Макдональда [14].

Предельное поведение некоторых классов моделей Райта-Фишера и Морана исследовано в работе Этье и Куртца [46], в которой построено семейство бесконечномерных диффузионных процессов, сохраняющих од-нопараметрические распределения Пуассона-Дирихле PD(0,в). Под бесконечномерным диффузионным процессом понимается строго марковский процесс с непрерывными траекториями на бесконечномерном компактном или локально компактном пространстве состояний. Построенные в [46] процессы исследовались и обобщались в работах, принадлежащих Вио, Доннелли, Гриффитсу, Куртцу, Таваре, Уоттерсону, Флемингу, Шмуланду,

Этье, и другим. Более подробно об этих процессах и их различных обобщениях см. главу 10 книги [47], а также работы [55], [41], [43], [83], [44], [45] [48].

Этье и Куртц строили бесконечномерные диффузионные процессы, сохраняющие распределения PD(O,0), с помощью их аппроксимации конечномерными диффузиями на симплексах растущей размерности. Данный метод неприменим в случае двухпараметрических распределений Пуассона-Дирихле PD(a. (9). Поэтому для построения бесконечномерных диффузий, обобщающих процессы Этье-Куртца [46] на двухпараметрический случай, требуется применение других методов.

В диссертации найдена алгебро-комбинаторная интерпретация модели Морана на разбиениях, которая позволяет обобщить эту модель на двухпараметрический случай, а также построить диффузии, сохраняющие двухпа-раметрические распределения Пуассона-Дирихле. Данная интерпретация включает модель Морана (и её двухпараметрическое обобщение) в широкий класс марковских цепей на разбиениях, рассматриваемый Фульманом, Бородиным и Ольшанским [58], [59], [33], [75]. Возникает вопрос об анализе асимптотического поведения других марковских цепей на разбиениях, входящих в этот класс. Проводится исследование одного семейства марковских цепей из этого класса на строгих разбиениях (то есть, разбиениях, все части которых различны).

О некоторых приложениях строгих разбиений в теоретической информатике (в задачах сортировки) см., например, монографию Кнута [13]. Соответствие Робинсона-Шенстеда-Кнута для обычных разбиений (описанное, например, в книгах [20], [13]) обобщается и на случай строгих разбиений [93], [82]. Это комбинаторное соответствие делает возможным применение различных ансамблей случайных разбиений в задачах, связанных со случайными матрицами, а также в теории массового обслуживания (см., например, работы [25], [42]). Комбинаторные свойства строгих разбиений изучались также в [80]. Важные асимптотические задачи, связанные со случайными строгими и обычными разбиениями (в частности, нахождение предельных форм случайных диаграмм), исследовались в работах [63], [2], [22], [35], [3], [4].

Модель марковских цепей на строгих разбиениях возникает в связи с ансамблем случайных строгих разбиений, введенном Бородиным [5]. Этот ансамбль связан с теорией проективных представлений симметрических групп, начало которой положила работа Шура [84]. Теория проективных представлений симметрических групп (включая асимптотические вопросы) развивалась в работах Иванова [10], Назарова [15], [73], [74], Сергеева [85], Стембриджа [87], и других . См. также книгу [62].

Стоит отметить, что ансамбль случайных строгих разбиений [5] приводит к новым моделям точечных процессов, которые отличаются от традиционно рассматриваемых в статистической физике (об этих моделях см., например, книгу Форрестера [56]). Изучение предельного поведения ^указанных марковских цепей на строгих разбиениях позволяет построить новые примеры бесконечномерных диффузионных процессов.

Первая глава диссертации посвящена построению и исследованию семейства бесконечномерных диффузионных процессов, сохраняющих двух-параметрические распределения Пуассона-Дирихле PD(cn,0).

В первом параграфе приводятся необходимые сведения о разбиениях и распределениях Пуассона-Дирихле. Приводится определение модели Морана на разбиениях и дается ее алгебро-комбинаторная интерпретация, а также вводится двухпараметрический аналог модели Морана. Обозначим через Тп (п е N) переходный оператор марковской цепи на множестве разбиений числа 72, которая является двухпараметрическим обобщением модели Морана. Оператор Тп зависит от параметров 0^а<1и#> -а.

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

В третьем параграфе строится и исследуется двухпараметрическое семейство бесконечномерных марковских процессов с непрерывным временем Xa$(t), которые являются пределами марковских цепей Тп при п -> оо (точный смысл сходимости пояснен ниже в теореме 1.3.9). Опишем пространство состояний процессов X^it). Распределения Пуассона-Дирихле PD(a, 0) описывают закон распределения последовательности невоз-растающих неотрицательных случайных величин (Xi,X2,. ■), таких, что Xi ^ Х2 > . . Z 0 и Y.'jti Х{ = 1. Другими словами, распределения PD(a, в) можно рассматривать как вероятностные меры на множестве Е := {(xi,x2,. ):xi ^ х2 > . ^ 0, Е^х* = l}.

Рассматриваемое как подмножество куба [0,1]°° с топологией покоординатной сходимости, пространство Е не является замкнутым. Удобно рассматривать замыкание пространства Е в этой топологии, а именно, пространство := {(хьх2,. ):х! ^ Х2 ^ . > 0, < l}. (0.1)

Таким образом, подмножество Е с Е плотно в Е. В топологии покоординатной сходимости, наследуемой из [0,1]°°, множество Е с [0,1]00 является компактным, метризуемым и сепарабельным топологическим пространством. Мы будем называть пространство Е (бесконечномерным) симплексом. Этот симплекс и выступает в качестве пространства состояний процессов Xafi{t).

Чтобы описать основные свойства процессов Xa>g(t), требуется дать некоторые определения. Через С(Е) обозначим банахову алгебру всех непрерывных функций на Е с поточечными операциями и супремум-нормой. Рассмотрим плотную подалгебру Т с С(Е), порожденную (как коммутативная алгебра с единицей) алгебраически независимыми функциями q&(x) := Е^хИ, к б N, х € Е. Отметим, что функция Y,T=i хг не является непрерывной на Е. Рассмотрим оператор А.Т -> Т, зависящий от параметров а и 9, который может быть записан как формальный дифференциальный оператор второго порядка в коммутативной алгебре полиномов от qi, q2,.: оо Q2 i,j=1 iu4j оо Q £ [-(« + 1)(г + в)Цг + (г + 1)(г - a)qi-i] тт", q0 == 1, г=1 ОС\г а также как дифференциальный оператор в естественных координатах:

ОО Q2 оО Q2 оо Q

А = - Е -+ о-- (0.2) г=1 аХг ij=l ОХгОХ0 -=1 СХг

Оператор Л, записанный в естественных координатах, может применяться только к функциям д € Т'. Чтобы применить его к такой функции, следует сначала вычислить Ад(х) для х е Е (такие х составляют плотное подмножество в Е) путем применения правой части формулы (0.2) к функции д(х) напрямую, а затем продолжить полученную функцию на весь симплекс Е по непрерывности.

Основные свойства процессов Xa>g(t), которые устанавливаются в третьем параграфе, состоят в следующем:

• Для каждой пары параметров 0 ^ а < 1 и в > -а оператор А\Т Т замыкаем в С(Е) и порождает бесконечномерный диффузионный процесс Xate{t) на Е. Оператор А-Т Т называется предгенератором процесса Xa>g(t).

• Процесс Xaj)(t) сохраняет меру Пуассона-Дирихле PD(cv, 0), обратим и эргодичен относительно нее.

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

• Конечные марковские цепи Тп на разбиениях (двухпараметрическое обобщение модели Морана) при п оо сходятся к процессу Xate(t). Точная формулировка этой сходимости приведена в теореме 1.3.9 ниже.

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

В первом параграфе приводится определение и основные свойства ансамбля случайных строгих разбиений (зависящего от параметра а > 0), введенного в работе [5]. Определяются марковские цепи на строгих разбиениях, связанные с указанным ансамблем. Используемая при определении этих марковских цепей алгебро-комбинаторная конструкция аналогична той, что была использована при исследовании модели Морана и ее двух-параметрического обобщения. Кроме того, в первом параграфе вводятся новые координаты для строгих разбиений, называемые перемежающимися координатами Керова, и исследуются их комбинаторные свойства. Эти координаты позволяют значительно уменьшить технические трудности, возникающие при исследовании построенных марковских цепей на строгих разбиениях.

Во втором параграфе вычисляется действие переходных операторов построенных марковских цепей на дважды симметрические функции от компонент разбиений. Функция /(Ai, А2,.) называется дважды симметрической, если она симметрична по Ai, А2,., и кроме того, для всех 1 ^ г < j функция 7(АЬ ., г,., -z,.) (z стоит на г-м месте, a (-z) — на j-м) не зависит от z. Здесь Ai > А2 > • • • > 0 — компоненты строгого разбиения. При вычислении действия переходный операторов используются полученные в первом параграфе комбинаторные свойства координат Керова строгих разбиений.

В третьем параграфе строится и исследуется семейство бесконечномерных марковских процессов Xa(t), зависящее от одного параметра а > 0. Марковские процессы Xa(t) являются пределами построенных в первом параграфе марковских цепей на строгих разбиениях (точный смысл сходимости поясняется в теореме 2.3.5 ниже).

Пространство состояний марковских процессов Xa(t) — бесконечномерный симплекс Е. Как pi в первой главе, бесконечномерный диффузионный процесс Xa(t) на Е удобно описывать в терминах его предгенератора. Пусть алгебра Q с С(Е) порождена функциями qA.(x) с четными номерами. Это также плотная подалгебра в С(Е). Рассмотрим оператор в алгебре полиномов от Ц2, q4, • • •, зависящий от параметра а > 0: оо Q2

В= Y, (2i + 1)(23 + 1) - q2iq2j) д—д—+ ij=1 oq2iOq2j

00 д °° ( а\ с)

2 £ (2г + 2j + 3) q2iq2,----£(2г + 1) 2г + - Чи—. ij=0 Cq2«+2i+2 г=1 \ 2/ Cq2i

Основные свойства процессов Xa(t), которые устанавливаются в третьем параграфе, состоят в следующем:

• Для каждого а > 0 оператор B:Q -> Q замыкаем в С(Е) и порождает бесконечномерный диффузионный процесс Xa(t) на Е.

• У процесса Xa(t) существует единственная инвариантная вероятностная мера Р(а) на Е. Процесс обратим и эргодичен относительно нее.

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

• Конечные марковские цепи на строгих разбиениях, построенные в первом параграфе второй главы, сходятся к процессу Xa(t). Точная формулировка этой сходимости приведена в теореме 2.3.5 ниже.

Основные результаты диссертации

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

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

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

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

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

Некоторые из полученных в диссертации результатов имеют продолжение в недавних работах Фенга и Сана [53] и Руггиеро и Уолкера [81].

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

Научная новизна

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

Основные результаты диссертации состоят в следующем:

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

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

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

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

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

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

Заключение

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

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

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

1. Прикладная статистика: классификация и снижение размерности / Айвазян С., Бухштабер В., Енюков И., Мешалкин Л.— М.: Финансы и статистика, 1989.— 608 С.

2. Блиновский В. Принцип больших уклонений для границы случайной диаграммы юнга // Пробл. передачи информ,— 1999.— Т. 35, № 1,— С. 61-74.

3. Блиновский В. Принцип больших уклонений для пуассоновских случайных величин и диаграммы Юнга // Проблемы передачи информации. — 2001,-Т. 37, № 1.-С. 72-77.

4. Блиновский В. Случайная диаграмма Юнга, вариационный метод и смежные проблемы // Проблемы передачи информации. — 2002. — Т. 38, №2.-С. 33-43.

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

6. Вентцель А. Курс теории случайных процессов. — М.: Наука. Физмат-лит, 1996.-400 С.

7. Вершик А. Асимптотическое распределение разложений натуральных чисел на простые делители II ДАН СССР.- 1986.- Т. 289, № 2.-С. 269-272.

8. Гончаров В. Из области комбинаторики // Известия Российской академии наук. Серия математическая. — 1944.— Т. 8, № 1.— С. 3-48.

9. Загоруйко Н. Прикладные методы анализа данных и знаний. — Изд-во Ин-та математики, Новосибирск, 1999.— 264 С.

10. Иванов В. Размерность косых сдвинутых диаграмм Юнга и проективные характеры бесконечной симметрической группы // Записки научных семинаров ПОМИ. 1997. - Т. 240. — С. 115-135.

11. Керов С. Комбинаторные примеры в теории AF-алгебр // Зап. науч. семып. ЛОМИ. 1989. - Т. 172. - С. 55-67.

12. Керов С. Анизотропные диаграммы Юнга и симметрические функции Джека // Функц. анализ и его прил. — 2000. — Т. 34, № 1. — С. 51-64.

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

14. Макдоиалъд И. Симметрические функции и многочлены Холла.— Москва, Мир, 1984.-221 С.

15. Назаров М. Ортогональный базис в неприводимых проективных представлениях симметрической группы // Функциональный анализ и его приложения. — 1988. Т. 22, № 1. - С. 77-78.

16. Петров Л. Двухпараметрическое семейство бесконечномерных диффузий на симплексе Кингмана // Функциональный анализ и его приложения. 2009. - Т. 43, № 4. - С. 45-66.

17. Петров Л. Предельное поведение некоторых случайных блужданий на строгих разбиениях // Успехи математических наук. — 2009.— Т. 64, №6.-С. 177-178.

18. Петров Л. Случайные блуждания на строгих разбиениях // Записки научных семинаров ПОМИ. 2009. - Т. 373. - С. 226-272.

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

20. Фултон У. Таблицы Юнга и их приложения к теории представлений и геометрии. М.: МЦНМО, 2006.- 328 С.

21. Шрейдер Ю. О возможности теоретического вывода статистических закономерностей текста (к обоснованию закона Ципфа) // Проблемы передачи информации. — 1967. — Т. 3, № 1.— С. 57-63.

22. Якубович Ю. Центральная предельная теорема для нормированных диаграмм юнга разбиений на различные слагаемые // Зап. научн. сем. ПОМИ.- 1999.-Т. 256.-С. 212-223.

23. Antoniak, С. Mixtures of Dirichlet Processes with Applications to Bayesian Nonparametric Problems // Ann. Statist.— 1974.— V. 2, № 6.— P. 1152-1174.

24. Aoki, M. Thermodynamic limits of macroeconomic or financial models: One-and two-parameter Poisson-Dirichlet models // Journal of Economic Dynamics and Control. 2008. - V. 32, № 1. - P. 66-84.

25. Baiyshnikov, Y. GUEs and queues // Probability Theory and Related Fields. 2001. - V. 119, № 2. - P. 256-274.

26. Berele, A., Tenner, B. Doubly symmetric functions. — 2009. — arXiv:0903.5306vl math.CO.

27. Billingsley, P. On the distribution of large prime divisors // Periodica Mathematica Hungarica.- 1972.- V. 2, № 1. — P. 283-289.

28. Blackwell, D., MacQueen, J. Ferguson distributions via Polya urn schemes I I The annals of statistics. — 1973.- V. 1, № 2,- P. 353-355.

29. Blei, D., Griffiths, Т., Jordan, M. The nested Chinese restaurant process and bayesian nonparametric inference of topic hierarchies // J. ACM. — 2010.— V. 57, № 2.- P. 1-30.

30. Blei, D.,-Lafferty, J. Dynamic topic models // Proceedings of the 23rd international conference on Machine learning / ACM. — 2006.

31. Blei, D., Lafferty, J. A correlated topic model of Science // Annals of Applied Statistics. 2007. - V. 1, № 1. - P. 17-35.

32. Blei, D., Ng, A., Jordan, M. Latent Dirichlet allocation // The Journal of Machine Learning Research. — 2003. — V. 3. — P. 993-1022.

33. Borodin, A., Olshanski, G. Infinite-dimensional diffusions as limits of random walks on partitions 11 Prob. Theor. Rel. Fields. — 2009.— V. 144, № 1.- P. 281-318.

34. Carlton, M. Applications of the two-parameter Poisson-Dirichlet distribution: Ph.D. thesis / University of California Los Angeles. — 1999.

35. Dembo, A., Vershik, A., Zeitouni, O. Large deviations for integer partitions // Markov Process. Relat. Fields. 2000. - V. 6, № 2. - P. 147-179.

36. Derrida, B. Random-energy model: An exactly solvable model of disordered systems // Physical Review B. 1981. - V. 24, № 5. - P. 2613-2626.

37. Derrida, B. From random walks to spin glasses // Physica D: Nonlinear-Phenomena.- 1997. — V. 107, № 2-4. — P. 186-198.

38. Dey, D., Mueller, P., Sinha, D. Practical nonparametric and semiparametric Bayesian statistics. — New York: Springer, 1998. — 392 P.

39. Dickman, K. On the frequency of numbers containing prime factors of a certain relative magnitude II Ark. Mat. Astr. Fys. — 1930. — V. 22. — P. 1-14.

40. Donnelly, P., Grimmett, G. On the asymptotic distribution of large prime factors // J. London Math. Soc. 1993. - V. 47, № 2. - P. 395-404.

41. Donnelly, P., Tavare, S. The population genealogy of the infinitely-many neutral alleles model I I Journal of mathematical biology.— 1987.— V. 25, № 4.- P. 381-391.

42. Draief M., Mairesse, J., O'Connell, N. Queues, stores, and tableaux // Journal of Applied Probability. 2005. - V. 42, № 4. - P. 1145-1167.

43. Ethier, S. The infinitely-many-neutral-alleles diffusion model with ages // Advances in Applied Probability. — 1990. V. 22, № 1. - P. 1-24.

44. Ethier, S. Eigenstructure of the infinitely-many-neutral-alleles diffusion model // Journal of Applied Probability.— 1992.— V. 29, № 3,— P. 487-498.

45. Ethier, S., Griffiths, R. The transition function of a Fleming-Viot process // The Annals of Probability. 1993. - V. 21, № 3. p. 1571-1590.

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

47. Ethier, S. N. Kurtz, T. G. Markov processes: Characterization and convergence. — New York: Wiley-Interscience, 1986. — 552 P.

48. Ethier, S. N., Kurtz, T. G. Fleming-Viot Processes in Population Genetics // SI AM J. Control and Optimization. — 1993. V. 31, № 2. - P. 345-386.

49. Ewens, W. The sampling theory of selectively neutral alleles // Theoretical Population Biology. 1972. - V. 3. - P. 87-112.

50. Ewens, W., Kirby, K. The eigenvalues of the neutral alleles process // Theoret. Popn Biol 1975. - V. 7. - P. 212-220.

51. Ewens, W. J. Mathematical Population Genetics. — Berlin: Springer-Verlag, 1979.- 325 P.

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

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

54. Ferguson, T. A bayesian analysis of some nonparametric problems // The Annals of Statistics. 1973,- V. 1, № 2,- P. 209-230.

55. Fleming, W. H., Viot, M. Some measure-valued Markov processes in population genetics theory // Indiana Univ. Math. J.— 1979.— V. 28.— P. 817-843.

56. Forrester, P. Log-gases and random matrices. — URL: http://www.ms.unimelb.edu.au/~matpjf/matpjf.html.

57. Friedman, J., Hastie, Т., Tibshirani, R. The elements of statistical learning. — Springer Series in Statistics, 2001. — 746 P.

58. Fulman, J. Stein's method and Plancherel measure of the symmetric group // Trans. Amer. Math. Soc. 2005. - V. 357. - P. 555-570.

59. Fulman, J. Commutation relations and Markov chains // Probability Theory and Related Fields. 2009. - V. 144, № 1. - P. 99-136.

60. Ghosh, J., Ramamoorthi, R. Bayesian Nonparametrics. — New York: Springer-Verlag, 2003. 305 P.

61. Goldwater, S., Griffiths, Т., Johnson, M. Interpolating between types and tokens by estimating power-law generators // Advances in Neural Information Processing Systems. — 2006. — V. 18.

62. Hoffman, P. N., Humphreys, J. F. Projective representations of the symmetric groups. — Oxford Univ. Press, 1992. — 320 P.

63. Ivanov, V. Plancherel measure on shifted Young diagrams // Representation theory, dynamical systems, and asymptotic combinatorics.— Amer. Math. Soc. Transl. Ser. 2, 2006. V. 217. - P. 73-86.

64. James, L. F. Bayesian calculus for gamma processes with applications to semiparametric intensity models // Sankhya: The Indian Journal of Statistics.- 2003.- V. 65, № 1,- P. 179-206.

65. James, L. F. Bayesian Poisson process partition calculus with an application to Bayesian Levy moving averages // Ann. Statist. — 2005. — V. 33, № 4. — P. 1771-1799.

66. Johnson, М., Griffiths, Т., Goldwater, S. Adaptor grammars: A framework for specifying compositional nonparametric bayesian models 11 Advances in neural information processing systems. — 2007. — V. 19. — P. 641-649.

67. Kerov, S. Asymptotic representation theory of the symmetric group and its applications in analysis. — Amer. Math. Soc., 2003.— 201 P.

68. Kerov, S., Okounkov, A., Olshanski, G. The boundary of Young graph with Jack edge multiplicities // Intern. Math. Research Notices. — 1998. — V. 4. — P. 173-199.

69. Kingman, J. F. C. Random discrete distributions // J. Roy. Statist. Soc. B. — 1975.-V. 37.-P. 1-22.

70. Kingman, J. F. C. Random partitions in population genetics // Proc. R. Soc. London, A.- 1978.-V. 361.-P. 1-20.

71. M. Kimura, J. C. The number of alleles that can be maintained in a finite population // Genetics. 1964.- V. 49.- P. 725-738.

72. Macdonald, I. G. Symmetric functions and Hall polynomials.— 2nd edition. — Oxford University Press, 1995. — 488 P.

73. Nazarov, M. Projective representations of the infinite symmetric group // Representation theory and dynamical systems / Ed. by A. Vershik. — Amer. Math. Soc., 1992.-V. 9.-P. 115-130.

74. Nazarov, M. Young's Symmetrizers for Projective Representations of the Symmetric Group // Advances in Mathematics.— 1997.— V. 127, № 2.— P. 190-257.

75. Olshanski, G. Anisotropic Young diagrams and infinite-dimensional diffusion processes with the Jack parameter // International Mathematics Research Notices. 2010. - V. 2010. - P. 1102-1166.

76. Pitman, J. The two-parameter generalization of Ewens' random partition structure: Technical report 345 / J. Pitman: Dept. Statistics, U. C. Berkeley, 1992.

77. Pitman, J. Some developments of the Blackwell-MacQueen urn scheme / J. Pitman // Lecture Notes-Monograph Series.— 1996.— V. 30.— P. 245-267.

78. Pitman, J. Combinatorial Stochastic Processes. — Springer-Verlag, 2006. — 256 P.

79. Pitman, J., Yor, M. Two-parameter Poisson-Dirichlet distribution derived from a stable subordinator // The Annals of Probability.— 1997.— V. 25, №2.-P. 855-900.

80. Pragacz, P. Algebro-geometric applications of Schur S- and Q-polynomials // Lecture Notes in Mathematics.— 1478.— V. 1991.— P. 130-191.

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

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

83. Schmuland, B. A result on the infinitely many neutral alleles diffusion model // Journal of Applied Probability.— 1991.— V. 28, № 2.— P. 253-267.

84. Schur, I. Uber die Darstellung der symmetrischen und der alternierenden Gruppe durch gebrocheme lineare Substitionen // J. Reine Angew. Math. — 1911.-V. 139,- P. 155-250.

85. Sergeev, A. The Howe duality and the projective representations of symmetric groups // Represent. Theory. — 1999. — V. 3. — P. 416-434.

86. Stembridge, J. A characterization of supersymmetric polynomials // J. Algebra. 1985. - V. 95. - P. 439-444.

87. Stembridge, J. Shifted tableaux and the projective representations of symmetric groups // Advances in Mathematics.— 1989.— V. 74, № 1.— P. 87-134.

88. Stembridge, J. On schur's q-functions and the primitive idempotents of a commutative hecke algebra // J. Algebraic Combin.— 1992.— V. 1,—

89. Trotter, H. F. Approximation of Semigroups of Operators // Pacific J. Math. 1958.-V. 8.-P. 887-919.

90. Wang, C., Blei, D., Heckerman, D. Continuous time dynamic topic models // Uncertainty in Artificial Intelligence UAI. — 2008.

91. Watterson, G. Reversibility and the age of an allele. I. Moran's infinitely many neutral alleles model // Theoret. Popn Biol.— 1976.— V. 10.— P. 239-253.

92. Worley, D. A theory of shifted Young tableaux: Ph.D. thesis / MIT, Dept. of Mathematics. — 1984.1. P. 71-95.