Автореферат (1149644), страница 3

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

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

Искомую производящую функцию обозначим для данного случая Fn,m  x, uнн , uнв , uвн , uвв  и применим для ее вычислениякомбинаторный метод, описанный в указанных выше работах Л. Шапиро и Й.Х. Кима.Полученные результаты выражены теоремами 4 и 5, сформулированными и доказаннымиавтором.Теорема 4. В принятых выше обозначениях справедливо равенство:F2,2  x, uнн , uнв , uвн , uвв  1  bduнвuвн x 2.1   ac  2bd  uнвuвн x 2   a 2 duвв  bc 2uнн  uнвuвн x3   acuннuвв  bduнвuвн  bduнвuвн x 4Теорема 5. Для любого целого n (n ≥ 2) справедливо равенство:Fn,2  x, uнн , uнв , uвн , uвв   1  bdf n2uнвuвн x 2 1   ac  adf n1  2bdf n2  uнвuвн x 2 12 2 4,bc  df n1  c  uннuнвuвн x3  b 2d d  f n22  f n1 f n3   cf n3 uнвuвн xгде fi  fi  a, b, uвв , x    afi 1  bfi 2  uвв x при i  0 , f 0  1 , fi  0 при i  0 .Приведем также решение данной задачи в общей постановке.Определение 1.

Пусть (xk) k 1 , (yk) k 1 – последовательности неотрицательных це-лых чисел. Последовательность целых чисел (zk) k 0 называют осциллирующей, если онаудовлетворяет условиям: z0 = 0; если k > 0, то zk = zk–1 – yk при zk–1 > 0 и zk = zk–1 + xk приzk–1 ≤ 0.Будем полагать, что элементы последовательностей (xk) k 1 , (yk) k 1 принадлежатмножествам {0, 1,…, n}, {0, 1,…, m} соответственно. Тогда элементы осциллирующейпоследовательности (zk) k 0 принадлежат множеству V = {– m + 1, – m + 2,…, n – 1, n}.

Дуге (i, j) орграфа G = (V, D) с множеством дуг D = {(i, j)  V2| i > 0, j ≤ i или i ≤ 0, j ≥ i} припишем вес: wij = dj – i uнн при i ≤ 0, j ≤ 0, wij = dj – i uнв при i ≤ 0, j > 0, wij = bi – j uвн при i > 0,j ≤ 0, wij = bi – j uвв при i > 0, j > 0.Последовательность (zk) k 0 элементов множества V является последовательностьювершин некоторого бесконечного пути в орграфе G тогда и только тогда, когда она является осциллирующей. Если в качестве последовательностей (xk) k 1 , (yk) k 1 рассматриватьсоответственно последовательности длин плиток верхнего и нижнего ряда замощенияпрямоугольника размера 2×r, то осциллирующая последовательность (zk) k 0 строится поописанному выше алгоритму укладки плиток.

Здесь z0 = 0 соответствует начальному мо-10менту укладки, когда прямоугольник пуст. Заметим, что осциллирующая последовательность (zk) k 0 образует цепь Маркова.Для отыскания весов путей в орграфе G известен метод трансфер-матрицы. Непосредственное его применение в данной задаче требует вычисления определителя порядкаm + n. Порядок определителя удалось снизить на величину n. Полученный результат выражает следующая теорема, сформулированная и доказанная автором.Теорема 6.

Для любых целых m, n (m ≥ 2, n ≥ 2) справедлива следующая формула:det R m,mF  x, uнн , uнв , uвн , uвв  ,det Rгде R – матрица порядка m вида1  A11 d1uнн x  A121  A22 A21 A31A32 Am1,1Am1,2Am,2 Am,1d 2uнн x  A13d m2uнн x  A1,m1d1uнн x  A23d m3uнн x  A2,m11  A33d m4uнн x  A3,m1Am1,31  Am1,m1Am,3Am,m1d m1uнн x  A1,m d m2uнн x  A2,m d m3uнн x  A3,m ,d1uнн x  Am1,m 1  Am,mAij  uвнuнв x 2  s mi 1 d s  t m j 1 bt f s t i  j , i  1,2,..., m , j  1,2,..., m , fs = 0 при s < 0, fs = 1nmпри s = 0, fs = (b1 fs–1 + b2 fs–2 + … + bm fs–m) uвв x при s > 0, матрица Rm,m получается из Rвычеркиванием m-й строки и m-го столбца.В параграфе 2.6 по теореме 6 в общем виде решена задача вычисления производящей функции суммы весов разбиений с учетом типов взаимного расположения элементов.В третьей главе рассмотрены приложения произведения Адамара к вычислениюпроизводящих функций распределений некоторых статистик от серий рекуррентных событий, а также некоторых статистик от осциллирующего случайного блуждания.

