On a question of limiting distribution of series in random binary sequence

Full Text

Введение. Структура серий, устойчиво воспроизводимая в случайной последовательности, является, по всей видимости, наиболее информативной статистикой критериев случайности, которые, в свою очередь, представляются актуальными для статистической физики, генетики, информационных технологий и других приложений теории вероятностей [1–6]. В указанных работах, а также в [7–9] рассматриваются двоичные последовательности и образующиеся в них серии успехов (неудач). При этом полученные результаты применимы к значительно более широкому классу последовательностей. В частности, последовательные попадания значений временного ряда стационарного процесса в межквантильный интервал, соответствующий вероятности p, совпадают с успехами в последовательности испытаний Бернулли с вероятностью p. Знаки последовательных разностей того же временного ряда образуют симметричную двоичную последовательность типа Пойа, и серия успехов в ней эквивалентна локальному восходящему тренду в исходном временном ряду. В последующем изложении будем рассматривать двоичные последовательности двух типов: марковскую, включающую в себя как 56 К вопросу о предельном распределении серий в случайной двоичной последовательности частный случай Бернулли, и образованную повыше указанной схеме Пойа, эквивалентной локальным трендам временного ряда. Подсчет серий условимся производить двояко. При установлении асимптотических законов и доказательстве предельных теорем серией успехов длиной l будем считать отрезок вида 0 1 . . . 1 0. В качестве статистик будем расl (n) сматривать число серий длиной l − Rl (n — длина последовательности) и длину максимальной серии Ln . При установлении точных законов распределения Ln в коротких и умеренно длинных последовательностях (n ≈ 103 ) будем рассматривать рекуррентные (феллеровы [5]) серии — непересекающиеся отрезки вида 1 . . . 1. В дополнение к результатам работ [1–9] будет исl следована сходимость по распределению длины максимальной серии успехов для последовательностей обоих типов. Для предельного распределения длины максимального локального тренда установлен эффект «циклического биморфизма», заключающийся в том, что с увеличением длины последовательности форма распределения циклически эволюционирует от симметричного бинарного на множестве Ln ∈ {l∗ (n), l∗ (n) + 1} до полностью вырожденного P {Ln = l∗ (n)} = 1. Закон больших чисел в смысле сходимости по вероятности будет получен в виде интервала l1 (n) Ln l2 (n). Для марковской цепи будет показано, что полученный в [1] закон тройного логарифма, обобщенный впоследствии в [3], соответствует нижней границе интервала. Верхняя граница определяется двойным логарифмом. Для максимального локального тренда доказывается, что интервал содержит не более четырёх соседних значений натурального ряда. Причём четыре значения соответствуют фазе полного вырождения предельного распределения. В остальное «время» интервал сокращается до трёх значений. 1. Асимптотические законы для максимальной длины и числа серий в марковской последовательности. Рассмотрим произвольную марковскую цепь с двумя состояниями. Используя обозначение [1, 3], запишем матрицу цепи в виде α 1−α , A= 1−β β где α = P {Xn+1 = 0 | Xn = 0}, β = P {Xn+1 = 1 | Xn = 1}, Xn ∈ {0, 1}, n 0. Начальное условие при исследовании асимптотики распределения на основании общеизвестного свойства марковских цепей, положим стационарным: p0 = P {X0 = 1} = 1−α . 2−α−β Данное условие можно интерпретировать таким образом, что начало сканирования последовательности расположено значительно правее её собственного начала. Серией успехов длины l будем считать отрезок вида 0 1 . . . 1 0. Далее l речь пойдет о предельном при n → ∞ распределении числа таких серий — (n) Rl . 57 Б а р в и н о к В. А., Б о г д а н о в и ч В. И., П л о т н и к о в А. Н. Предлагаемый и являющийся, по-видимому, наиболее простым вывод предельного закона, основанный на индикаторных переменных В. Феллера, будет опираться на следующую лемму. Лемма. Для любых двух отрезков марковской последовательности x1 , . . . , xm , y 1 , . . . , y n ; m 1, n 1, P {x1 , . . . , xm ,0, y1 , . . . , yn ∪ x1 , . . . , xm , 1, y1 , . . . , yn } = P {x1 , . . . , xm }P {y1 , . . . , yn }. Д о к а з а т е л ь с т в о. Поскольку в левой части равенства фигурируют два несовместных события, вероятность составного события равна сумме вероятностей. Слагаемые представляют собой цепочки сомножителей, такие, что на m + 1 месте стоят величины, в сумме составляющие 1, а остальные сомножители обеих цепочек попарно совпадают. Вынося общие множители, убеждаемся, что оставшийся равен 1, и лемма доказана. Естественным следствием данной леммы является её обобщение на случай произвольной длины разделяющей цепочки. Для краткости примем символичную запись следующего вида: P {x1 , . . . , xm , ∗, y1 , . . . , yn } = P {x1 , . . . , xm } P {y1 , . . . , yn }, где под «∗» будем подразумевать цепочку произвольной длины k 1 и объединение по всем её возможным комбинациям. Далее введём в рассмотрение рекуррентные вероятности образования на (l) (l) n-ном шаге серии успехов длиной l: un и индикаторные переменные Un , принимающие значения 1, если событие наступило, и 0 — в противном случае. Число серий и индикаторные переменные связаны между собой: (n) Rl n (l) (1) Uk . = k=0 В силу центральной предельной теоремы сумма (1) сходится по распределению к нормальному закону. Для вычисления параметров нормальной (l) асимптотики установим структуру ряда un . На основании следствия из леммы 1, перемножая вероятности переходов в цепочке-серии, получим  1, n = 0,   0, 1 n l, un = (2) γβ l−1 , n = l + 1,   l−1 γβ (1 − β), n l + 2, где сохранено обозначение [1, 3] γ = (1 − α)(1 − β)(2 − α − β)−1 . Поскольку (n) среднее и дисперсия величины Rl пропорциональны n с точностью до аддитивной константы, удобнее перейти к пределам: 1 µl = lim E n→∞ n n k=0 (l) Uk , σl2 1 = lim D n→∞ n n (l) Uk . k=0 Непосредственными вычислениями находим n E k=0 58 (l) Uk = 1 + γβ l−1 + (n − l − 1)γβ l−1 (1 − β). (3) К вопросу о предельном распределении серий в случайной двоичной последовательности Соответственно, предел составит µl = γβ l−1 (1 − β). (4) (l) 2 n Для вычисления дисперсии потребуется найти E . Перемноk=0 Uk жение индикаторных переменных эквивалентно совместному осуществлению событий: (l) (l) (l) (l) E Um Un = P Um = 1, Un = 1 , поэтому при непосредственном вычислении необходимо выделять цепочки и соответствующие им вероятности следующего вида: P ∗0 1 . . . 1 0 1 . . . 1 0∗ = γβ 2l−2 (1 − β)2 (1 − α), l l (5) P ∗0 1 . . . 1 00 1 . . . 1 0∗ = γβ 2l−2 (1 − β)2 (1 − α)α. l l Серии, разделенные хотя бы одним знаком, на основании леммы 1 факторизуются, т.е. P ∗0 1 . . . 1 0 ∗ 0 1 . . . 1 0∗ = µ2 . l l l Используя (5), а также очевидное соотношение (l) E Un 2 (l) = E Un = un , получаем n (l) E Uk k=0 2 = 1 + γβ l−1 + (n − l − 1)γβ l−1 (1 − β)+ + 2 γβ l−1 + (n − l − 1)γβ l−1 (1 − β) + + 2 (n − 2l − 3)γβ 2l−2 (1 − β)2 (1 − α) + (n − 2l − 4)γβ 2l−2 (1 − β)2 (1 − α)α + + (n − 2l − 3)(n − 2l − 4)γ 2 β 2l−2 (1 − β)2 . (6) Возводя (3) в квадрат, вычитая из (6) и выделяя член порядка n, окончательно получаем σl2 = γβ l−1 (1 − β) 1 − β l−1 (1 − β) (2l + 5)γ − 2(1 − α2 ) (n) Таким образом, параметры нормальной асимптотики для Rl (4), (7): √ (n) Rl ∼ N (nµl , σl n). . (7) имеют вид Для перехода к цепи Бернулли с параметром p следует положить в (4), (7) β = p, α = 1 − p, γ = p(1 − p). Устремив в (7) l → ∞, замечаем, что σl2 → µl (µl − σl2 )µl −1 ∼ O(lβ l ) . 59 Б а р в и н о к В. А., Б о г д а н о в и ч В. И., П л о т н и к о в А. Н. (n) Для исследования взаимодействия (зависимости) между величинами Rl , l = 1, 2, . . . n, воспользуемся нормальной асимптотикой. Взаимосвязь в системе нормальных величин, как известно, исчерпывается линейной, которую удобнее всего представлять в виде ковариационной либо корреляционной матрицы. По аналогии с дисперсией (7) введём в рассмотрение величины 2 σk,l = lim n→∞ 1 (n) (n) , D Rk + Rl n l > k. Ряд un для составного события (аналог (2)) в силу несовместности комбинируемых событий будет иметь вид un ∼ 1, 0, . . . , 0, µ0 , µ1 , . . . , µ1 + µ0 , µ1 + µ1 , . . . , k k k l k l 0 1 k k+1 k+2 обозначено µ0 = γβ k−1 , k l+1 1 = µk l+2 k−1 (1 γβ − β). где для краткости Производя цепочку вычислений, аналогичную (1)–(7), и обозначая для краткости µU = E n m=0 Um n m=0 Um , µU 2 = E 2 , получим µU = 1 + µ0 + µ0 − (k + 1)µ1 − (l + 1)µ1 + n(µ1 + µ1 ), l k l k l k (8) µU 2 = µU + 2 µ0 + µ0 + (n − k − 1)µ1 + (n − l − 1)µ1 + k l k l + µ0 (n − 2k − 4)µ1 + (n − k − l − 4)µ1 k l k + + 2 µ0 (n − 2l − 4)µ1 + (n − k − l − 4)µ1 + l k l + (n − k − l − 3) P 0 1 . . . 1 0 1 . . . 1 0 +P 0 1 . . . 1 0 1 . . . 1 0 k l l + 2 (n − k − l − 4) P 0 1 . . . 1 00 1 . . . 1 0 + P 0 1 . . . 1 00 1 . . . 1 0 k l + k l + k + 2 (n − 2k − 3)γβ 2k−2 (1 − β)2 (1 − α) + (n − 2k − 4)γβ 2k−2 (1 − β)2 (1 − α)α+ + (n − 2l − 3)γβ 2l−2 (1 − β)2 (1 − α) + (n − 2l − 4)γβ 2l−2 (1 − β)2 (1 − α)α + + (n − 2k − 3)(n − 2k − 4)(µ1 )2 + (n − k − l − 3)(n − k − l − 4)µ1 µ1 + k k l + (n − 2l − 3)(n − 2l − 4)(µ1 )2 . (9) l Возводя (8) в квадрат, вычитая из (9) и выделяя член порядка n, находим 2 σk,l = µ1 + µ1 + 4γβ k+l−2 (1 − β)2 (1 − α2 ) + 2γ(1 − β)2 (1 − α2 )(β 2k−2 + β 2l−2 )− k l − (2k + 5) µ1 k 2 − 2(k + l + 5)µ1 µ1 − (2l + 5) µ1 k l l 2 . И, наконец, с учётом (7) окончательно получаем 2 2 σk,l − σk − σl2 1 (n) (n) = cov Rk , Rl = n→∞ n 2 = γβ k+l−2 (1 − β)2 2(1 − α2 ) − γ(k + l + 5) , (10) lim 60 К вопросу о предельном распределении серий в случайной двоичной последовательности ρk,l 2 2 σk,l − σk − σl2 1 (n) (n) = lim ρ Rk , Rl = = n→∞ n 2σk σl (1 − β)β (k+l)/2−1 2(1 − α2 ) − γ(k + l + 5) . (11) = 1 − β k−1 (1 − β) (2k + 5)γ − 2(1 − α2 ) × × 1 − β l−1 (1 − β) (2l + 5)γ − 2(1 − α2 ) Как видно из (11), при k, l → ∞, ρk,l < 0, |ρk,l | = O (k + l)β (k+l)/2 . Соотношения (1)–(11) дают основания сформулировать следующую теорему. Теорема 1. Распределение числа длинных серий успехов в двоичной марковской последовательности имеет нормально-пуассоновскую асимптотику и образует взаимно независимую систему величин. (n) Д о к а з а т е л ь с т в о. Нормальность величин Rl при n → ∞ следует из представления (1) на основании центральной предельной теоремы и огра(n) ниченности последействия. Взаимная независимость Rl , l = l1 , l1 + 1, . . . при l1 → ∞, в свою очередь, равносильна их асимптотической некоррелированности согласно (11). И, наконец, асимптотическое равенство параметров нормального закона согласно (7), (4), а так же применимость нормальной асимптотики для распределения Пуассона [5] доказывает справедливость (n) пуассоновской асимптотики для Rl при l → ∞, n/l → ∞: µ(n, l) = σ 2 (n, l) = = λ(n, l) = nγβ l−1 (1 − β). Следует отметить тот факт, что знак корреляции коротких серий определяется согласно (11) величиной 2(1 − α2 ) − γ(k + l + 5), так что при k + l < < 2(1 − α2 )/γ − 5 корреляция положительная, при смене знака неравенства — (n) (n) отрицательная, а в случае равенства Rk и Rl независимы. Переход к цепи Бернулли осуществляется ранее указанным образом. В качестве иллюстрации ниже приведен начальный фрагмент матрицы ρk,l , k, l ∈ {1,2, . . . ,7} для симметричной (p = 1/2) цепи Бернулли:   1 −0,21 −0,218 −0,2 −0,173 −0,145 −0,118  −0,21 1 −0,214 −0,184 −0,153 −0,124 −0,099   1 −0,153 −0,123 −0,098 −0,078 −0,218 −0,214   1 −0,097 −0,076 −0,059 . ρ =  −0,2 −0,184 −0,153 −0,173 −0,153 −0,123 −0,097 1 −0,059 −0,045   −0,145 −0,124 −0,098 −0,076 −0,059 1 −0,034 −0,118 −0,099 −0,078 −0,059 −0,045 −0,034 1 На основании теоремы 1 можно установить предельную при n → ∞ форму распределения величины Ln , аналогичную полученной в [7] для симметричной цепи Бернулли. Для этого воспользуемся пуассоновской асимптотикой с (n) параметром λl = nγβ l−1 (1 − β) и взаимной независимостью Rl , l = l1 , l2 , . . . Вероятность vn (l) = P {Ln = l} на основании двух вышеуказанных условий можем представить в виде (n) vn (l) = P {Rl (n) > 0, Rm = 0, ∀m > l} = (1 − e−λl ) e−λm . m>l 61 Б а р в и н о к В. А., Б о г д а н о в и ч В. И., П л о т н и к о в А. Н. После элементарных преобразований искомую вероятность получим в виде vn (l) = exp(−nγβ l ) − exp(−nγβ l−1 ) 1 + O(nγβ n−l ) . (12) Пренебрегая бесконечно малой и переходя к действительной переменной (13) t = l − 1 + logβ n, получаем континуальный аналог независящей от n предельной формы распределения Ln : f (t) = exp(−γβ t+1 ) − exp(−γβ t ). (14) Предельная форма (14) положительно определена, удовлетворяет условию нормировки на −∞ < t < ∞, унимодальна и положительно асимметрична. Применяя при вычислении числовых характеристик (14) прием, использованный для симметричной цепи Бернулли [7], получаем C1 ln γ 1 − + , ln β ln β 2 2 1 C2 − C1 + , = 2 12 ln β (15) µLn = − logβ (n) − 2 σ Ln (16) ∞ где Ck = (−1)k e−x lnk x dx, k = 1,2 — интегралы Эйлера. Результаты 0 (12)–(16) справедливы и для цепи Бернулли. Переход осуществляется так же, как и в предыдущем случае. 2. Закон больших чисел для максимальной серии успехов в марковской цепи. Предельная форма распределения (14), составляющая содержание закона больших чисел в смысле сходимости по распределению, несмотря на весьма простой и удобный для анализа вид, тем не менее, насколько можно судить по литературе, до сих пор не введена в широкий научный обиход. Закон больших чисел для Ln в смысле сходимости по вероятности получил гораздо более широкое освещение в литературе. Вместе с тем опубликованные результаты, как представляется, могут быть получены более простым путём и в некоторой мере дополнены либо уточнены. Поскольку длина максимальной серии успехов Ln натурально определена и не предполагает, в отличие от числа успехов Sn , центрирования и нормировки, понятия нижняя и верхняя границы можно сформулировать в элементарном виде. Зададим интервал практически реализуемых значений в виде нестрогого неравенства l1 (n) Ln l2 (n) и для установления верхней границы рассмотрим правый хвост Ln : P {Ln l}. На основании взаимной неза(n) висимости и пуассоновской асимптотики Rl искомую вероятность можно представить и оценить сверху следующим образом: n P {Ln l} = 1 − m=l exp −nγ(1 − β)β m−1 < 1 − exp −nγβ l−1 < < nγβ l−1 . (17) 62 К вопросу о предельном распределении серий в случайной двоичной последовательности Согласно первой лемме Бореля—Кантелли, вероятность «меры 0» распределения Ln соответствует области сходимости ряда, члены которого имеют вид (17). В качестве мажоранты (17) возьмем ряд 1/l1+ε , который сходится при любом ε > 0 и расходится при ε 0. Таким образом, область слишком больших значений Ln будет определяться неравенством nγβ l−1 < 1/l, которое заменой переменной (13)) и последующим логарифмированием преобразуется к виду ln γ + t ln β < − ln(1 + t − logβ n). (18) Учитывая, что t > 0, ln β < 0, logβ n < 0, t(1 − logβ n)−1 = o(1), заменим (18) более строгим неравенством t > ln−1 β − ln(1 − logβ n) − t(1 − logβ n)−1 − ln γ , откуда после элементарных преобразований и обратной замены (13) окончательно получаем l > − logβ n − (1 − logβ n) ln β ln γ logβ (1 − logβ n) + + 1. (1 − logβ n) ln β + 1 ln β (19) (n) Поскольку события в пространстве величин Rl при n, l → ∞ независимы, и смена знака неравенства (18) влечет расходимость ряда (17) (простейший случай второй леммы Бореля—Кантелли), верхней границей Ln будет наибольшее натуральное число, удовлетворяющее неравенству, противоположному (19), т.е. l2 (n) = − logβ n − (1 − logβ n) ln β ln γ logβ (1 − logβ n) + (1 − logβ n) ln β + 1 ln β + 1, (20) где [ · ] означает целую часть. При установлении l1 (n) по аналогии с (17) получим n P {Ln l} = m=l+1 exp −nγ(1 − β)β m−1 < exp(−nγβ l ). (21) Следовательно, область малых значений Ln будет определяться решением неравенства exp(−nγβ l ) < 1/l. Используя вместо (13) t = l + logβ n (при этом следует учесть, что t < 0) и преобразуя (21), аналогично предыдущему случаю окончательно получаем l < − logβ n + (ln ln n − ln(− ln β)) ln n × (ln ln n − ln(− ln β)) ln n + 1 × logβ (− logβ (− logβ n)) + ln(− ln β) ln γ . (22) − ln β ln β Нижнюю границу определим как минимальное натуральное l, удовлетворяющее неравенству, противоположному (22): 63 Б а р в и н о к В. А., Б о г д а н о в и ч В. И., П л о т н и к о в А. Н. l1 (n) = − logβ n + (ln ln n − ln(− ln β)) ln n × (ln ln n − ln(− ln β)) ln n + 1 ln(− ln β) ln γ × logβ (− logβ (− logβ n)) + − ln β ln β + 1. (23) Таким образом, вывод соотношений (20), (23) служит доказательством следующей теоремы. Теорема 2. Длина максимальной серии успехов в марковской цепи при n → ∞ «почти всюду» заключена в границах l1 (n) Ln l2 (n), вычисляемых согласно (23), (20). В качестве иллюстрации на рис. 1 приведён отрезок смоделированной методом Монте—Карло траектории длины максимальной серии успехов в марковской цепи с параметрами p0 = 1/2, α = β = 1/3. Средняя линия представляет собой (15), нижняя и верхняя границы — графики зависимостей (23), (20). Для лучшей наглядности использован логарифмический масштаб оси абсцисс. 3. Длина максимальной серии успехов в марковской цепи. Точное распределение. Точное расРис. 1. Отрезок траектории случайного блуждания длины пределение Ln в симметричной цепи Бернулли максимальной серии успехов (в виде рекуррентной схемы) приведено в [8]. Для в двоичной марковской цепи обобщения на случай марковской цепи с произвольными параметрами p0 , α, β введем в рассмотрение две последовательности вероятностей (0) qn,l = P {Ln < l, Xn = 0}, (1) qn,l = P {Ln < l, Xn = 1}, n 1, l n. (24) Согласно формуле полной вероятности для последовательностей (24) будем иметь систему рекуррентных уравнений: (0) n = 1; 1 − p0 , (0) (1) αqn−1,l + (1 − β)qn−1,l , n > 1,  n = 1; 0,  (1) (0) 1 < n < l; = (1 − α)qn−1,l + βqn−1,l ,   l−1 k−1 (0) (1 − α) k=1 β qn−k,l , n l, qn,l = (1) qn,l qn,l = (1) 1, 0 (0) (1) qn,l + qn,l , n n < l; l. При l = 1 qn,l очевидно будет тождественным нулем. Точный ряд распределения на основании (24) получаем в виде P {Ln = l} = vn (l) = qn,l+1 − qn,l , n 1, 1 l n. 64 К вопросу о предельном распределении серий в случайной двоичной последовательности 4. Асимптотическое распределение максимальной длины и числа локальных монотонных трендов во временном ряду строго стационарного процесса. Предельная форма распределения комбинированных трендовых серий Ln = = max{L+ , L− } была приведена (без вывода) и исследована в [7]. Вывод n n опирается на представление цепи отношений порядка (> / <) в виде схемы Пойа и интегральный способ вычисления вероятностей. Доказательство нормально-пуассоновской асимптотики и взаимной независимости величин (n) Rl длинных серий схемы Пойа по аналогии с цепью Маркова заключается в следующем. Справедливость аналога леммы из п. 1 для цепи кодированных последовательных разностей легко доказывается с помощью интегрального способа вычисления вероятностей. Повторяя вывод и ограничиваясь для краткости малыми цепочками, в качестве исходного примем равенство, очевидное в силу несовместности комбинируемых событий P {x1 , x2 , x3 , 0, x4 , x5 ∪ x1 , x2 , x3 ,1, x4 , x5 } = = P {x1 , x2 , x3 ,0, x4 , x5 } + P {x1 , x2 , x3 ,1, x4 , x5 }. Вероятности комбинируемых событий, как показано в [8, 9], вычисляются через повторные интегралы, которые в символической записи имеют следующий вид: 1 0 1 0 ∗ ∗ dx, dx dx (25) ∗ ∗ 0 ∗ ∗ ∗ dx dx dx dx p1 = dx, dx x ∗ ∗ ∗ x ∗ ∗ ∗ ∗ ∗ dx dx dx dx 1 ∗ ∗ ∗ dx p0 = ∗ ∗ 1 , где каждый из интегралов на интервале 0 < x < 1 берется в пределах x x — если 1. С помощью элеесли соответствующее звено цепи равно 0, и 0 ментарных преобразований убеждаемся, что при сложении p0 + p1 третий по 1 счету справа интеграл в (25) становится полным , следовательно, пра0 вый тройной интеграл становится не зависящей от x константой. Тем самым 1 0 ∗ ∗ ∗ 0 ∗ ∗ dx dx dx× dx dx 1 ∗ ∗ ∗ dx p0 +p1 = ∗ ∗ dx = P {x1 , x2 , x3 }P {x1 , x2 }, и аналог леммы из п. 1 для цепи кодированных последовательных разностей доказан. Данная схема рассуждений естественным образом обобщается на произвольную длину как разделяемых, так и разделяющей цепочек, если имеет место полная сумма по всем комбинациям разделяющей цепочки. Справедливость полученного результата для стационарного процесса при любом законе распределения следует из общеизвестного факта о существовании взаимно однозначного универсального автопреобразования любой непрерывной величины в стандартную равномерную. 65 Б а р в и н о к В. А., Б о г д а н о в и ч В. И., П л о т н и к о в А. Н. (n) Для доказательства асимптотики и анализа числовых характеристик Rl в рассматриваемой схеме Пойа используем тот же прием, что и при анализе цепи Маркова в п. 1. При этом во избежание разночтений относительно длины восходящего тренда и соответствующей битовой серии в цепи кодированных последовательных разностей условимся оперировать длиной исходного временного ряда, т.е. битовому отрезку вида 0 1...1 0 будет соответствовать l−1 восходящий локальный тренд длиной l. Далее на основании леммы для цепи кодированных последовательных разностей, произведя непосредственный подсчёт вероятностей по аналогии с (2), получим  1,   0, un = l   (l+1)! ,  l2 +l−1  (l+2)! n = 0; 1 n n = l; , n l − 1; l + 1. Произведя вычисления, аналогичные п. 1, находим l2 + l − 1 1 (n) = E Rl , (26) n→∞ n (l + 2)! 4l = µl 1 + − (2l + 3)µl − 2(µ2l − µ2l+1 ), (27) (l + 1)! µl = lim 1 (n) D Rl n→∞ n σl2 = lim 1 (n) (n) = D Rk + Rl n 4k 4l = (µk + µl ) 1 + + − (2k + 3)µk − (2l + 3)µl − (k + 1)! (l + 1)! − 4(µk+l − µk+l+1 ) − 2(µ2k − µ2k+1 + µ2l − µ2l+1 ). (28) 2 σk,l = lim n→∞ Сравнивая (27) с (26), убеждаемся, что при l → ∞ σl2 → µl так, что µl − σl2 l3 . =O µl (l + 2)! Коэффициент парной корреляции ρk,l на основании (27), (28) составит ρk,l = 2 2 σk,l − σk − σl2 = 2σk σl l k =2 µl + µk − µk+l + µk+l+1 − (k + l + 3)µk µl . (29) (k + 1)! (l + 1)! Как видно из (29), (26), коэффициент корреляции строго отрицателен и при больших k, l имеет оценку k+l |ρk,l | = O √ . k!l! 66 (30) К вопросу о предельном распределении серий в случайной двоичной последовательности Начальный фрагмент матрицы ρk,l , k, l ∈ {2, 3, . . . , 7} трендовых серий имеет вид  1 −0,533 −0,352  ρ= −0,199  −0,1 −0,045 −0,533 1 −0,321 −0,172 −0,084 −0,037  −0,352 −0,199 −0,1 −0,045 −0,321 −0,172 −0,084 −0,037   1 −0,097 −0,046 −0,02  −3  , −0,097 1 −0,023 −9,862 · 10  −0,046 −0,023 1 −4,491 · 10−3  −0,02 −9,862 · 10−3 −4,491 · 10−3 1 Таким образом, соотношения (26)–(30) завершают доказательство теоремы 1 для схемы Пойа, соответствующей цепи кодированных последовательных разностей временного ряда строго стационарного процесса с непрерывным состоянием. Далее, воспроизведя схему рассуждений, использованную при выводе (12), получаем предельную форму распределения вида vn (l) = exp −(n − 1) l+1 l − exp −(n − 1) , (l + 2)! (l + 1)! 2 l n. (31) Положим в (31) n−1 = α(l+1)!, где α — константа порядка 1. Соседние члены (31) с номерами l и l + 1 представим в виде vn (l) = exp −α l+1 − exp(−αl), l+2 vn (l + 1) = exp − α l+1 − exp −α . l+3 l+2 Учитывая, что vn (l) = vn (l + 1) = 1/2, получаем α = ln 2. Таким образом, последовательность n2 (l) = [1 + (l + 1)! ln 2] ≈ [(l + 1)! ln 2] (32) соответствует фазе симметрично расщепленной двойной изолированной моды: P {Ln2 = l} ≈ P {Ln2 = l + 1} ≈ 1/2. Оценки первых отброшенных членов составляют: v2 (l − 1) = exp(−l ln 2) − exp(−(l2 − 1) ln 2) = O(2−l ); − ln 2 − ln 2 v2 (l + 2) = exp − exp = O(ln 2/l). (l + 2)(l + 4) l+3 Другую последовательность характерных значений n представим в виде n1 (l) = [(l + 1)!β(l)] и определим β(l) из условия v1 (l) → max. Подставляя n1 (l) в (31), получаем v1 (l) = exp −β l+1 − exp(−βl) ≈ exp(−β) − exp(−βl). l+2 67 Б а р в и н о к В. А., Б о г д а н о в и ч В. И., П л о т н и к о в А. Н. Заменой переменной t = exp(−β(l)) приходим к функции вида ϕ(t) = t − tl , максимум которой достигается в точке t = l−1/(l−1) . Обратной подстановкой находим β(l) = (l + 1)! ln l (l + 1)! ln l ln l ≈ . n1 (l) = 1 + l−1 l−1 l−1 (33) После подстановки n1 (l) в (31) получаем оценку v1 (l) = 1 − O(ln l/l). Следовательно, последовательность значений длины временного ряда (33) соответствует фазе изолированной моды, т.е. предельной формой распределения в этой фазе является вырожденное: P {Ln1 = l} ≈ 1. Оценки максимальных отброшенных членов составляют: v1 (l − 1) = O (1/l) , v1 (l + 1) = O (ln l/l) . Таким образом, можно считать установленным фактом «атипичность» предельной формы распределения длины максимального локального тренда в стационарном временном ряду. Её особенность заключается в том, что с возрастанием n она циклически эволюционирует от симметричного бинарного до полностью вырожденного распределения. При этом её ареал последовательно пробегает все значения натурального ряда. Точный закон распределения Ln в виде рекуррентной схемы получен в [8]. 5. Закон больших чисел для максимальной длины локального тренда. При установлении закона больших чисел для длины максимального локального (монотонного) тренда во временном ряде «белого шума» воспользуемся пуас(n) соновской асимптотикой и взаимной независимостью величин Rl трендовых серий, а также схемой рассуждений, аналогичной п. 2, заменив нестрогие неравенства на строгие. Для верхней границы будем иметь P {Ln > l} = 1 − exp −(n − 1) m>l m m+1 − (m + 1)! (m + 2)! = 1 − exp −(n − 1) = l+1 l+1 < (n − 1) . (34) (l + 2)! (l + 2)! Подставив в (34) n1 (l) вместо n и l + 1 вместо l, получаем оценку pl = P {n < n1 (l), Ln > l + 1} < ln l ln l ∼ 2 . (l − 1)(l + 3) l (35) Ряд pl сходится. Следовательно, при n (l + 1)! ln l/(l − 1) верхняя граница интервала допустимых значений не превосходит l + 1. Для нижней границы по аналогии с (22) будем иметь P {Ln < l} = exp −(n − 1) m l m+1 m − (m + 1)! (m + 2)! = = exp −(n − 1) 68 l . (36) (l + 1)! К вопросу о предельном распределении серий в случайной двоичной последовательности Подставляя (32) в (36), получаем оценку нижней границы P {n > n2 (l), Ln < l} ∼ 2−l . (37) Объединяя (35), (37), убеждаемся, что при l1 = l, l2 = l + 2 интервалы (l + 1)! ln 2 < n − 1 < (l + 3)! ln(l + 2) l+1 покрывают все множество N, пересекаясь между собой. Следовательно, согласно лемме Бореля—Кантелли при любом достаточно большом n множество практически реализуемых значений максимальной трендовой серии состоит не более чем из четырёх подряд стоящих значений: Ln ∈ {l(n), l(n) + 1, l(n) + 2, l(n) + 3}. При l2 = l1 + 1 интервалы (l + 1)! ln 2 < n − 1 < (l + 2)! ln(l + 1) l не пусты. Следовательно, внутри каждого такого интервала множество реализуемых значений сокращается до трёх: Ln ∈ {l(n), l(n) + 1, l(n) + 2}. Таким образом, длина максимальной трендовой серии гораздо «менее случайна», чем серия успехов в цепи Бернулли—Маркова, и можно считать доказанной теорему, аналогичную предыдущей. Теорема 3. Длина максимального монотонного тренда во временном ряду белого шума при n → ∞ лишь конечное число раз может выйти за границы множества четырёх подряд стоящих значений; на интервале (l + 1)! ln 2 < n − 1 < (l + 2)! ln(l + 1) l множество практически реализуемых значений сокращается до трёх: Ln ∈ {l(n), l(n) + 1, l(n) + 2}. Очевидным следствием теоремы 3 является её справедливость при переходе от временного ряда белого шума к последовательной выборке из совокупности с любым непрерывном распределением. Иллюстрацией данного закона может служить показанный на рис. 2 отрезок траектории случайного блуждания длины максимального восходящего тренда во временном ряду белого шума, полученного путем статистического эксперимента. В заключение представляется интересным отметить следующий факт. Если битовый поток, образуемый в результате кодирования последовательных разностей во временном ряду белого шума, «рассчитать на первый — второй», то образующиеся две взаимодействующие «шеренги» каждая внутри себя будет состоять из невзаимодействующих битов, т.е. будет совпадать с результатами последовательных опытов с симметричной монетой. Доказательство данного факта очевидно. Во-первых, симметричность следует из равновероятности отношений порядка между любыми двумя соседними членами временного ряда, во-вторых, независимость следует из того, что последовательные разности, номера которых отличаются более чем на «1», не содержат общих членов исходного временного ряда. 69 Б а р в и н о к В. А., Б о г д а н о в и ч В. И., П л о т н и к о в А. Н. Рис. 2. Отрезок траектории случайного блуждания максимальной длины локального восходящего тренда в стационарном временном ряду Одним из непосредственных и актуальных приложений приведенных в статье результатов, как можно заключить, например, по содержанию [6], а также по информации, размещенной в Интернете, является тестирование алгоритмических генераторов псевдослучайных чисел. В контексте подобных приложений речь идет фактически о теоретико-вероятностном обосновании и алгоритме трёхступенчатой мониторинговой фильтрации генерируемой (или любой исследуемой) последовательности. Параллельный анализ серий неудач, очевидно подчиняющихся тем же законам, удваивает количество фильтрующих ступеней, доводя его до шести.

About the authors

Vitaly A Barvinok

S. P. Korolyov Samara State Aerospace University (National Research University)

Email: barvinok@ssau.ru
(Dr. Sci. (Tech.), Corresponding member of RAS), Head of Dept., Dept. of Manufacture of Flying Machines and Quality Management in Mechanical Engineering 34, Moskovskoe sh., Samara, 443086, Russia

Valery I Bogdanovich

S. P. Korolyov Samara State Aerospace University (National Research University)

Email: bogdanovich@ssau.ru
(Dr. Sci. (Tech.)), Professor, Dept. of Manufacture of Flying Machines and Quality Management in Mechanical Engineering 34, Moskovskoe sh., Samara, 443086, Russia

Andrey N Plotnikov

S. P. Korolyov Samara State Aerospace University (National Research University)

Email: anplotnikov@ssau.ru
(Ph. D. (Tech.)), Associate Professor, Dept. of Manufacture of Flying Machines and Quality Management in Mechanical Engineering 34, Moskovskoe sh., Samara, 443086, Russia

References

Supplementary files