Диссертация (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 / 2n0 / 2n0tt 2t 4...t 2n0 1 2 4... 2n0 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 ), что даётследующий результат:571 z 2 n n H nA n! z . 1 z k 0 k 2 k 2 nk n(2.20)Отсюда видно, насколько сложнее задача изучения распределениячисла циклов случайной A - подстановки (имеющей лишь циклынечётной длины).Ar -циклы2.4.Пусть подмножество A имеет видAr i : i r, r 2(длины циклов ограничены числом r ). Для этого случая формула (2.3)принимает видrzi H nA r n! z 1 z exp 1 2 i 1 i zi n1 n! z 1 z exp 2 1 .i r i n 2 (2.21)Отметим, что при r 2 этот результат совпадает с (2.11) в случаеd 2.Итак, изучение совместного распределения чисел Ar -цикловC A r n ir ciиA r -цикловC A r n ir 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)суммыiA jziмогут быть заменены наiz ld j1 d 2ijk/dln (1 ze 2ik/d ), ld j = d el 0k =1(3.2)60что проверяется непосредственно разложением логарифма в рядс учётом очевидных соотношений1 d 2i ( 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 dG ( z ) = exp j e 2ijk/d ln (1 ze 2ik/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 iA 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 ). iA 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 2i ( j 1)k/d e1 dj (r ) = r (ln G (r )) = r ,= j ,2ik/d 1rdd1rej =1k =1j =1d d 1 e 2i ( j 2)k/d j2 (r ) = r (r ).22ik/d 2 (1r)d(1re)j=1k=1(3.9)Уравнение же (3.7) можно переписать в форме62d r jr = 1 (1 r )nj =1 dd 1 2i ( j 1)k/de 1 re 2ik/dk =1,откуда следует,что при n rn = 1 1 O 2 .nn (3.10)С учётом этого находим:djj =1dG (rn ) = exp{ ln (1 rn ) = exp{ lnndjj =1dd 1e 2ijk/d ln (1 rn e 2ik/d )} =k =1d 1e 2ijk/d ln (1 e 2ik/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)),2n(3.11)где ( ) -независящая от n , непрерывная функция от .Заметим, далее, что если в формуле (3.11) заменить вектор навектор t = (t11 ,, t d d ) , то, в соответствии с (1.1)-(1.2), мыполучимследующееасимптотическоепредставлениедляпроизводящей функции: 1 dFn (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 ), iA i j находим, чтоE C A ( n ) =jjdln 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 .ddДоказательство.Введём нормированные случайные величиныC *A (n) =C A ( n) jjjdjdln n, j = 1,, d .(3.14)ln nТогда для их совместной характеристической функции всоответствии с (3.12) имеем: dE 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 и асимптотически не зависит от числа остальныхddциклов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 (см.