В этойглаве показана возможность явного вычисления распределений некоторых характеристикслучайных последовательностей при условии, что производящие функции исходных случайных величин рациональны.В параграфе 3.1 c применением произведения Адамара вычислены производящиефункции распределений некоторых статистик от серий рекуррентных событий. Здесьрассматривается последовательность повторяющихся испытаний с возможными исходами Ej (j = 1, 2,…).

Предполагается, что испытания могут продолжаться неограниченно, ивероятности P E j1 , E j2 ,..., E jn определяются однозначно для всех конечных наборов.Пусть E  некоторое свойство конечных последовательностей: для любого набораE j1 , E j2 ,..., E jn можно сказать, обладает он свойством E или нет.Определение 21. Свойство E определяет рекуррентное событие, если:1) для того чтобы E происходило на n-м и (n + m)-м местах последовательностиE j1 , E j2 ,..., E jn  m , необходимо и достаточно, чтобы E происходило на последнем месте каждой из двух подпоследовательностей E j1 , E j2 ,..., E jn и E jn 1 , E jn  2 ,..., E jn  m ;2) если E происходит на n-м месте, то1Феллер В.

Введение в теорию вероятностей и ее приложения. В 2-х томах. Т. 1: Пер. сангл. М.: Мир, 1984. 528 с.11 P E j1 , E j2 ,..., E jn  m  P E j1 , E j2 ,..., E jn P E jn 1 , E jn  2 ,..., E jn  m .Очевидно, что с каждым рекуррентным событием E связана последовательностьчисел, определенная для n = 1, 2,… следующим образом:fn = P (E впервые происходит при n-м испытании).Введем производящую функцию F  x    n1 f n x n .

Рассмотрим формальные производящие функции от бесконечного множества не коммутирующих между собой переменных y0, y1, y2,…:U  y0 , y1 ,...  Pi1 ,i2 ,...,ik yi1 yi2 ... yik , F  y0 , y1,...   n1 fn yn1 ,i1 i2 ...ik  k  nгде Pi1 ,i2 ,...,ik  вероятность того, что рекуррентное событие E произошло в последовательности из n испытаний при испытаниях с номерами i1 + 1, i1 + i2 + 2,…, i1 + i2 +…+ ik + k, апри испытаниях с остальными номерами – не произошло.Теорема 7. Справедливо следующее равенство:U(y0, y1,…) = U(y0, y1,…) F(y0, y1,…) + F(y0, y1,…).Теорема 8.

Пусть z0  x, y0 , y1 ,...   n1 yn1 x n . ТогдаF  y0 , y1 ,...   z0  t , y0 , y1 ,...  F  t  t 1.Теоремы 7 и 8, сформулированные и доказанные автором, позволяют явно вычислить производящие функции распределений некоторых статистик от серий рекуррентныхсобытий. Их применение не требует вычисления вероятностей Pi1 ,i2 ,...,ik , что значительнооблегчает решение задач данного класса.Пример 1.

Пусть { X n }n1 – последовательность испытаний Бернулли. Рекуррентноесобытие E означает «успех» в последовательности { X n }n1 . Тогда F(x) = px(1 – qx) –1.Найдем производящую функцию U(y0, y1,…) последовательности { X n }n1 при подстановке yi = xi + 1y0, если i – четное, и yi = xi + 1y1, если i – нечетное. При этомnU  y0 , y1 ,...   n1  k 1  s  s k Pns,0k,s1 x n y0s0 y1s1 ,01где P– вероятность того, что в последовательности из n испытаний рекуррентное событие E произошло k раз, причем событие E произошло на последнем месте s0 подпоследовательностей нечетной длины и s1 подпоследовательностей четной длины.

