Диссертация (1137428), страница 3
Текст из файла (страница 3)
Но предварительно мынапомним некоторые факты из комбинаторики и теории вероятностей,которые будут необходимы нам в качестве технического аппарата.20§5. Некоторые вспомогательные результаты5.1. Биноминальные коэффициенты. Число C mk (используется такжеmобозначение ), 0 k m , равное количеству k-подмножеств mk множества, называется биномиальным коэффициентом, так как этичисла фигурируют в знаменитой формуле бинома Ньютона:m1 x m Cmk x k .(5.1)k 0Для этих чисел можно использовать следующие представления:Cmk m!mm 1 m k 1 mk.k! m k !k!k!(5.2)Эти формулы можно обобщить на случай, когда показательстепени m есть произвольное действительное число.
Для этогоразложим функцию 1 x в окрестности точки x=0 в ряд Тейлора 1 k 1k 1k!1 x 1 kk 0k!x kxk .(5.3)Сравнивая коэффициенты в (5.3) с (5.2), можно записать, чтоCk kk!, k=0,1,2,…(5.4)Формула (5.4) и определяет биноминальные коэффициенты Ck дляпроизвольногоубывающуюдействительногофакториальнуюαчерез,функциютакназываемую,t n t t 1 t n 1,n 1, t 0 1.21Используя эти формулы, также можем записать разложение1 z tk 0Ckt z k t kk 0k!1k z k (5.5)t t t 1 t k 1 kkkz Ct k 1 z k z k ,k!k 0k 0k 0 k!где t k t t 1 t k 1,k 1,t 0 1, есть, так называемая,возрастающая факториальная функция.В(5.5)представленыразличныезаписибиномиальныхкоэффициентов, которые мы в дальнейшем будем использовать.5.2.
Числа Стирлинга. Если разложить убывающую факториальнуюфункцию по степеням аргумента t:nt n sn, k t k , sn, k 1nkk 1 i1...ink ,(5.6)1i1 ...i nk n1то коэффициенты этого разложения s(n,k) есть, так называемые, числаСтирлинга первого рода.Черезэтичислазаписываетсятакжеиразложениевозрастающей факториальной функции, определенной в (5.5):nt n 1 t n 1nk sn, k t k .n(5.7)k 15.3. Нам понадобится также следующая асимптотическая (при n )формула:n11 k ln n C 2n 8n 2 , || 1,(5.8)k 1где C =0,5772..
– постоянная Эйлера, а также формула221 2 k 2 6 o1.k 1n(5.9)5.4. Производящие функции. При исследовании целочисленныхслучайных величин (с. в.) удобно использовать аппарат производящихфункций (пр. ф.). Напомним, что если с. в.
η имеет распределениеP( k ) ak , k=0,1,2….,то её пр. ф. определяется равенством x Ex ak x k .k 0Эта функция определена по крайней мере для| x | 1, а внутриединичного круга она аналитична; при этом распределение с. в. η ипр. ф. x однозначно определяют друг друга, причемak k 0k!, k 0,1,2...Напомним также следующие важные свойства пр. ф.:1)если у с.
в. η существует конечный момент r-го порядка,то её факториальные моменты E s E 1... s 1 , при s r,могут быть вычислены по формуламE s s 1 ;2)если 1 ,..., n - независимые целочисленные случайныевеличины, то для производящей функции их суммы 1 ... nсправедливо соотношение x 1 x ...n x ;233)сходимостьпоследовательностиP n k ak n, k 0,1,2.,..n прираспределенийкраспределениюP k ak , k 0, (то есть ak n ak для любого фиксированного k),что символически записывается в виде L n L , эквивалентнасходимости n x x , x 0,1 .Пример. Пусть с.
в. имеет распределение Пуассона спараметром 0 : L , то есть здесьP k ekk!, k 0,1,2,.. , x kk 0k! x e e ( x1 ) .В данном случае все моменты существуют иE s s , s 1,2,...Известно, что распределение Пуассона однозначно определяетсясвоими моментами, при этомP k 1s kСходимостькs kCskss!распределениюekk!, k 0.Пуассонаможетбытьсформулирована и как сходимость соответствующих моментов: еслиE ns s ,n ,принекотором 0длялюбогофиксированного s 0 , то L n L .Аналогичные свойства имеют место и для производящихфункциймногомерныхслучайныхвеличин 1 ,...,k с24целочисленнымикомпонентами: x1 ,.., xk Ex11 ..... xk k ;приэтом1 ,..., k независимы тогда и только тогда, когда x1 ,.., xk 1 x1 ....k xk .5.5.
Центральная предельная теорема (ЦПТ). В дальнейшем мычастобудемссылатьсянаэтуключевуютеоремутеориивероятностей, поэтому мы напомним как ее общую формулировку вформе А.М. Ляпунова, так и некоторые ее важные частные случаи.Теорема Ляпунова. Пусть дана последовательность серий kn , k 1,..., n, n 1,2,... ,имеющих2 kn D knвзаимно независимых случайных величин,математическиеожидания kn E kn ,и абсолютные моменты Ckn E kn knдисперсии2, 0.Обозначим2 n2 k 1 kn, Cn2 k 1Ckn .nnТогда, если выполнено условие ЛиндебергаlimnCnn 0,(5.10)1то при n нормированная случайная величинаnk 1 kn kn nасимптотически нормальна с параметрами (0,1) , т.е. 11nlim P k 1 kn kn x x n2nxeu22 du ,(5.11)что кратко записывается так:25 1 nL kn kn N 0,1. n k 1(5.12)Отметим также некоторые следствия этой теоремы.Следствие 1.
Если с. в. 1n , 2n ,..., nn взаимно независимы ипринимают лишь значения 0 и 1, при этом n2 k 1 pk qk , n ,nгде pk pk n P kn 1 , qk qk n P kn 0 ,pk qk 1 , то приn 1L nnk 1 kn pk N 0,1.Следствие 2. Если взаимно независимые с. в.равномерноограничены: kn C , 1 k n, C 0 ,1n , 2n ,..., nnнекотораяпостоянная, и n2 k 1 D kn , когда n , тоn 1L nnk 1 kn kn N 0,1.26§6. Число циклов случайной подстановкиВернёмся к обсуждению цикловой структуры случайной nподстановкии,преждевсего,рассмотримеёважнейшуюnхарактеристику – общее число циклов n r .r 1Чтобы найти производящую функцию n t Et n , надо вобщей производящей функции (4.7) положить t1 t 2 ...
t n t :1zr expt 1 z n 1 z t .1 zr 1 r n t Fn t ,..., t z n (6.1)Воспользовавшись разложением (5.5), из (6.1) получаем искомоепредставление: n t t nn!.(6.2)В (6.2) содержится вся информация о распределении случайнойвеличиныα(n).Например,чтобыполучитьвыражениядлявероятностей P n k , достаточно разложить правую часть в (6.2)по степеням t. Такое разложение дано в (5.7), откуда получаем, что P n k t k n t sn , k , k 1, 2,..., nn!(6.3)Вычислим теперь среднее и дисперсию этой характеристики.Для этого перепишем соотношение (6.2) следующим образом:t 1 t 2t n 1 n1 n t t ...
t qi pi t ,23ni 1(6.4)27где pi 1 qi 1, i 1, ..., n 1 .i 1Заметим теперь, что i-й сомножитель в правой части (6.4) естьпроизводящая функция бернуллиевской случайной величины ξi, длякоторойPi 1 pi , Pi 0 qi ,а все произведение представляет собой производящую функцию ихсуммы, при этом они взаимно независимы (см. п.5.4 в §5). Такимобразом, α(n) можно представить в виде: n 0 1 2 ...
n1 , 0 1.Представление(6.5)удобнодля(6.5)исследованиясвойствслучайной величины α(n). Так, из него сразу же получаем, учитывая,что E i pi , D i pi qi , формулы для среднего и дисперсии:n1n1n11 ,i 0 i 1 k 1 kE n E i i 0n1n1n1nn(6.6)i1111 2.22i 1 i 1i 1 i 1 i 1 i 1k 1 kk 1 kD n D i i 0n1Рассмотрим теперь вопрос об асимптотическом поведении α(n)при n .
Воспользовавшись формулами (5.8) и (5.9), из (6.6)получаем важный результат, что как среднее, так и дисперсия числациклов α(n) при больших значениях n ведут себя асимптотически какln n :1E n ln n C O , D n ln n o16n2(6.7)28Более того, из представления (6.5), на основании ЦПТ (см.Следствие 1 в п.5.5 §5), можно сделать вывод о том, что при n 1 n ln n N 0,1.L ln n(6.8)Суммируя изложенное, можно сформулировать следующееутверждение.Теорема 2. Число циклов α(n) в случайной n-подстановке имеетраспределение (6.3), моменты которого даны в (6.6).
Если n , тослучайная величина α(n) асимптотически нормальна с параметрамиln n, ln n :L n~ N ln n, ln n .Этот результат позволяет приближённо оценивать числоподстановокs Sn ,длякоторыхчислоциклов n ln n ln n, ln n ln n , : это число приближённоравно n! .29§7. Циклы конечной длиныРассмотрим теперь вопрос о том, сколько может быть вслучайной n-подстановке циклов произвольной фиксированной длиныi (i=1,2,…).
Производящая функция случайной величины αiдлялюбого i получается из общей производящей функции (4.7) приt r 1, r i , ti t : i (t) = Eti zi1= Fn t1 ,..., t n tr 1,r i ,ti t = zexp t 1 .1 zi n(7.1)Как использовать представление (7.1) для анализа свойств величиныαi ? Проще всего найти ее факториальные моменты:Eai ss 1 , n is 0,1 z i 1 nis 1 = s z i ( 1) z i s1 z i i1 z 0 , n is 0.s n(7.2)nТаким образом (см. пример в п.5.4 §5), первые (целая часть) i факториальные моменты случайной величины αi совпадают с1аналогичными моментами распределения Пуассона П .iЕсли n→∞ , то отсюда следует, что для любого фиксированногоs0E( i )s 1.isНо это означает, что справедлива30Теорема 3.
Если n→∞ , то при любом фиксированном i 1число αi циклов длинны i в случайной n-подстановке асимптотическираспределено по закону Пуассона с параметром1.iЗамечание 1. Если рассматривать любой набор (α i1 ,α i2 ,…,α ik ),1≤i1<i2<…<ik , то совместная производящая функция этих величинесть i1 ikEt i1 ...t ik= Fn t1 ,..., tn tr 1,r i1 ,...,iki1k zj= zexpti j 1 .1 z j 1 i j nИспользуя это представление, можно показать, что при n→∞ ификсированных i1,…,ikk 1Et i1 i1 ...t ik ik → expti j 1 = j 1 i jkj 11exp ti j 1 ,i jследовательно, величины α i1 ,α i2 ,…,α ik асимптотически независимы.31§8. Циклы большой длиныИз изложенных результатов уже во многом проясняетсяасимптотический(при 1 , 2 ,..., n n )характерслучайнойцикловойn-подстановки:структурывэтойпоследовательности сначала идут асимптотически независимые1 1пуассоновские случайные величины со средними 1, , ,..., суммарное2 3же число её членов имеет порядок ln n .
Значит, на правом хвосте этойпоследовательности с большой вероятностью (т.е. с вероятностью,стремящейся к 1 при n ) должны стоять нули и, возможно,незначительноечислоотличныхотнуляэлементов.Этипредварительные заключения о случайной величине i с большимизначениями индекса i можно сделать более точными, о чем иговорится дальше.Вначале рассмотрим событиеAb n i b : i 2 i b i 2(8.1)и оценим его вероятность, когда b bn вместе с n (то естьмырассматриваем1 , 2 ,..., n ).«далёкийхвост»последовательностиИмеем:PAb n P i 2 1 P i 0 P i 1.i bВоспользуемсяi bпредставлением(7.1)длявычисления(8.2)этихвероятностей:32z1 i1k ik n s P i 0 i 0 ze z z z k1 z s0 k 0 k! i1k1 k! i k 1 i ,k n ii nzi zi zi1 i t i1 zi innP i 1 t i t z t e ze 1 z1 z izi 1 n i 1 i 1 1 ze 1 .i1 zi iОтсюда следует, что правая часть (8.2) оценивается сверху величиной1 1 1 i i 1 i i 2 .11i b1i bСледовательно,PAb n 1 0 , если b .2ii bТаким образом, при n «далёкие хвосты» i , i b цикловойструктуры с вероятностью, близкой к 1, будут содержать лишь нули иединицы.Для уточнения картины рассмотрим случайную величину b n i , которая асимптотически (при n и b bn какi bугодно медленно) совпадает с числом единиц в «хвосте» i , i b .