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

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

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

В последнем случае (при 2  0,1    0 ) формула (2.16) принимает вид:H nA   n! / d n / d ,n / d !(2.17)если n кратно d , и H nA    0 в противном случае.Отметим важный частный случай d  2 . В этом случаеC A n C A n–числоцикловчётной(нечётной)длинывподстановке, и для подстановок чётной степени, то есть при n  2n0 ,из (2.8) и (2.17) следует, что:56F2 n0 t ; A  E t cA  n   t / 2n0  / 2n0tt  2t  4...t  2n0 1  2  4...  2n0  1(2.18)n0 1 t  q i  tp i ,i 1гдеp i  1  q i Изпредставления(2.18).  2iследует,чтоF2n0 , t ; Aестьпроизводящая функция независимых бернуллиевских случайныхвеличин, таким образом, в данном случае имеет место представлениеC A n  1  1   2  ...

  n0 1 ,(2.19)где слагаемые независимы иΡ i  1  1  Ρ i  0  p i , i  1,..., n0  1.Отметим, что аналогичное разложение на сумму независимыхбернуллиевскихслагаемыхобщегочислацикловслучайнойподстановки в модели Эвенса было получено в [5], поэтомурезультатыэтойработымогутбытьнепосредственнопереформулированы для рассматриваемого случая.Замечание 3.

Для изучения числа C A n  циклов нечётной длины в(2.15) надо положить 1  0, 2    0 (напомним, что d  2 ), что даётследующий результат:571  z  2 n  n     H nA    n! z         . 1 z k 0  k  2  k  2  nk n(2.20)Отсюда видно, насколько сложнее задача изучения распределениячисла циклов случайной A - подстановки (имеющей лишь циклынечётной длины).Ar  -циклы2.4.Пусть подмножество A имеет видAr   i : i  r, r  2(длины циклов ограничены числом r ). Для этого случая формула (2.3)принимает видrzi H nA r     n! z 1  z  exp 1   2   i 1 i zi n1 n! z 1  z  exp  2  1  .i r i  n 2 (2.21)Отметим, что при r  2 этот результат совпадает с (2.11) в случаеd  2.Итак, изучение совместного распределения чисел Ar  -цикловC A r  n   ir ciиA r  -цикловC A  r  n   ir ci случайнойn-подстановки в модели (2.2) может быть основано на исследованиисовместной производящей функции (2.4) этих характеристик сH nA r    , указанным в (2.21).58Рассмотренные примеры убедительно демонстрируют какдостаточнуюуниверсальностьпредложеннойметодики,такиприсущие ей сложности: за исключением отдельных случаев (типа(2.18)-(2.19)), точные решения в обсуждаемой проблематике имеютформугромоздкихкомбинаторныхвыражений,изкоторыхпроблематично извлечь конкретную информацию (хотя бы, например,вычислить средние и дисперсии величин C A n  и C A n  ).Поэтому дальнейшее продвижение в этой тематике можноосуществить лишь на пути асимптотического анализа, предполагая,что степень подстановки стремится к бесконечности, как это обычноделаетсявтеориислучайныхподстановоквклассической(равновероятной) модели.59§3.

Асимптотическая нормальность чисел конгруэнтных цикловв d -параметрической модели случайных подстановок3.1.Конгруэнтные циклы подстановкиЕсли подмножество A j в (В.1) – (В.2), имеет видA j = {k : k = ld  j, l  0},(3.1)для некоторых целых d  2 и 1  j  d , то говорят о конгруэнтныхциклах [17,c.187].В данном параграфе рассмотривается полный ( d - мерный)вектор чисел конгруэнтных циклов подстановки s  S nC(n) = (C A (n),, C A (n))1dи устанавливается его асимптотическая нормальность в общейпараметрической модели (1.1)-(1.3).

Для этого приведём необходимыепредварительные соотношения.Мера и производящая функцияЕсли подмножества A j имеют вид (3.1), то в выражении (1.1)суммыiA jziмогут быть заменены наiz ld  j1 d 2ijk/dln (1  ze 2ik/d ), ld  j =  d el 0k =1(3.2)60что проверяется непосредственно разложением логарифма в рядс учётом очевидных соотношений1 d 2i ( m j ) k/d 1, если m-j кратно d =.e0,впротивномслучаеd k =1Окончательно имеем, что в рассматриваемой нами задаче оконгруэнтных циклах основная функция H n ( ) в (1.1) принимает вид H n    n! z n G( z ), гдеd 1 dG ( z ) = exp   j e 2ijk/d ln (1 ze 2ik/d ). d j =1 k =1(3.3)МоментыОбщая формула для смешанных факториальных моментоввектора C(n) имеет вид (с учётом формул (3.2) и (3.3))rj i  rj  n zE (C A (n))r =   j [ z ]    G ( z )/[ z n ]G ( z )jjj j  iA j i   j(3.4)(напомним, (a) r = a(a  1)(a  r  1), r  1, (a0 ) = 1) .Отсюда, в частности, имеем следующие представления длясредних значений:zi E C A (n) =  j [ z n ]  G ( z )/[ z n ]G ( z ). iA i j j (3.5)Метод перевалаИзпредставленийасимптотическогоанализа(3.3)-(3.5)следует,распределениячтозадачаслучайноговекторасводится к нахождению асимптотики для коэффициентов Тейлора61[ z n ] f ( z ) аналитической функции.

