Диссертация (1137428), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Но предварительно мынапомним некоторые факты из комбинаторики и теории вероятностей,которые будут необходимы нам в качестве технического аппарата.20§5. Некоторые вспомогательные результаты5.1. Биноминальные коэффициенты. Число C mk (используется такжеmобозначение   ), 0  k  m , равное количеству k-подмножеств mk множества, называется биномиальным коэффициентом, так как этичисла фигурируют в знаменитой формуле бинома Ньютона:m1  x m   Cmk x k .(5.1)k 0Для этих чисел можно использовать следующие представления:Cmk m!mm 1    m  k  1 mk.k! m  k !k!k!(5.2)Эти формулы можно обобщить на случай, когда показательстепени m есть произвольное действительное число.

Для этогоразложим функцию 1  x  в окрестности точки x=0 в ряд Тейлора  1      k  1k 1k!1  x   1   kk 0k!x kxk .(5.3)Сравнивая коэффициенты в (5.3) с (5.2), можно записать, чтоCk  kk!, k=0,1,2,…(5.4)Формула (5.4) и определяет биноминальные коэффициенты Ck дляпроизвольногоубывающуюдействительногофакториальнуюαчерез,функциютакназываемую,t n  t t 1    t  n 1,n  1, t 0  1.21Используя эти формулы, также можем записать разложение1  z   tk 0Ckt z   k  t kk 0k!1k 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:nt n   sn, k t k , sn, k    1nkk 1 i1...ink ,(5.6)1i1 ...i nk n1то коэффициенты этого разложения s(n,k) есть, так называемые, числаСтирлинга первого рода.Черезэтичислазаписываетсятакжеиразложениевозрастающей факториальной функции, определенной в (5.5):nt n  1  t n   1nk sn, 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  o1.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  0k!, 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   ekk!, k  0,1,2,.. , x  kk 0k!  x    e  e ( x1 ) .В данном случае все моменты существуют иE s  s , s  1,2,...Известно, что распределение Пуассона однозначно определяетсясвоими моментами, при этомP  k    1s kСходимостькs kCskss!распределениюekk!, k  0.Пуассонаможетбытьсформулирована и как сходимость соответствующих моментов: еслиE ns  s ,n  ,принекотором 0длялюбогофиксированного s  0 , то L n  L    .Аналогичные свойства имеют место и для производящихфункциймногомерныхслучайныхвеличин  1 ,...,k с24целочисленнымикомпонентами:  x1 ,.., xk   Ex11 ..... xk 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Тогда, если выполнено условие ЛиндебергаlimnCnn 0,(5.10)1то при n   нормированная случайная величинаnk 1 kn   kn nасимптотически нормальна с параметрами (0,1) , т.е. 11nlim P k 1  kn   kn   x    x  n2nxeu22 du ,(5.11)что кратко записывается так:25 1 nL    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  nnk 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 nnk 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 expt 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  sn , k , k  1, 2,..., nn!(6.3)Вычислим теперь среднее и дисперсию этой характеристики.Для этого перепишем соотношение (6.2) следующим образом:t 1 t  2t  n 1 n1  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, длякоторойPi 1  pi , Pi  0  qi ,а все произведение представляет собой производящую функцию ихсуммы, при этом они взаимно независимы (см. п.5.4 в §5). Такимобразом, α(n) можно представить в виде: n  0  1   2  ...

  n1 , 0  1.Представление(6.5)удобнодля(6.5)исследованиясвойствслучайной величины α(n). Так, из него сразу же получаем, учитывая,что E i  pi , D i  pi qi , формулы для среднего и дисперсии:n1n1n11 ,i 0 i  1 k 1 kE n    E i  i 0n1n1n1nn(6.6)i1111   2.22i 1 i  1i 1 i  1 i 1 i  1k 1 kk 1 kD n    D i  i 0n1Рассмотрим теперь вопрос об асимптотическом поведении α(n)при n   .

Воспользовавшись формулами (5.8) и (5.9), из (6.6)получаем важный результат, что как среднее, так и дисперсия числациклов α(n) при больших значениях n ведут себя асимптотически какln n :1E n   ln n  C  O , D n   ln n   o16n2(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) = Eti zi1= Fn t1 ,..., t n  tr 1,r i ,ti t = zexp  t  1 .1 zi n(7.1)Как использовать представление (7.1) для анализа свойств величиныαi ? Проще всего найти ее факториальные моменты:Eai ss 1 , n  is  0,1  z i  1 nis 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→∞ , то отсюда следует, что для любого фиксированногоs0E( 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 ,...,iki1k zj= zexpti j  1  .1 z j 1 i j nИспользуя это представление, можно показать, что при n→∞ ификсированных i1,…,ikk 1Et i1 i1 ...t ik ik → expti j  1  = j 1 i jkj 11exp  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  bn   вместе с n   (то естьмырассматриваем1 , 2 ,..., n  ).«далёкийхвост»последовательностиИмеем:PAb n    P i  2  1  P i  0  P i  1.i bВоспользуемсяi bпредставлением(7.1)длявычисления(8.2)этихвероятностей:32z1 i1k ik n s P i  0  i 0  ze  z   z  z  k1 z s0  k 0 k! i1k1 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Следовательно,PAb n   1 0 , если b   .2ii bТаким образом, при n   «далёкие хвосты»  i , i  b цикловойструктуры с вероятностью, близкой к 1, будут содержать лишь нули иединицы.Для уточнения картины рассмотрим случайную величину b n    i , которая асимптотически (при n   и b  bn   какi bугодно медленно) совпадает с числом единиц в «хвосте»  i , i  b .

Характеристики

Список файлов диссертации