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

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

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

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

Обасимптотическомраспределенииэтойхарактеристикиизвестноследующее утверждение.Теорема 4. При n   и b ~ n,0    1,33Et b n P t   1 t  1k1 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Добавим к этой теореме некоторые комментарии.Прежде всего отметим, что предельная производящая функция1P 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  on.

.Наконец, опишем ещё и схему доказательства теоремы 4.Производящая функция случайной величины  b n  получается из(4.7) при t r 1, r  b, t r  t , r  b :Et b n1zr  zexpt  1  1 zr b r  n  j   t  1 kz   z   j 0  k 0 k! n1t  1kk!1 k  n b zr  r b rkS k b, n ,гдеS k b, n  1r ... r  n r ... r1kr1 ,...,rk b1.k35Далее показывается, что в условиях теоремы для чисел Sk b, n справедливы асимптотические соотношения:Sk b, n~ I k  , k  1,2,...,что и даёт в результате (8.3).Можно также показать, что вероятность события C = {случайнаяn-подстановка содержит цикл длины, большей n } при  асимптотически равна ln112.Из теоремы 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 bsk 0 11 k 1  1k 1k!I k   (8.6)k1 1I k  ,   , , s  0,1,2,...k! s  1 s 36§9.

Длина максимального циклаВажной характеристикой случайной n-подстановки являетсядлина её максимального цикла – это номер 1 n  последнего (илипервогосконца)ненулевогочленавпоследовательности  1 ,...,  n  :1 n  maxi :  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 Для доказательства слабой сходимости достаточно заметить, что371 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,x21111 x 1  x   ,x ,1  ln x32 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 E1 n  / n  0,6243...nУказанное в теореме 5 предельное распределение впервые былонайдено В.Л.

Гончаровым в 1944г., поэтому оно носит его имя.В завершение этой темы приведем ещё обобщение теоремы 5 внекоторых направлениях. Введем ещё следующие характеристикицикловой структуры:  2 n  maxi  1 n :  i  0- номер второго сконцаненулевогочленав  1 ,...,  n  ,..., m n  maxi  m1 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  xm1  ...

 x1  1 таковы, что0  x1  ...  xm  1. Тогда lim n m  j n   nx j , j  1,..., m    m  x1 ,..., xm  nxm1.1 x1... xm1x...x1m (9.4)Определенная в (9.4) функция  m x1 ,..., xm  называется m-мернойплотностью Гончарова (при m=1 она сводится к (9.2)).39§10. Общая картинаИтак,цикловая  1 ,  2 ,...,  n структураслучайнойn-подстановки при n   устроена следующим образом.«Голова» этой последовательности  i , i  b (её распределение)при любом b  on устроена так же, как совокупностьнезависимыхпуассоновскихслучайныхвеличин,Z i , i  bприэтом1L Z i    , i  1,2, ,..

, а «далёкие хвосты»  i , i  b , b  bn   (как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  PL2 n  0  PL2  0  Pвсе Z i  1 4011  PZ i  1   1  i e i  e C  0,561...i 1i 1Здесь использована формула Вейерштрасса для гамма-функции:  z   ze  1 i 1 1Czzz  ie ,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  ntt ln n   N 0,1.В то же время могут быть и очень длинные циклы: сположительной вероятностью случайная n-подстановка может иметьцикл (но только один!) любой длины n, 0    1.41Глава 2d -параметрическая модель случайныхподстановок и её анализ§1. Модель и основные соотношения для неё1.1.Мера и производящие функцииВид вероятностной меры PA  s  , s  S n , для произвольногоразбиения A   A1 , A2 ,..., Ad  (см.

(В.4)) следует из общих соотношений(В.1) – (В.2), в которых надо все параметры  i при i  A j положитьравными одномерному новому параметру для каждого j  1,..., d : притакой замене статистическая сумма (В.2) примет вид:H nA ( ) = n![ z n ]exph z ;  ,(1.1)гдеdh z ,    jj =1iA jzi,  1 ,..., d ,i(то есть определяется теперь d - мерным параметром),а соотношение (В.1) – вид d d СA j nPA ( s) = I   icij = n   jH nA ( ) , j =1iA j =1j(1.2)где, напомним, символом cij - число A j -циклов длины i  A j вподстановке s и C Aj n   iA cij - общее число A j -циклов.j42Соотношениями (1.1) – (1.2) определяется d - параметрическаямодель случайных подстановок, которая и является объектом нашегоисследования. В рамках такой модели можно рассматривать болеедетальноструктуризациюцикловойпоследовательностиcn  c1 , c2 ,..., cn  подстановки, именно, записывать её в видеcn  cij ,i  A j ,j  1,...,d.Введем соответствующую производящую функциюF n t ; A  E   t ijcij , t  tij , i  A j , j  1,..., d ,dj 1iAjтогда аналогом (В.3) является в рассматриваемой моделипредставлениеF n t ; A  H nA t   / H nA  ,(1.3)dzi H nA t    n! z exp  j iA tij  j i j 1dzin n! z exp  j iA tij  1 h z ;  ,j i j 1(1.4)где теперь: n и h  z ;   определено в (1.1).Если мы интересуемся лишь циклами определенного вида,скажем, A j0 - циклами, то из (1.3) – (1.4) следует, что совместнаяпроизводящая функция для них есть:zin! z exp  j0 iAti  1  h z ;  ji.H nA   nE iA tij0cij00Эти общие соотношения открывают новые(1.5)возможности визучении случайных подстановок.

Предложенная модель обобщает в43различных направлениях изучавшиеся ранее модели, включая их всебявкачестверавновероятнаячастныхмодельслучаев(например,соответствуетслучаюклассическая1  ...   d  1).Детальнее об этом будет сказано ниже, а здесь стоит отметить, что врамках нашей модели возможно, в принципе,исследовать иподстановки с «запретами», то есть когда какие-то A j - циклы вподстановке«запрещенные»(впредыдущихсоотношенияхсоответствующие параметры  j надо положить равными нулю), и приэтом важно знать не просто о числе остальных циклов подстановки,но и об их более детальной структуризации.Подчеркнем еще, что достоинством модели (1.1) – (1.2) являетсяее достаточная общность: она допускает конкретизации в различныхнаправлениях (выбор разбиения A   A1 ,..., Ad  , размерности d и видапараметров  j ).

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

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

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