Основным инструментом для этогоявляется, как известно, метод перевала. Напомним его общую схему вудобном для целей нашего исследования виде.Пусть f (z ) -аналитическая при | z |< 1 функция. Определим дляr > 0 функции (r ) = r (ln f (r )), (r ) = r (r ),(3.6)и предположим, что lim  (r ) =  , lim  (r ) =  .r 1r 1Предположим, далее, что для достаточно больших значений nсуществуеттакое > 0 , что в интервале(1   ,1)имеетсяединственный корень rn уравнения (r ) = n(3.7)(этот корень есть растущая функция от n и lim rn = 1).nТогда при n  [ z n ] f ( z) =rnnf (rn )(1  o(1)).2 (rn )(3.8)Применим этот метод к функции G(z ) , определённой в (3.3). Вданном случае формулы (3.6) принимают вид:d  d 1  2i ( j 1)k/d  e1 dj (r ) = r (ln G (r )) = r  ,= j ,2ik/d 1rdd1rej =1k =1j =1d  d 1 e 2i ( j 2)k/d j2 (r ) = r    (r ).22ik/d 2 (1r)d(1re)j=1k=1(3.9)Уравнение же (3.7) можно переписать в форме62d r jr = 1    (1  r )nj =1 dd 1 2i ( j 1)k/de 1  re 2ik/dk =1,откуда следует,что при n  rn = 1 1 O 2 .nn (3.10)С учётом этого находим:djj =1dG (rn ) = exp{ ln (1  rn )  = exp{ lnndjj =1dd 1e 2ijk/d ln (1 rn e 2ik/d )} =k =1d 1e 2ijk/d ln (1 e 2ik/d )  o(1)},k =1rnn = e  (1  o(1)), (rn ) =n2(1  o(1)).В итоге формула (3.8) принимает вид[ z n ]G( z ) =exp{ ln n  ( )}(1  o(1)),2n(3.11)где  ( ) -независящая от n , непрерывная функция от  .Заметим, далее, что если в формуле (3.11) заменить вектор  навектор t   = (t11 ,, t d  d ) , то, в соответствии с (1.1)-(1.2), мыполучимследующееасимптотическоепредставлениедляпроизводящей функции: 1 dFn (t ) = exp (t j 1) j ln n  (t  )  ( )(1 o(1)). d j =1(3.12)63Асимптотика моментовОграничимся анализом средних значений (3.5) (анализ старшихмоментов чрезвычайно трудоёмок и предполагает использование,вместо (3.8), соответствующих асимптотических разложений).Повторяя проделанный выше путь для функцийz i f j ( z) = G ( z ), iA i  j находим, чтоE C A ( n ) =jjdln n(1 o(1)), j = 1,, d .(3.13)Такая же асимптотика имеет место и для дисперсий D C A (n) ,jчто является прямым следствием основного результата, поскольку изсходимости к нормальному распределению следует и сходимостьсоответствующих моментов.643.2.Асимптотическая нормальность чисел конгруэнтныхциклов случайной подстановке (доказательство основногорезультата).Теорема 7.

Если n   , а параметры 1 ,  ,  d фиксированы,то компоненты вектора C(n) асимптотически независимы иасимптотическинормальныспараметрамисоответственноj j ln n, ln n  , j = 1 ,  , d .ddДоказательство.Введём нормированные случайные величиныC *A (n) =C A ( n) jjjdjdln n, j = 1,, d .(3.14)ln nТогда для их совместной характеристической функции всоответствии с (3.12) имеем: dE exp i x j C *A (n) =j j =1 d i x 1ln n dix d ln n d  == exp  i x j  j ln n d  n,  e 1,, e dj=1 d 1 d  i x  j ln n d= exp  i x j  j ln n d    j  e j 1 ln n  o(1)(1 o(1)) = d j =1 j =1 1 d = exp  x 2j (1 o(1)), 2 j =1 65что и требовалось показать.