Применяятеоремы 8 и 7, находимpx  y0  y1 xq .U  y0 , y1 ,... 2 21  x q  px  y0  y1 xq Пример 2. При подстановке y0 = x, yi = xi + 1y (i > 0) для рассмотренной выше последовательности имеемnU  y0 , y1 ,...   n1  k 1  d d k Pnd,k0 ,d x n y d ,s0 , s1n ,k0где P– вероятность того, что в последовательности из n испытаний рекуррентное событие E произошло k раз, причем событие E произошло на последнем месте d0 подпоследовательностей единичной длины и d подпоследовательностей, длина которых превышает единицу. Из теорем 8 и 7 находимd0 , dn ,k12px 1  qx  y  1 U  y0 , y1 ,... .1  x  pqx 2  y  1Пример 3. Выполняя подстановку yi = xi + 1yi (i = 0, 1,…) для рассмотренной вышепоследовательности получаемnU  y0 , y1 ,...   n1  k 1 Pn,k x n y nk ,где Pn,k  вероятность того, что рекуррентное событие E произошло в последовательности из n испытаний k раз.

По теоремам 8 и 7 находимU(y0, y1,…) = px(1 – x(qy + p)) –1.Пример 4. С помощью теорем 8 и 7 найдем производящую функцию U(y0, y1,…)рассмотренной выше последовательности при подстановке yi = xi + 1yi, если i = 0, 1,…, r, иyi = xi + 1y, если i > r. При этомnU  y0 , y1 ,...  n 1 m 0 n  k0  k1   kr  k  mгде Pn, m, k0 , k1 ,, kr , kPn, m, k0 , k1 ,, kr , kx n y0k0 y1k1 ... yrkr y k ,– вероятность того, что в последовательности из n испытаний рекур-рентное событие E произошло n  m раз, причем событие E произошло на последнем месте k0 подпоследовательностей длины 1, k1 подпоследовательностей длины 2, …, kr подпоследовательностей длины r + 1, k подпоследовательностей длины, превышающей r + 1.Имеемpxy0  p i 1 qi xi 1  yi  yi 1   pq r 1 x r  2  y  yr rU  y0 , y1 ,... 1  qx  pxy0  p i 1 qi xi 1  yi  yi 1   pq r 1 x r  2  y  yr r.Пример 5.

Выполняя подстановку yi = xi + 1y при i ≤ r и yi = 0 при i > r для последовательности из примера 1 находимnU  y0 , y1 ,...   n1  k 1 Pnr,k x n y k ,где Pnr,k – вероятность того, что в последовательности из n испытаний рекуррентное событие E произошло k раз, причем событие E произошло на последнем месте подпоследовательностей, длина которых не превышает r + 1.

Применяя теоремы 8 и 7, получаемpxy  q r x r  q r 1 x r 1   qx  1.U  y0 , y1 ,... 1  pxy  q r x r  q r 1 x r 1   qx  1В параграфе 3.2 c применением произведения Адамара вычислены производящиефункции распределений некоторых статистик от осциллирующего случайного блуждания.Определение 3. Пусть Z – случайная величина,  X n n1 , Yn n1  последовательности неотрицательных случайных величин. Последовательность Z n  n 0 ,определеннаяформулами: Z0  Z ,Z n  Z n1  sg  Z n1  Ysg  Z0 ... sg  Zn1   sg  Z n1  X sg  Z0... sg  Zn 1 , n  0,где sg  Z   1 при Z  0 , sg  Z   0 при Z  0 , sg  Z   1  sg  Z  , называется осциллиру-ющим случайным блужданием, построенным по тройке Z ,  X n n1 , Yn n1 .13Так как распределение времени n = sg (Z0) + sg (Z1) + …+ sg (Zn–1), проведѐнногоосциллирующим случайным блужданием на положительной полуоси за первые n шагов,связано с распределением случайной величины Sn,k = Z0 + X1 + … + Xn–k – Y1 – … – Yk равенством1 P (n ≤ k) = P (Sn,k ≤ 0) для всех n  0, 0 ≤ k ≤ n, то для вычисления распределения n полезна следующая теорема, доказанная автором.Теорема 9.

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

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