Диссертация (1137428), страница 4
Текст из файла (страница 4)
Обасимптотическомраспределенииэтойхарактеристикиизвестноследующее утверждение.Теорема 4. При n и b ~ n,0 1,33Et b n P t 1 t 1k1 k 1 k!I k ,(8.3)гдеI k t ,...,t 1kdt1 ...dt k, k 1,2,..., I 0 1.t1 ...t kt1 ... tk 1Добавим к этой теореме некоторые комментарии.Прежде всего отметим, что предельная производящая функция1P t представляет собой многочлен степени , то есть случайная 1величина b n в пределе принимает лишь значения 0,1,..., .
Так, 12 ,если b n 0,1 ,то поскольку 1 2и, следовательно, 1 1; если11 , то есть 2 1 3 , 1 2 , то32 b n 0,1,2; вообще, если11 при некотором целом s 1 , тоs 1s есть s 1 s 1, 1 s , то b n 0,1,.., s.nТаким образом, во всей правой половине i , i цикловой2последовательности 1 , 2 ,..., n можетвстретитьсясамоебольшее лишь одна «1» (в n-подстановке может быть лишь один циклдлины,большейn/2,что,конечно,очевидно,таккак1 2 2 ... n n n ).
По мере же расширения «хвоста» i , i n , тоесть по мере уменьшения , число возможных единиц в нём нарастаетописанным выше образом.34Вычислим, далее, среднее значение предельного распределения в(8.3), то есть производную1P 1 I1 dt1 ln .tСправедливо более сильное утверждение, именно, в условияхтеоремыE b n ln1(8.4)Сравнивая результаты (8.4) и (6.7), можно констатировать, чтоnвклад в сумму n i«далёких хвостов»i 1 i , i bприb ~ n,0 1, незначителен – всё «богатство» цикловой структуры 1 , 2 ,..., n связано с её начальными отрезками i , i on.
.Наконец, опишем ещё и схему доказательства теоремы 4.Производящая функция случайной величины b n получается из(4.7) при t r 1, r b, t r t , r b :Et b n1zr zexpt 1 1 zr b r n j t 1 kz z j 0 k 0 k! n1t 1kk!1 k n b zr r b rkS k b, n ,гдеS k b, n 1r ... r n r ... r1kr1 ,...,rk b1.k35Далее показывается, что в условиях теоремы для чисел Sk b, n справедливы асимптотические соотношения:Sk b, n~ I k , k 1,2,...,что и даёт в результате (8.3).Можно также показать, что вероятность события C = {случайнаяn-подстановка содержит цикл длины, большей n } при асимптотически равна ln112.Из теоремы 4 следует также формула для вероятностей:1 k mP n m m 1 I k , m 1;m k 1 k m 1! k m !b(8.5)в частности,P n 0 1 1 bsk 0 11 k 1 1k 1k!I k (8.6)k1 1I k , , , s 0,1,2,...k! s 1 s 36§9.
Длина максимального циклаВажной характеристикой случайной n-подстановки являетсядлина её максимального цикла – это номер 1 n последнего (илипервогосконца)ненулевогочленавпоследовательности 1 ,..., n :1 n maxi : i 0.(9.1)Хотя n-подстановка может иметь циклы любой длинны от 1 доn, но, скажем, вероятность получить полноцикловую подстановку(имеющую один цикл длины n), равная (n-1)!/n!=1/n, мала прибольших n, то есть в вероятностной модели такие подстановки“нетипичны”. Вероятностная модель позволяет выявлять как раз“типичные” ситуации, вероятности которых не являются бесконечномалыми при n . Какова же “типичная” длина максимальногоцикла случайной n-подстановки? Ответ на этот вопрос легко получитьиз предыдущих результатов, и он даётся следующей теоремой.Теорема 5. Нормированная случайная величина 1 n / n имеет приn собственное предельное распределение на отрезке [0,1],функция распределения которого 1 x определена в (8.6), а1x плотность имеет вид 1 x 1 x 1 .x 1 x Для доказательства слабой сходимости достаточно заметить, что371 n b (все i 0 при i>b)= b n 0,и воспользоваться теоремой 4, точнее, следствием из неё (8.6).Вид плотности 1 x следует непосредственно из (8.6):1 s 1 1 k x 1 , 1 , s 1,2,...;1 x Ik при x x k 0 k!1 x s 1 s (9.2)в частности,11, x 1,x21111 x 1 x ,x ,1 ln x32 x 1 1 ln 1 x 1 I x , 1 x 1 .2 x x2 1 x 43Таким образом, функция распределения 1 x и её плотность1 x на отрезке [0,1] задаются с помощью счетного множествавыражений.Добавим к сказанному ещё один известный результат:lim E1 n / n 0,6243...nУказанное в теореме 5 предельное распределение впервые былонайдено В.Л.
Гончаровым в 1944г., поэтому оно носит его имя.В завершение этой темы приведем ещё обобщение теоремы 5 внекоторых направлениях. Введем ещё следующие характеристикицикловой структуры: 2 n maxi 1 n : i 0- номер второго сконцаненулевогочленав 1 ,..., n ,..., m n maxi m1 n : i 0- номер m-го (с конца) ненулевогочлена в .
Другими словами, m n - это m-я максимальная длина38циклов случайной n-подстановки (при этом каждая длина iучитывается i раз, если i >0). Нетрудно видеть, чтослучайными величинами m n и b n имеетмеждуместо следующаясвязь: m n b b n m.Следовательно, в силу результата (8.5), имеем, что при n илюбом фиксированном m 1 m x , 0 x m 1 ,n m n x x m 1 . 1,1Далее,для1 n ,…, m n совместногодоказанараспределенияследующаяслучайныхмногомерная(9.3)величинлокальнаяпредельная теорема [4].Теорема 6. Пусть m 1 и 0 xm xm1 ...
x1 1 таковы, что0 x1 ... xm 1. Тогда lim n m j n nx j , j 1,..., m m x1 ,..., xm nxm1.1 x1... xm1x...x1m (9.4)Определенная в (9.4) функция m x1 ,..., xm называется m-мернойплотностью Гончарова (при m=1 она сводится к (9.2)).39§10. Общая картинаИтак,цикловая 1 , 2 ,..., n структураслучайнойn-подстановки при n устроена следующим образом.«Голова» этой последовательности i , i b (её распределение)при любом b on устроена так же, как совокупностьнезависимыхпуассоновскихслучайныхвеличин,Z i , i bприэтом1L Z i , i 1,2, ,..
, а «далёкие хвосты» i , i b , b bn (какiугодно медленно), с вероятностью, стремящейся к 1 при n ,состоят лишь из нулей и единиц.Для общего числа тех значений индекса i, для которых i 2 , тоесть для случайной величиныnL2 n I i 2,i 1имеет место сходимость по вероятности [5]L2 n L2 I Z i 2,i 1при этом EL2 0,528... (тем самым по вероятности случайнаявеличина L2 n асимптотически ограничена).Отсюда, в частности, следует, чтоPвсе i 1 PL2 n 0 PL2 0 Pвсе Z i 1 4011 PZ i 1 1 i e i e C 0,561...i 1i 1Здесь использована формула Вейерштрасса для гамма-функции: z ze 1 i 1 1Czzz ie ,iгде С – постоянная Эйлера (см.
(5.8).nОбщее число циклов n i в среднем растёт как ln n , а егоi 1распределение асимптотически нормально N ln n, ln n . Более того,для любого t 0,1 при n L i t ln n i ntt ln n N 0,1.В то же время могут быть и очень длинные циклы: сположительной вероятностью случайная n-подстановка может иметьцикл (но только один!) любой длины n, 0 1.41Глава 2d -параметрическая модель случайныхподстановок и её анализ§1. Модель и основные соотношения для неё1.1.Мера и производящие функцииВид вероятностной меры PA s , s S n , для произвольногоразбиения A A1 , A2 ,..., Ad (см.
(В.4)) следует из общих соотношений(В.1) – (В.2), в которых надо все параметры i при i A j положитьравными одномерному новому параметру для каждого j 1,..., d : притакой замене статистическая сумма (В.2) примет вид:H nA ( ) = n![ z n ]exph z ; ,(1.1)гдеdh z , jj =1iA jzi, 1 ,..., d ,i(то есть определяется теперь d - мерным параметром),а соотношение (В.1) – вид d d СA j nPA ( s) = I icij = n jH nA ( ) , j =1iA j =1j(1.2)где, напомним, символом cij - число A j -циклов длины i A j вподстановке s и C Aj n iA cij - общее число A j -циклов.j42Соотношениями (1.1) – (1.2) определяется d - параметрическаямодель случайных подстановок, которая и является объектом нашегоисследования. В рамках такой модели можно рассматривать болеедетальноструктуризациюцикловойпоследовательностиcn c1 , c2 ,..., cn подстановки, именно, записывать её в видеcn cij ,i A j ,j 1,...,d.Введем соответствующую производящую функциюF n t ; A E t ijcij , t tij , i A j , j 1,..., d ,dj 1iAjтогда аналогом (В.3) является в рассматриваемой моделипредставлениеF n t ; A H nA t / H nA ,(1.3)dzi H nA t n! z exp j iA tij j i j 1dzin n! z exp j iA tij 1 h z ; ,j i j 1(1.4)где теперь: n и h z ; определено в (1.1).Если мы интересуемся лишь циклами определенного вида,скажем, A j0 - циклами, то из (1.3) – (1.4) следует, что совместнаяпроизводящая функция для них есть:zin! z exp j0 iAti 1 h z ; ji.H nA nE iA tij0cij00Эти общие соотношения открывают новые(1.5)возможности визучении случайных подстановок.
Предложенная модель обобщает в43различных направлениях изучавшиеся ранее модели, включая их всебявкачестверавновероятнаячастныхмодельслучаев(например,соответствуетслучаюклассическая1 ... d 1).Детальнее об этом будет сказано ниже, а здесь стоит отметить, что врамках нашей модели возможно, в принципе,исследовать иподстановки с «запретами», то есть когда какие-то A j - циклы вподстановке«запрещенные»(впредыдущихсоотношенияхсоответствующие параметры j надо положить равными нулю), и приэтом важно знать не просто о числе остальных циклов подстановки,но и об их более детальной структуризации.Подчеркнем еще, что достоинством модели (1.1) – (1.2) являетсяее достаточная общность: она допускает конкретизации в различныхнаправлениях (выбор разбиения A A1 ,..., Ad , размерности d и видапараметров j ).