Главная » Просмотр файлов » Диссертация

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

Файл №1137428 Диссертация (Многомерные параметрические модели случайных подстановок и их вероятностно-статистический анализ) 3 страницаДиссертация (1137428) страница 32019-05-20СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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 .

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

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

Многомерные параметрические модели случайных подстановок и их вероятностно-статистический анализ
Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6390
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее