Диссертация (1137428), страница 5
Текст из файла (страница 5)
Ряд наиболее интересных для приложений такихконкретизаций будет детально рассмотрен ниже, а здесь получим ещенекоторые общие соотношения для структурных характеристикподстановки в рамках рассматриваемой модели.1.2.МоментыОбщая формула для смешанных факториальных моментовE j iA cij rjij(здесь a r aa 1...a r 1, r 1, a 0 1)легкополучается дифференцированием по t ij функции H nA t и, с учетом(1.3)-(1.4), имеет вид:44E ji cij r ijd i , j ij)H nA t все t 1 rijijdti , j ijr1H nA(nir i , j j z i , j ij exph z ; n! i rij Hni , j irij A n! j . n i , j irij ! i , j i H nA rij1H nA(1.6)Это представление может быть полезным при использованииметода моментов для доказательства предельных теорем, когдастепень подстановки n .Так, будет показано в последующем, что в типичных ситуацияхчисла циклов любых конечных длин распределены асимптотически(при n ) независимо и по пуассоновским законам: j L cij , i A j . i Выпишем еще формулы для математических ожиданий величинcij : для любых i A j и j 1,..., d .E cij n! j H ni A .n i ! i H nA (1.7)1.3.
Вектор чисел A j - цикловВажнейшей характеристикой случайной подстановки в модели(1.1)-(1.2) является векторC A n C A1 n,..., C Ad n45чисел её A j - циклов (в дальнейшем будем его называть A структурой подстановки). Его производящая функция находится из(1.3)-(1.4) при замене переменных t ij t j для всех i A j , j 1,..., d , и,следовательно, имеет видdFn t E t j CA j n H nA t H nA ,(1.8)zidH nA t n! z exp j t j 1 h z ; .iAj i j 1(1.9)j 1где nОтсюда, в частности, получаем представление и для маргинальныхпроизводящих функций:E tCA j n zi n! z exp j t 1 h z ; H nA .iAj i n(1.10)Примеры использования этих соотношений будут рассмотрены ниже.1.4. Максимальные длины A j - цикловПусть j n обозначает максимальную длину A j - цикласлучайной подстановки: j n maxi , i A j : cij 0, j 1,...d .Тогда для совместного распределения этих экстремальныххарактеристик случайной подстановки в рассматриваемой моделиможно записать следующую цепочку соотношений (см.(1.3)-(1.4)):46P j n s j , j 1,...d P cij 0, i s j , i A j , j 1,..., d Fn , t t1, i s jiA j , j 1,...,d0 , i s jij idz z n exp j h z ; j 1 i s j iiA j (1.11)z exph z ; .n1.5.
Представление в виде условного распределенияЭто свойство модели (как и последующее) представляет собойпроекцию соответствующего свойства общей модели (В.1) (см. [7, 8]),и формулируется следующим образом.Пусть случайные величины Z ij , i A j , j 1,..., d независимы всовокупности и при этом Z ij имеет распределение Пуассона ij спараметром ij j i .Тогда распределение случайной структурыcn cij , i A j , j 1,..., d может быть представлено в виде условного распределенияL cn L Z ij, i A j , j 1,..., d Tn n ,(1.12)гдеdTn iZ ij ;j 1 iA jпри этом P Tn n exp h1; z n exph z ; ,47где h z ; определено в (1.1).1.6. Подстановки с рандомизированной степеньюЕсли степень подстановки является случайной величиной сраспределением типа степенного ряда: z n z n f z P n , n 0,1,2,...,f z (1.13)где функция f z exphz; , то элементы структуры cij будутнезависимыми пуассоновскими случайными величинами: zi L cij j , i A j , j 1,..., d i (1.14)Здесь z 0 является свободным параметром рандомизации, значениекоторого можно подбирать специальным образом в зависимости отцели исследования.48§2.
Конкретизации d - параметрической модели2.1.Двухпараметрическая модельПусть множество X n состоит из двух подмножеств: AA X n \ A . Циклы подстановкииs , длины которых являютсяэлементами подмножества A (соответственно, подмножества A )будем называть A -циклами (соответственно, A -циклами). ОбозначимC A n ( C A n ) общее число A -циклов ( A -циклов) подстановки s :C A n ci , C A n ci ,(2.1)iAiAи введём на множестве S n вероятностную меру, приписывающуюкаждой подстановке s S n вес, пропорциональныйC n1CA n 2 A, где 1 , 2 , 1 , 2 0, параметры меры. Эта мера представляет собойспециальный случай общей меры (1.2) и имеет видC n n 1CA n 2 APA s I ici n ,H i1nA(2.2)гдеzizi H nA n! z exp 1 2 .iA i iA i nЗдесь выражение в показателе экспоненты может быть заменено на izizzi1 2 2 2ln 1 z 1 2 iA ii 1 iiA i49либо наzizizi1 2 1 1ln 1 z 2 1 ,i 1 iiA iiA iследовательно,zi H nA( ) n! z 1 z exp 1 2 iA i zi n1 n! z 1 z exp 2 1 .iA i n 2(2.3) Далее, для производящей функции парыC A n,C A nизпредставления (1.3) следует равенство:Fn t1 , t 2 ; A E t1CA n t2 CA n ПолучимC A ( n ), C A ( n ) распределенияслучайнойH nA t11 , t2 2 .H nA двумернойподстановкив(2.4)характеристикирассматриваемой(двухпараметрической) модели для различных вариантов заданийподмножества A X n .Но прежде мы выделим некоторые, представляющие исамостоятельный интерес, следствия соотношений (2.3) и (2.4).1.Положив t1 t 2 t в (2.4), получаем производящую функциюважнейшей характеристики случайной подстановки - общего числа еёцикловnC n C A n C A n ci ,i 1именно,50E t C n H nA t1 , t 2 .H nA Если, кроме того, 1 2 0, топриходим к известнойоднопараметрической модели Эвенса [23], когда каждая подстановкаs S n наблюдается с вероятностью, пропорциональной C( n ) .
Дляэтого случая представление (2.3) принимает вид: H nA n! z n 1 z 1n n! n 1... n 1 n (эта комбинаторная формула в дальнейшем будет неоднократноиспользоваться),и приходим к известному результату [4]:E t C n t n. nЭтот случай (распределение числа циклов C n в модели Эвенса)детально исследован в литературе (см. [4]), в то же времяпредставление(2.4)длядвумернойслучайнойвеличиныzi exp t1 t 2 ,iA i (2.5)CA n,CA n, принимающее в данном случае видFn t1 , t 2 ; A 1 n n! z 1 z n t2является новым результатом и для модели Эвенса.512.Если в модели (2.2) положить 2 0,1 0 , то получиммеру, сосредоточенную на подмножестве подстановок, имеющихлишь A -циклы, такие подстановки называются A - подстановками[16] и их изучению в рамках классической (равновероятной) моделипосвящена обширная литература (см.
[21,22] и библиографию в них).Предложенная здесь модель позволяет, таким образом, изучать инеравновероятные A -подстановки.Пусть S n A обозначает подмножество A -подстановок в S n .Если на этом подмножестве задана параметрическая мераPA s I iai n CA n , s S n A ,H nA iA(2.6)zi H nA n! z exp , iA i (2.7)1где теперь nто производящая функция общего числа циклов C A n такойслучайной A -подстановки имеет видFn t ; A E t CA ( n ) H nA t ,H nA (2.8)где H nA дано в (2.7).Если здесь положить 1 , то получим равновероятную наS n Aмодель:каждаяподстановкаs S n Aнаблюдаетсяс11 .вероятностью H nAЗамечание 2.
Случай 1 0, 2 0 соответствует симметричномуварианту – A -подстановкам.523.Отметим, что из представления (2.4) следует общая формуладля смешанных факториальных моментов случайных величин C A n иC A n :E C A n r1 C A n r2 r1 r2 r1 r2 Fn t1 , t 2 ; At1 t 2t t 11 1r1 2r2r1 r21r1 2r22H nA 1 , 2 / H nA ,здесь и далее, напомним,a r aa 1...a r 1, r 1, a 0 1.Введя для краткости обозначение,zizi f z exp 1 2 ,iA i iA iотсюда, в частности, получаем следующие представления для первыхдвух моментов: z n z f z z f z ,i iE C Ann1iA zi E C A n 2 z f z z n f z , iA i nE C A22 zi n z f z z n f ( z ) E C A n , iA i 21 n2 (2.9) zi n z f z z n f ( z ) E C A n , iA i z i z i n E C A n C A n 1 2 z f z z n f z . iA i iA i E C A222 n 53Эти общие представления могут быть основой для вычислениямоментов рассматриваемых характеристик случайной подстановкипри различных конкретизациях подмножества A .Далее разберем ряд наиболее популярных в литературе классовA -подстановок в контексте изложенного подхода.2.2.d -инволюцииВ теории подстановок важное значение имеют решенияуравненияs d e, s S n ,(2.10)где d натуральное число, а e единичная подстановка, эти решениямы будем называть d -инволюциями.
Известно, что такие подстановкисостоят из циклов, длины которых являются делителями числа d .Таким образом, решения уравнения (2.10) образуют подмножество A подстановок S n A при A i : i| d , d 2 , i| d означает, что i делит d .Если d 2 , то решение уравнения (2.10) называется простоинволюцией. Инволюция содержит только циклы длин 1 и 2 и,следовательно, является A -подстановкой при A 1,2 .Будем считать, чтоd - простое число, тогда функцияH nA (см.
(2.3)) для этого случая имеет вид H nA n! z n 1 z 2 exp1 2 z z d / d .(2.11)Разложим здесь экспоненту в ряд по степеням z и получим:54 1 2 r r 1 2 j dj exp1 2 z z / d z z jr! r 0 j 0 d j!m a m ,d 1 2 z ,d(2.12)m0гдеu m d 1 jam ,d u j,j m / d d j! m dj !и запишем явное представление для H nA в виде комбинаторнойсуммы:am ,d 1 2 2 nm .n m!m 0nH nA n! (2.13)Производящая функция (2.8) числа циклов в такой случайнойA -подстановке имеет, следовательно, видa t Fn t ; A n ,dan ,d j n / dj n / d2.3.t n d 1 jd j j! n jd ! n( d 1 ) j.(2.14)d j j! n jd !Подстановки с кратными длинами цикловРассмотрим такуюA - подстановку, что длины всех её цикловкратны числу d 2 , то есть A kd , k 1,2,....При таком задании множества A формула (2.3) принимает вид55H nA n! z n 1 z exp 1 2 21 z kd d k 1 k n! z n 1 z 2 exp 1 2 ln 1 z d d n! z n 1 z 2 1 z d(2.15) 1 2 / d,что можно записать в виде следующей комбинаторной суммы:H nA n!1 2 d k 2 nkdk n dk! n kd !.(2.16)Отсюда можно получить явные формулы как для совместнойпроизводящей функции (2.4) пары C A n, C A n, где в данном случаеC A n –число циклов кратныхd случайной подстановки, а C A n –число остальных её циклов, так и для производящей функции (2.8)числа циклов случайной A -подстановки.