Диссертация (Случайные разбиения и асимптотическая теория представлений), страница 4

Рассмотрим на A упорядочение, обратное p (будем обозначатьего pt ), и будем считать, что:Lte = Lo ,Lto = Le .Таким образом, параметры {βj } и {αi } меняются местами; φpt определяется обобщенным RSK-алгоритмом, примененным к порядку pt и Lte , Lto , G. Будем обозначатьλt диаграмму Юнга, транспонированную к λ.Лемма 1.2.3.φp (w) = φpt (w)t для почти всех w.Доказательство. Если все буквы из G, входящие в w, различны (это условие вызвано формальной несимметричностью отношений x1 % x2 и x1 & x2 ) , то легко видеть,что возрастающая последовательность букв относительно p и Le ∪ Lo — это убывающая последовательность относительно pt ,Lte ∪ Lto . Таким образом, лемма следует изутверждения 1b).211.2.3Пусть q1 , q2 , q3 ≥ 0, q1 < q3 и q1 + q2 + q3 = 1.

Рассмотрим случайное блужданиечастицы по множеству {0, 1, 2 . . . }, в котором шаг вправо делается с вероятностьюq1 , а шаг влево — с вероятностью q3 , за исключением точки 0. Вначале частицанаходится в 0. Обозначим символом Ψq3 ,q1 (n) положение частицы после n-ого шага.Иначе говоря, Ψq3 ,q1 (n) — марковская цепь с переходной матрицейq + q2 q1 0 0 . . . 3 q3q2 q1 0 0D= 0q3 q2 q1 0..... ...

... ........ . .. . ....и начальным вектором ~a0 = (1, 0, 0, 0, . . .).Лемма 1.2.4. Существует константа C, не зависящая от n, такая чтоEΨq3 ,q1 (n) < Cдля любого nДоказательство. Определим вектор ~a формулой 2q1q1~a = (2, 2,2, . .

.)q3q3Легко видеть, что ~aD = ~a. Кроме того, вектор ~a покомпонентно больше, чем начальный вектор этой марковской цепи ~a0 = (1, 0, 0, 0, . . .). Из неотрицательности элементов матрицы D следует, что и ~aDn будет покомпонентно больше, чем ~a0 Dn длялюбого n. Но ~aDn = ~a, поэтому EΨq3 ,q1 (n) для любого n будет ограничено числом i∞Xq12iq3i=01.2.4Зафиксируем порядок на A. Пусть буквы a, b ∈ Le , a < b, образуют интервал относительно этого порядка (т.е.

a и b — соседние буквы) и w ∈ An — слово, подаваемое22на вход RSK-алгоритма. Обозначим символом wa,b слово, полученное из w вычеркиванием всех букв, кроме a и b.Назовем возможным преобразованием слова wa,b слово (обозначим его символомdw (wa,b )), в которое записывается тот порядок букв a и b, в котором они выбиваютсяиз первой строчки в процессе действия обобщенного RSK-алгоритма на слове w; есликакие-то буквы остались не выбитыми из первой строчки, то допишем их в конецслова dw (wa,b ) в том порядке, в котором они стоят в первой строчке.Будем называть суффиксом слова w=z1 z2 . . . zn любое слово видаzk zk+1 zk+2 .

. . zn . Для всех суффиксов (включая пустой) слова wa,b определим разность числа букв b и числа букв a, входящих в них. Максимальную из этих разностейназовем результатом и обозначим символом ρ(wa,b ), а любой суффикс, на которомона достигается, будем называть максимальным.Легко видеть, что если применять RSK-алгоритм непосредственно к слову wa,b ,то в первой строчке останутся не выбитыми ровно ρ(wa,b ) букв b.Пример. Пусть x1 < x2 < x3 ∈ Le и w = x2 x1 x3 x2 x1 x2 x3 x3 x2 x3 x1 x3 x2 . Тогдаwx2 x3 = x2 x3 x2 x2 x3 x3 x2 x3 x3 x2 , максимальный суффикс wx2 ,x3 состоит из 6 последнихбукв и ρ(wx2 ,x3 ) = 2. При этом выполненоdw (wx2 ,x3 ) = x2 x3 x2 x3 x2 x3 x2 x2 x3 x3 .Лемма 1.2.5.ρ(dw (wa,b )) ≤ ρ(wa,b )для любого w.Доказательство.

Шаг 1Будем образовывать пары букв из слова wa,b . В каждой паре будет одна буква bи одна буква a, причем буква a будет стоять в слове wa,b правее, чем буква b из этойпары. Составим эти пары следующим образом: первой возьмём самую правую буквуa и поставим ей в соответствие ближайшую к ней слева букву b. Затем возьмём самуюправую из ещё не выбранных букв a и поставим ей в пару самую ближнюю к нейслева букву b из числа ещё не выбранных. Проделаем эту процедуру максимально23возможное число раз.