Теорема доказана.Добавим к этому результату некоторые комментарии.Как хорошо известно, в модели равновероятных подстановок,когда каждая подстановка из S n наблюдается с вероятностью (n!) 1 (внашей модели надо положить все  j = 1 ), общее число циклов C (n)случайной подстановки асимптотически нормально с параметрами(ln n , ln n) [1]. Обобщение этого результата на неравновероятныйслучай:подстановкасчисломцикловнаблюдаетсяC (n)свероятностью, пропорциональной  C (n ) , где  > 0 - произвольныйпараметр,полученоЮ.И.Медведев[4]).подстановкивЭвенсом[23]Именно,такойчисломодели(см.такжецикловГ.И.Ивченко,C (n)асимптотическислучайнойнормальноспараметрами ( ln n ,  ln n) .

Модель Эвенса является частным случаемрассматриваемой в работе модели и получается из неё при1 =  =  d =  . А из приведённой теоремы следует, что в нашейdмодели число циклов C A (n) = C A (n) случайной подстановкиj =1j1 dасимптотически нормально с параметрами ( ln n ,  ln n) ,  =  j .d j =1Таким образом, сформулированный в теореме результатобобщает свойство асимптотической нормальности числа цикловслучайной подстановки (с логарифмическим порядком роста этогочисла) на достаточно широкий класс неравновероятных моделей,давая одновременно информацию о более детальной структуризациициклов подстановки. В частности, теорема даёт ответ также и навопрос о цикловой структуре подстановок с «запретами», т.е.

когда66какие-то A j -циклы в подстановке «запрещены» (соответствующиепараметры  j надо положить равными нулю).Полученныйрезультатпозволяетпостроитьновыйстатистический критерий проверки гипотезы о равновероятностиподстановок и вычислить его предельную мощность при «близких»альтернативах, что будет рассмотрено в Главе 3.Выделим, в качестве следствия, случай d = 2 .

Здесь речь идёт оциклах чётной и нечётной длины, и из теоремы, в частности, следует,что в равновероятной модели (при 1 =  2 = 1) число тех и других всреднем асимптотически равно половине общего числа циклов ln n факт, в литературе ранее не отмечавшийся.Наконец, если акцентировать внимание лишь на одном каком-токлассе конгруэнтности, скажем, Ad -циклах, то в рассматриваемоймоделиихчислоC A (n)dасимптотическинормальноN  d ln n, d ln n  и асимптотически не зависит от числа остальныхddцикловC A (n) ,такжеасимтотическиd     d 1     d 1нормального N  1ln n, 1ln n  .ddЗамечание 4.(Схема серий.) Пусть параметры рассматриваемоймодели имеют видj =jln n,  j = const > 0, j = 1,, d .(3.15)Представление (3.12) остаётся справедливым и в этом случае, имы получаем, что в схеме серий (3.15) числа конгруэнтных цикловслучайной подстановки асимптотически ведут себя как независимые67пуассоновские случайные величины с параметрами соответственно j /d , j = 1,, d .68Глава 3 .

Статистикаd - параметрической моделислучайных подстановок.§1. Асимптотическое оцениваниеВозможности точного анализа в задачах оценивания длярассматриваемойконстатируетсямоделивработедовольно[6],гдеограничены,какрассматривалсяэтослучайоднопараметрической модели. Именно, в [6] обсуждаются вопросыоценивания и проверки гипотез о параметре  модели Эвенса, когдапроизвольная подстановка s  S n наблюдается с вероятностью ,пропорциональной cs ( n ), где cs (n) - общее число циклов подстановкиs и  > 0 - неизвестный параметр.

Это частный случай нашей моделипри d = 1 и A1 = X n , и для него в [6] показано, что несмещённыеоценки сущетсвуют лишь для параметрических функций вида ( ) = a( )/ ( n) , где  ( n) =  (  1)(  n  1) иa( ) -многочленстепени не выше n , причём a(0) = 0 . В частности, для самогопараметра  несмещённой оценки не существует. В [6] построенытакже оптимальные (несмещённые с минимальной дисперсией)оценки для таких параметрических функций, при этом базой для этогоявляется известное точное распределение достаточной статистикиcs (n) . Также констатируется, что более широкие возможности вобсуждаемой проблематике предоставляет асимптотический подход,когда порядок подстановок n   , и для этого случая развиваетсясоответствующаяасимптотическаятеория,врамкахкоторой69конструируются асимптотически несмещённые и асимптотическиэффективные оценки не только для параметра  , но и для широкогокласса функций от него, а также рассчитываются соответствующиеасимптотические доверительные интервалы.В свете сказанного, при анализе нашей модели мы будемиспользовать асимптотический подход ( n   ), поскольку точноераспределение достаточной статистикив удобной дляC A (n)использования форме получить весьма проблематично, в то время какеё асимптотическое распределение, указанное в теореме 7, достаточнопросто устроено.Из теоремы 7 (см.

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

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