Марковские процессы

1. Марковские процессы

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

Примеры марковских процессов на графе Юнга:

• Процесс Ричардсона: одинаковые исходящие переходные вероятности для каждой вершины.
• Процесс Планшереля: одинаковые вероятности путей между любой парой диаграмм (центральный процесс).
• Равномерный процесс: одинаковая вероятность пути в любую диаграмму на одном уровне.

Процесс Ричардсона и процесс Планшереля будут подробнее рассмотрены в следующих разделах.

2. Процесс Ричардсона

На графе Юнга может быть построен процесс Ричардсона, в котором вероятности перехода во все диаграммы, которые могут быть построены из диаграммы \lambda_n добавлением одной клетки, равны. На рис. 10 приведены первые 5 уровней графа Юнга и вероятности процесса Ричардсона.

Процесс Ричардсона не обладает свойством центральности — вероятности путей, ведущих в одинаковые диаграммы, не равны. На рис. 11 рассмотрены три пути из диаграммы (3, 1) в диаграмму (3, 3, 1). Вероятности двух из них равны \frac{1}{36}, а одного — \frac{1}{18}.

3. Процесс Планшереля

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

Сумма вероятностей, исходящих из любой диаграммы на рисунке, равна единице. Рассмотрим два пути из корня графа Юнга в диаграмму, соответствующую разбиению (3, 1), обозначенных на рис. 12 пунктиром и пунктиром с точкой. Вероятность первого пути P_{path\_1}=\frac{1}{2}*\frac{1}{3}*\frac{3}{4}=0.125, вероятность второго пути P_{path\_2}=\frac{1}{2}*\frac{2}{3}*\frac{3}{8}=0.125 что вытекает из свойства центральности процесса Планшереля.

Вероятность случайного планшерелевского пути из корня графа Юнга в диаграмму λ характеризуется вероятностной мерой, называемой мерой Планшереля:

P_{diag}(\lambda)=\frac{dim(\lambda)^2}{n!},

где dim(\lambda) — точная размерность диаграммы, n — размер диаграммы. Учитывая свойство центральности, можно вычислить планшерелевскую вероятность пути из корня графа Юнга в диаграмму \lambda:

P_{diag}(\lambda)=\frac{dim(\lambda)}{n!},

где dim(\lambda) — точная размерность диаграммы, n — размер диаграммы. Вероятность пути в диаграмму \lambda_{n+1}, которую можно получить из диаграммы λ добавлением одной клетки, равна:

P_{path}(\lambda_{n+1})=P_{path}(\lambda_n)*P(\lambda_n\nearrow\lambda_{n+1}),

где P(\lambda_n\nearrow\lambda_{n+1}) — вероятность перехода по ребру графа Юнга в диаграмму\lambda_{n+1} из диаграммы \lambda, которая вычисляется следующим образом:

P(\lambda_n\nearrow\lambda_{n+1})=\frac{P_{path}(\lambda_{n+1})}{P_{path}(\lambda_n)}.

В формулу вероятности перехода по ребру подставляется формула планшерелевской вероятности пути:

P(\lambda_n\nearrow\lambda_{n+1})=\frac{\frac{dim(\lambda_{n+1})}{(n+1)!}}{\frac{dim(\lambda_n)}{n!}}=\frac{dim(\lambda_{n+1})*n!}{dim(\lambda_n)*(n+1)!}.

В формулу выше подставляется формула точной размерности диаграммы Юнга:

P(\lambda_n\nearrow\lambda_{n+1})=\frac{\frac{(n+1)!}{\prod_{(i,j\in\lambda_{n+1})}{}h(i,j)}\cdot n!}{\frac{n!}{\prod_{(i,j\in\lambda_n)}{}h(i,j)}\cdot(n+1)!}\frac{\prod_{(i,j\in\lambda_{n+1})}{}h(i,j))}{\prod_{(i,j\in\lambda_n)}{}h(i,j)}

Рассмотрим пример — диаграмму Юнга, соответствующую разбиению (4, 3, 2,1), изображенную на рис. 13 а). На рис. 13 б) изображена эта же диаграмма, но к ней добавлена клетка с координатами (2, 2) (выделена пунктиром). Длины крюков подписаны целыми числами.

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

p(\lambda,x,y)=\prod_{i=0}^{x-1}\frac{h(\lambda,i,y)}{h(\lambda,i,y)+1}\prod_{j=0}^{y-1}\frac{h(\lambda,x,j)}{h(\lambda,x,j)+1}

где \lambda — диаграмма Юнга, x и y — координаты добавляемой клетки, h(\lambda,i,j) — длина крюка с вершиной в клетке (i,j).