Буквы b, не вошедшие в пары, будем называть черными, авошедшие — белыми.Для слова wx2 ,x3 из примера (см. выше) разбиение на пары будет выглядеть следующим образом:x2x3x2x2x3x3x2x3x3x2Шаг 2Докажем, что ровно ρ(wa,b ) букв b не вошло в пары. Действительно, пусть числочерных букв равно ρ0 . Рассмотрим суффикс, начинающийся с самой левой из черныхбукв. Каждая буква a из этого суффикса должна быть сопоставлена с буквой b изэтого же суффикса. Поэтому разность числа букв b и a для него равна ρ0 .

Значит,ρ(wa,b ) ≥ ρ0 . С другой стороны, в максимальном суффиксе должно быть как минимумρ(wa,b ) черных букв. Поэтому ρ0 = ρ(wa,b ).Будем для удобства считать, что в ходе RSK-алгоритма выбивается сначала белаябуква b, и только если такой нет — то черная. Понятно, что эта условность никак невлияет на ход алгоритма.Шаг 3Покажем, что в каждой паре буква b будет выбита раньше, чем соответствующаяей буква a. Будем доказывать это утверждение индукцией по числу пар. Рассмотримсамую левую пару. Буква b, входящая в нее, является первой белой буквой b в слове,поэтому буква a из этой пары обязана её выбить.

Для k-ой слева пары рассуждениеаналогично: в момент прихода буквы a из этой пары белые буквы b из предыдущихk − 1 пары уже выбиты (по предположению индукции), поэтому пришедшая буква aобязана выбить букву b именно из своей пары (если она не была выбита раньше, чтотакже возможно). Поэтому порядок в паре будет тот же и после любого возможногопреобразования строки wa,b .Следовательно, в результат слова dw (wa,b ) могут дать положительный вклад лишь24чёрные буквы слова wa,b , которых ровно ρ(wa,b ). Поэтому результат слова не увеличивается после возможного преобразования.1.31.3.1Доказательства теоремДоказательство теоремы 2 для конечного AДокажем теорему 2 для частного случая, а именно: предположим, что среди α- иβ-параметров имеется лишь конечное число ненулевых и что γ = 0. В этом случаетеорему достаточно доказать для случая, когда K равно числу всех ненулевых αпараметров, а L равно числу всех ненулевых β-параметров.

Таким образом, алфавитA = {x1 , x2 , . . . , xK } ∪ {y1 , y2 , . . . , yL }.В силу следствия из леммы 1, утверждения теоремы достаточно доказать длякакого-то одного порядка. Упорядочим алфавит A следующим образом:x1 < x2 < · · · < xK < yL < yL−1 < · · · < y2 < y1 .Будем применять к случайному слову w ∈ An обобщенный RSK-алгоритм. Обозначим символом ξji (n) число букв xj в i-ой строчке получающейся A-таблицы. Легковидеть, что при введенном порядке ξji (n) = 0, если i > j.Последовательность случайных величин {ψ(n)} назовём L-ограниченной, если существует константа C, не зависящая от n и такая, чтоE|ψ(n)| < Cдля любого nБудем обозначать любые последовательности L-ограниченных случайных величин символом {L(n)}.

Заметим, что выполнены соотношения{L(n)} + {L(n)} = {L(n)},{L(n)} − {L(n)} = {L(n)}.Сначала докажем утверждение теоремы для строк. Будем вести индукцию построкам.251) Первая строкаОценка снизу. Заметим, что все буквы x1 стоят в первой строке. ПоэтомуλP1 (n) ≥ Nx1 (n).Оценка сверху. Посмотрим, по каким правилам меняется число ξk1 (n) при k ≥ 2.Увеличиваться оно может только в случае появления буквы xk , что происходит свероятностью αk .

Если же появляется xk−1 , что происходит с вероятностью αk−1 >αk , и ξk1 6= 0, то ξk1 обязано уменьшиться на 1. В силу леммы 4, это означает, чтопоследовательность ξk1 (n) L-ограничена. Из определения A-таблицы следует, что вкаждой строке не больше одной буквы yj . ПоэтомуλP1 (n) = Nx1 (n) + {L(n)}2) Зафиксируем l ≤ K. Пусть утверждение теоремы верно для первых l − 1 строк.Докажем его для l-ой.Оценка снизу. Буква xl не может попасть ниже l-ой строки. С другой стороны,по уже доказанному, выше l-ой строки может быть лишь L-ограниченное количествобукв xl . ПоэтомуλPl (n) ≥ Nxl (n) − {L(n)}.Оценка сверху.

Обозначим символом w0 слово на входе обобщенного RSKалгоритма, и символами w1 , w2 , . . . — слова, в которые записываются буквы в томпорядке, в котором они выбиваются из первой, второй, ... строчек.Докажем L-ограниченность величины ξkl (n) при k > l. Заметим, что wxi−1—k−1 ,xkэто последовательность букв xk−1 и xk поступающих в i-ую строку, а wxi k−1 ,xk — последовательность букв xk−1 и xk выбиваемых из i-ой строки. Поэтому слово wxi k−1 ,xkявляется возможным преобразованием слова wxi−1, из которого вычеркнуты теk−1 ,xkбуквы xk−1 и xk , которые остались не выбитыми из i-ой строки.