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

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

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

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

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