Статистический анализ локальных участков битовых последовательностей
В работе установлены совместные распределения числа 2-цепочек и числа 3-цепочек фиксированного вида случайной битовой последовательности. Даны примеры использования этих распределений. Возможным применением полученных формул может быть проверка гипотезы случайности расположения нулей и единиц в (0,...
Gespeichert in:
| Datum: | 2019 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Schriftenreihe: | Проблемы управления и информатики |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/180836 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Статистический анализ локальных участков битовых последовательностей / В.И. Масол, С.В. Поперешняк// Проблемы управления и информатики. — 2019. — № 5. — С. 92-105. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-180836 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1808362021-10-21T01:26:34Z Статистический анализ локальных участков битовых последовательностей Масол, В.И. Поперешняк, С.В. Методы обработки и защиты информации В работе установлены совместные распределения числа 2-цепочек и числа 3-цепочек фиксированного вида случайной битовой последовательности. Даны примеры использования этих распределений. Возможным применением полученных формул может быть проверка гипотезы случайности расположения нулей и единиц в (0, 1)-последовательности конечной длины. Розглянуто сумісні розподіли числа 2-ланцюжків і числа 3-ланцюжків фіксованого вигляду випадкової (0, 1)-послідовності, які дозволяють здійснювати статистичний аналіз локальних ділянок цієї послідовності. Сформульовано і доведено дві теореми. The joint distributions of the number of 2-chains and the number of 3-chains of a fixed form of a random (0, 1)-sequence, which allow a statistical analysis of local sections of this sequence, were examined. Two theorems are formulated and proved. 2019 Article Статистический анализ локальных участков битовых последовательностей / В.И. Масол, С.В. Поперешняк// Проблемы управления и информатики. — 2019. — № 5. — С. 92-105. — Бібліогр.: 4 назв. — рос. 0572-2691 http://dspace.nbuv.gov.ua/handle/123456789/180836 519.237.3 + 519.669 + 681.51 ru Проблемы управления и информатики Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Методы обработки и защиты информации Методы обработки и защиты информации |
| spellingShingle |
Методы обработки и защиты информации Методы обработки и защиты информации Масол, В.И. Поперешняк, С.В. Статистический анализ локальных участков битовых последовательностей Проблемы управления и информатики |
| description |
В работе установлены совместные распределения числа 2-цепочек и числа 3-цепочек фиксированного вида случайной битовой последовательности. Даны примеры использования этих распределений. Возможным применением полученных формул может быть проверка гипотезы случайности расположения нулей и единиц в (0, 1)-последовательности конечной длины. |
| format |
Article |
| author |
Масол, В.И. Поперешняк, С.В. |
| author_facet |
Масол, В.И. Поперешняк, С.В. |
| author_sort |
Масол, В.И. |
| title |
Статистический анализ локальных участков битовых последовательностей |
| title_short |
Статистический анализ локальных участков битовых последовательностей |
| title_full |
Статистический анализ локальных участков битовых последовательностей |
| title_fullStr |
Статистический анализ локальных участков битовых последовательностей |
| title_full_unstemmed |
Статистический анализ локальных участков битовых последовательностей |
| title_sort |
статистический анализ локальных участков битовых последовательностей |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2019 |
| topic_facet |
Методы обработки и защиты информации |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/180836 |
| citation_txt |
Статистический анализ локальных участков битовых последовательностей / В.И. Масол, С.В. Поперешняк// Проблемы управления и информатики. — 2019. — № 5. — С. 92-105. — Бібліогр.: 4 назв. — рос. |
| series |
Проблемы управления и информатики |
| work_keys_str_mv |
AT masolvi statističeskijanalizlokalʹnyhučastkovbitovyhposledovatelʹnostej AT poperešnâksv statističeskijanalizlokalʹnyhučastkovbitovyhposledovatelʹnostej |
| first_indexed |
2025-07-15T21:10:39Z |
| last_indexed |
2025-07-15T21:10:39Z |
| _version_ |
1837748812099092480 |
| fulltext |
© В.И. МАСОЛ, С.В. ПОПЕРЕШНЯК, 2019
92 ISSN 0572-2691
УДК 519.237.3 + 519.669 + 681.51
В.И. Масол, С.В. Поперешняк
СТАТИСТИЧЕСКИЙ АНАЛИЗ ЛОКАЛЬНЫХ
УЧАСТКОВ БИТОВЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Ключевые слова: s-цепочки, битовая последовательность, случайность, ло-
кальные участки, совместное распределение.
Введение
Всесторонний статистический анализ битовой последовательности, получае-
мой на выходе генераторов псевдослучайных чисел, не исключает проверки гипо-
тезы случайного расположения нулей и единиц на некоторых интервалах неболь-
шой длины, например до ста битов (вариант классификации битовых последова-
тельностей согласно их длине приведен в [1]). Необходимость в проверке этой
гипотезы возникает также в иных областях, например в химической промышлен-
ности при производстве синтетических волокон в процессе анализа причин обры-
ва нити в ходе ее формирования. Здесь (0, 1)-последовательность получается по
результатам взвешивания отрезков нити на небольшом участке до ее обрыва с по-
следующим сравнением с номинальным весом этих отрезков.
В тестах для проверки гипотезы случайности расположения нулей и единиц в
(0, 1)-последовательностях предполагается, что длина (0, 1)-последовательности
велика (см., например, [2]). Это предположение связано с использованием асимп-
тотических приближений для точного распределения статистики (как правило,
одномерной) соответствующего теста.
В данной работе предлагаются точные совместные распределения некоторых
статистик (0, 1)-последовательности длины ,n 1 .n Для 20n (т.е. для би-
товой последовательности малой длины [1]) приведены таблицы, содержащие
числовые значения соответствующего распределения. Эти таблицы, равно как и
предлагаемые их графические представления, могут быть использованы для про-
верки гипотезы случайности расположения нулей и единиц.
1. Постановка задачи
Рассмотрим последовательность случайных величин
1 2 ... ,n (1)
где {0, 1},i 1, 2,..., ,i n 0.n
Подпоследовательность 1 1...j j j s последовательности (1) будем
называть s-цепочкой, 1, 2,..., 1,j n s 1, 2,..., .s n Обозначим 1 2( ... )st t t
число s-цепочек в последовательности (1), которые совпадают с 1 2 ... ,st t t где
{0, 1},it 1, 2,..., .i s Сформулируем условие.
Условие. Последовательность (1) состоит из ,n 0,n независимых одинако-
во распределенных случайных величин; вероятности событий { 1},i { 0}i
известны и равны P{ 1} ,i p P{ 0} ,i q 1,p q 1, 2,..., .i n
В данной работе рассмотрены совместные распределения случайных величин
1 2( ... ),st t t 1 2( ... ),st t t где , {0,1},j it t 1, 2,..., ,j s 1, 2,..., ,i s для некото-
рых значений s и .s Перейдем к точным формулировкам.
Международный научно-технический журнал
«Проблемы управления и информатики», 2019, № 5 93
2. Совместные распределения числа 2-цепочек
и числа 3-цепочек фиксированного вида
Теорема 1. Пусть выполняется сформулированное выше условие, ,n 1,k
2 ,k 3,k ,t 1t — целые числа, такие, что 1 0,k 2 0,k 3 0,k 1max(2 , 3),n k
1, {0,1}.t t Тогда
1
101
1
1
1
1
1
1
* * *
1 2
0
P{ ( ) , ( 1 ) ( ,0 ) } i
i
k
m
n k
mm
k
m k i
k
t t k t t t t k p q C C
(2)
где 0 1,m n m символ обозначает суммирование по всем целым неотрица-
тельным числам 0 и 1, таким, что 0 1 1 22 ,k k
* 1 ;t t
2 2 1
1 1
1
01
1 1
*
* *
1 1 1 1 1 2P{ ;( , ( ) })
t t
n k
m k k k
k m k m
m
m k
t t k t t t k p q C C C
(3)
3 32 2
1 1 1
1
0
1
1
1 1
0
1
* * *
31 2P{ ( ) , ( 1 ) ), .0 }(
n k
mm
m k
k kk k
k k m k m k
t t k t t k t t k p q C C C C
(4)
Пример. Для (0, 1)-последовательности вида
0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 0 1
значениями случайных величин *( ),t t *( 1 ),t t *( 0 )t t и *( ),t t где {0,1},
для 1t являются соответственно числа 5, 3, 2 и 5.
Доказательство. Проверим соотношение (3). Обозначим количество единиц
в случайной последовательности (1). Случайная величина имеет биномиальное
распределение с параметрами ( , ),n p что позволяет записать для 0,1, 2, ...,m n
вероятность события { },m а именно:
P{ } .m m n m
nm C p q (5)
С помощью формулы полной вероятности находим
1
1 2 1 1 2 1
0
P{ , P{ } P{ / },} ,
n
m
A A m A A m
(6)
где
def
*
1 1 1 1{ ,( ) }A t t k
def
*
2 1 1 2( ) .{ }A t t t k
Покажем, что
1 2 2 1
1 1 *
1
1 2 1P{ , / } ( )
t t
k k k
k m k m
m
nA A m C C C C
. (7)
Введем следующие обозначения: 1( , )n m — множество всех n-мерных
(0, 1)-векторов, каждый из которых содержит 1m единиц и 0m нулей, 0 1 ;m m n
0 1 1 2 1( , , , ; )D m m k k t — подмножество множества 1( , )n m , которое содержит
все попарно различные векторы, начинающиеся с элемента 1,t заканчивающи-
еся элементом *
1 ,t содержащие 1 2( )k k цепочек вида * *
1 1 1 1( );t t t t t Q — общее
число векторов , 1( , ),n m каждый из которых имеет 1 2( )k k цепочек ви-
да * *
1 1 1 1( ).t t t t t
94 ISSN 0572-2691
Используя принятые обозначения, получаем
1
2 11 1P{ , / } ( ( ,, ) )nA m Q mA (8)
*
* *
*
1 2 1
0 0
( , , , ; )
t t
t t
mm
t t t t
Q D m m k k t
. (9)
Далее убедимся в том, что
2 2 1
1 1 *
1 1
0 1 1 2 1 1 1
( , , , ; ) .
t t
k k k
k m k m
C CD m m k k t C
(10)
Действительно, для произвольного вектора , 0 1 1 2 1( , , , ; ),D m m k k t во-
первых, событие 1 2{ , }A A имеет место тогда и только тогда, когда
( )
2 1 1 0,
t
k k (11)
где
( )
1
t
— число t -серий длины единица каждая в векторе , {0,1};t во-вто-
рых, перестановка между собой t -серий не изменяет чисел 1k и 2.k Поэтому
вектор определяется однозначно, если
зафиксировано одно из
( )
1
1
t
k
C
возможных размещений t -серий длины еди-
ница каждая;
зафиксировано одно из возможных разбиений
( )
1
t
tm t -элементов на
( )
1 1
t
k t -серий, длина каждой из которых равняется двум или больше двух;
зафиксировано одно из возможных разбиений *t
m *t -элементов на 1k *t -се-
рий, длина каждой из которых не меньше единицы.
Между указанными разбиениями множества t -элементов ( *t -элементов) и
решениями уравнения
( )
1 1
( ) ( ) ( ) ( )
1 1 2 ... t
t t t t
t
k
m x x x
(12)
1
( *) ( *) ( *) ( *)
* 1 1 2( ... )
t t t t
t k
m x x x (13)
в целых числах, каждое из которых не меньше двух (единицы), существует вза-
имно-однозначное соответствие. В свою очередь, число решений уравнения (12)
или (13), таких, что
( )
2
t
jx ,
( )
1 11, 2, ...,
t
j k
( *)
( 1
t
jx , 11, 2, ..., ),j k равня-
ется
( )
1 1 1
1 *
1 1
1 1
( ).
t
t t
k k
m k m
C C
Таким образом, с учетом (11) произведение 2 2 1
1 1 *
1 1
1 1t t
k k k
k m k m
C C C
дает общее
число элементов множества 0 1 1 2 1( , , , ; ),D m m k k t что доказывает (10). Принимая
во внимание (9), (10) и равенство
1 1
1 1... ,nnC C C
(14)
Международный научно-технический журнал
«Проблемы управления и информатики», 2019, № 5 95
получаем соотношение 2 2 1
1 1 *
,
t t
k k k
k m k m
Q C C C
которое совместно с (8) и равен-
ством
1
1( , )
m
nn m C (15)
приводит к (7). В свою очередь, из (5)–(7) непосредственно следует (3).
Соотношения (2) и (4) можно проверить, используя схему доказательства
равенства (3).
Частный случай соотношения (2) установлен в [3].
3. Примеры к теореме 1
3.1. Иллюстрация использования равенства (2). В табл. 1 и на рис. 1 при-
ведено использование соотношения (2) для 1/ 2,p q малой выборки длины ,n
20,n и некоторых значений 1,k 2.k
В первом столбце табл. 1 помещены все возможные варианты значений 1k и 2 ,k
для которых вероятность * * *
1 2P{ ( ) , ( 1 ) ( 0 ) 0,0} 1.t t k t t t t k Во втором
столбце даны вероятности (в неубывающем порядке) * *
1P{ ( ) , ( 1 )t t k t t
*
2( }0 )t t k для пар чисел 1 2( , ),k k указанных в первом столбце.
В каждой строке третьего столбца дана сумма накопленных вероятностей до
реализации события * * *
1 2{ ( ) , ( 1 ) ( 0 })t t k t t t t k включительно, где 1k и 2k
указаны в этой же строке в первом столбце.
Таблица 1
(k1, k2) P Pc
(k1, k2) P Pc
(7, 3) 0,012149811 0,100008011 (5, 7) 0,018882751 0,132255554
(7, 5) 0,013364792 0,113372803 (7, 4) 0,020047188 0,152302742
(5, 7) 0,018882751 0,132255554 (3, 3) 0,026035309 0,178338051
(7, 4) 0,020047188 0,152302742 (6, 3) 0,026435852 0,204773903
(3, 3) 0,026035309 0,178338051 (3, 5) 0,02863884 0,233412743
(6, 3) 0,026435852 0,204773903 (6, 6) 0,031723022 0,265135765
(3, 5) 0,02863884 0,233412743 (5, 3) 0,037765503 0,302901268
(6, 6) 0,031723022 0,265135765 (4, 3) 0,03818512 0,341086388
(5, 3) 0,037765503 0,302901268
(3, 4) 0,04295826 0,384044647
(4, 3) 0,03818512 0,341086388
Например, для 1 7k и 2 3k имеем * * *
1 2P{ ( ) , ( 1 ) ( 0 ) }t t k t t t t k
,01210 49811,
* * *
1 2P P{ ( ) , ( 1 ) ( },0 )c t t k t t t t k где знак суммирова-
ния распространяется на все пары 1 2( , ),k k для которых *
1P{ ( ) ,t t k
* *
2( 1 ) ( 0 ) ,0121498 1} 10 .t t t t k
На рис. 1 представлена пузырьковая диаграмма [4], в которой первый
параметр (горизонтальная ось) — значение 1,k второй (вертикальная ось) —
96 ISSN 0572-2691
значение 2 ,k третий (размер пузырька) — вероятность осуществления со-
бытия *
1{ ( ) ,t t k * *
2( 1 ) ) },( 0t t t t k выраженная в процентах.
Например, на рис. 1 при 1 5k и 2 5k вероятность осуществления собы-
тия * * *
1 2{ ( ) , ( 1 ) ( 0 })t t k t t t t k в процентах равняется 11,10 %.
Рис. 1
3.2. Иллюстрация использования равенства (3) . В табл. 2 и на рис. 2
приведено использование соотношения (3) для 1/ 2,p q малой выборки
длины ,n 20,n и некоторых значений 1k и 2.k
Таблица 2
(k1, k2) P Pc
(k1, k2) P Pc
(2, 2) 0,01108932 0,0622549 (4, 1) 0,04721069 0,3276072
(7, 3) 0,01214981 0,0744047 (3, 2) 0,05311203 0,3807192
(7, 1) 0,01336479 0,0877695 (5, 1) 0,05455017 0,4352694
(6, 4) 0,01952648 0,107296 (6, 3) 0,05727768 0,492547
(7, 2) 0,02004719 0,1273432 (6, 2) 0,0715971 0,5641441
(4, 4) 0,02318382 0,150527 (4, 3) 0,09273529 0,6568794
(3, 1) 0,02451324 0,1750402 (5, 3) 0,10910034 0,7659798
(3, 3) 0,03034973 0,20539 (4, 2) 0,11128235 0,8772621
(6, 1) 0,03682137 0,2422113
(5, 2) 0,12273788 1
(5, 4) 0,03818512 0,2803965
Интерпретация табл. 2 аналогична интерпретации табл. 1.
На рис. 2 дана пузырьковая диаграмма, в которой первый параметр (го-
ризонтальная ось) — значение 1,k второй (вертикальная ось) — значение 2 ,k
третий (размер пузырька) — вероятность осуществления события *
1 1P{ ( )t t
1,k *
1 1 2( ) }t t t k , которая представлена в процентах.
k 2
– 1
0
1
2
3
4
5
6
7
8
9
1 2 3 4 5 6 7 8 9 k 1
Международный научно-технический журнал
«Проблемы управления и информатики», 2019, № 5 97
Рис. 2
3.3. Иллюстрация использования равенства (4). В табл. 3 приведено ис-
пользование соотношения (4) для 1/ 2p q , малой выборки длины ,n 20,n и
некоторых значений 1,k 2k и 3.k
Таблица 3
(k1, k2, k3) P Pc
(k1, k2, k3) P Pc
(6, 1, 2) 0,010815 0,280055 (4, 1, 3) 0,019638 0,522853
(6, 2, 1) 0,010815 0,29087 (4, 3, 1) 0,019638 0,542491
(5, 1, 4) 0,011015 0,301885 (5, 1, 3) 0,02203 0,564521
(5, 4, 1) 0,011015 0,3129 (5, 3, 1) 0,02203 0,586551
(3, 1, 2) 0,011716 0,324615 (6, 2, 3) 0,024033 0,610583
(3, 2, 1) 0,011716 0,336331 (6, 3, 2) 0,024033 0,634616
(6, 3, 3) 0,013733 0,350064 (3, 2, 2) 0,025775 0,660391
(3, 2, 3) 0,014319 0,364384 (4, 3, 3) 0,026184 0,686575
(3, 3, 2) 0,014319 0,378703 (6, 2, 2) 0,027037 0,713612
(6, 1, 3) 0,01442 0,393123 (5, 3, 3) 0,031471 0,745083
(6, 3, 1) 0,01442 0,407542 (4, 2, 3) 0,039276 0,784359
(5, 1, 2) 0,015736 0,423278 (4, 3, 2) 0,039276 0,823635
(5, 2, 1) 0,015736 0,439013 (5, 2, 2) 0,04406 0,867695
(5, 2, 4) 0,015736 0,454749 (5, 2, 3) 0,04406 0,911755
(5, 4, 2) 0,015736 0,470485 (5, 3, 2) 0,04406 0,955814
(4, 1, 2) 0,016365 0,48685
(4, 2, 2) 0,044186 1
(4, 2, 1) 0,016365 0,503215
Пояснения к табл. 3 аналогичны пояснениям к табл. 1.
4. Совместные распределения
числа 2-цепочек и числа 3-цепочек вида *
1 1t t и
*
,t t {0, 1}
Теорема 2. Пусть выполняется сформулированное выше условие, ,n 1,k 2 ,k
3,k ,t 1t — целые числа, такие, что 1 0,k 2 0,k 3 0,k 1max{2 , 3},n k
1, {0,1}.t t Тогда
– 1
0
1
2
3
4
5
6
k 2
1 2 3 4 5 6 7 8 9 k 1
98 ISSN 0572-2691
1
01
1 1
*
1 1 1 2P{ ( ) , ( 1 ) ( 0 ) }
n k
mm
m k
t t k t t t t k p q
* 1 *
*
1 1
2
1 1
{ , 1}
( , ) ( 2)t t t t
t
m i k
t t t t tii m i
i k k
C C Z m i m i C m Z
, (16)
где — суммирование по всем целым неотрицательным числам t и *t , таким,
что * 2,t t k 1 2( 0) ( 1)t tZ m k k 2 2 1( 1) ( 1) ( 0, 2)tm k k k
1 2 1 2( ( 0) ( 1) ( 1, 0)),k k n k k ( )E — индикатор события ,E ( )E
1 ( ),E
1
1
def
, если 1;
( , ) 1, если 0;
0 в остальных случаях;
b
aC a b
Z a b a b
1
01
1 1
*
1 1 1 2P{ ( ) , ( ) }
n k
mm
m k
t t k t t t k p q
21
*
1 1
2
, 1
( , ) ( 2)t
t
m k ik
t t t tim
i k k
C C Z m i m i k m Z
; (17)
*
1 1 1 2P{ ( ) , ( * ) }t t k t t t k
1
2 1 201
*
1 1 1 1
1
, 1
( 2)
t t
n k
k k kmm i
t ti m m i
m k i k k
p q C C C m Z
; (18)
1
01
1 1
*
1 1 1 2 3P{ ( ) , ( ) , ( * ) }
n k
mm
m k
t t k t t t k t t t k p q
2 3 1 3
*
1 1
2
21 1
{ , 1}
( , ) ( 2)t
t
k m i k k k
t t t ti i m i
i k k
C C Z m i m i k C m Z
, (19)
где 1 2 3( 0) ( 1)t tZ m k k k 2 3 2 3 1( 1) ( 1) ( 0, 2)tm k k k k k
1 2 3 1 2 3( ( 0) ( 1) ( 1, 0)).k k k n k k k
Доказательство. Проверим соотношение (17). Аналогично (6) находим
1
1 2 1 1 2 1
0
P{ , } P{ } P{ , / },
n
m
B B m B B m
(20)
где
def
*
1 1 1 1{ ,( ) }B t t k
def
2 2 .{ ) }(B t t t k
Пусть Q — число всех векторов , 1( , ),n m каждый из которых име-
ет 1 2( )k k 2-цепочек вида *
1 1t t (3-цепочек вида ).t t t Тогда с учетом (15) имеем
1 1
1 2 1P{ , / } ( ) .
m
nB B m C Q (21)
Далее установим формулу для нахождения числа .Q Рассмотрим подмно-
жество 0 1 1 2 1( , , , ; ) ( , )D m m k k t n m всех попарно отличных векторов, каж-
Международный научно-технический журнал
«Проблемы управления и информатики», 2019, № 5 99
дый из которых начинается и заканчивается элементом ,t содержит 1 2( )k k
2-цепочек вида *
1 1t t (3-цепочек вида ).t t t Отметим, что произвольный век-
тор , 0 1 1 2( , , , ; ),D m m k k t обладает таким свойством: перестановка в век-
торе между собой -серий, {0,1}, не изменяет чисел 1k и 2.k Это поз-
воляет записать равенство
*
*
* * 1 2
0
( , , , ; )
t
t
m
t t tQ D m m k k t
* *
* *
* * * 1 2
0 1
( , , 1, ; )
t t
t t
m m
t t t tD m m k k t
. (22)
Покажем, что
2 1 1
1 *
1 1
0 1 1 2 1 1 21 1
( , , , ; ) ( 1, 1).t
t
m k k k
t tk m
D m m k k t С C Z m k m k k
(23)
Действительно, для произвольного вектора , 0 1 1 2( , , , ; ),D m m k k t имеем
( )
2 11 2 2,
t
tk m k (24)
где
( )
1
t
— число t -серий длины единица в векторе . Для 2tm и * 1tm эле-
мент множества 0 1 1 2( , , , ; )D m m k k t определяется однозначно, если
зафиксировать одно из
( )
1
1 1
t
k
С
возможных размещений t -серий длины еди-
ница каждая;
зафиксировать одно из возможных разбиений числа *tm на 1k *t -серий,
длина каждой из которых не меньше единицы;
зафиксировать одно из возможных разбиений числа
( )
1
t
tm на
( )
1 11
t
k
t -серий, длина каждой из которых не меньше двух.
Отсюда с учетом (24) получаем (23). (Если * 0,tm то в формуле (23) пола-
гаем 1
* 1
1
1 1{1, если 0; 0, если 1}.
t
k
m
C k k
С помощью (14) и (23) находим для 2tm и * 0tm
*
* 0
* * 1 2( , , , ; )
t
t
m
t t tD m m k k t
2 1 1
1 *
1
1 1 21
( 1, 1),t
t
m k k k
t tk m
C C Z m k m k k
(25)
* *
* 0 * 1
* * * 1 2( , , 1, ; )
t t
t t
m m
t t t tD m m k k t
2 1 1
1 *
1 1 2( , ).t
t
m k k k
t tk m
C C Z m k m k k
(26)
100 ISSN 0572-2691
Из (22), (25) и (26) следует равенство
21
*
1 1
2
{ , 1}
( , ) ( 2),t
t
m k ik
t t tim
i k k
Q C C Z m i m i k m
которое вместе с (20), (21), (5) и очевидными соотношениями
1 1 2*
1 1 1 2
(P{ *}) , если 0,
P{ ( ) , ( ) }
0 в остальных случаях,
n
tt m k k
t t k t t t k
*
1 1 1 2P{ ( ) , ( ) }t t k t t t k
1
1 1 1 2
1
1 1 1 2
(P{ *}) P{ }, если 1, 0,
( 1)(P{ *}) P{ }, если 1, 0,
0 в остальных случаях
n
t
n
t
t t m k k
n t t m k k
приводит к (17).
Используя схему доказательства равенства (17), можно проверить (16),
(18) и (19).
5. Примеры к теореме 2
5.1. Иллюстрация использования равенства (16). В табл. 4 и на рис. 3 при-
ведено использование соотношения (16) для 1/ 2p q , малой выборки длины
,n 20,n и некоторых значений 1,k 2k .
Таблица 4
(k1, k2) P Pc (k1, k2) P Pc
(3, 7) 0,010046 0,160690308 (5, 7) 0,0258274 0,415276527
(7, 4) 0,011816 0,172506332 (6, 6) 0,0259638 0,441240311
(3, 2) 0,0121012 0,184607506 (4, 6) 0,0309591 0,47219944
(3, 6) 0,0121164 0,196723938 (6, 5) 0,0358648 0,50806427
(7, 5) 0,0131178 0,209841728 (6, 3) 0,0363922 0,544456482
(3, 5) 0,013607 0,223448753 (4, 2) 0,0369673 0,581423759
(3, 3) 0,0137167 0,237165451 (4, 5) 0,0379229 0,619346619
(3, 4) 0,0142107 0,251376152 (5, 6) 0,0386162 0,657962799
(4, 8) 0,015398 0,266774178 (6, 4) 0,0412607 0,699223518
(5, 8) 0,015399 0,282173157 (4, 3) 0,0421267 0,741350174
(6, 7) 0,0161362 0,298309326 (4, 4) 0,0421772 0,783527374
(6, 2) 0,0196438 0,31795311 (5, 2) 0,0471888 0,830716133
(4, 7) 0,0229654 0,340918541 (5, 5) 0,0509062 0,881622314
(5, 1) 0,0231276 0,364046097 (5, 4) 0,0590916 0,940713882
(4, 1) 0,025403 0,38944912 (5, 3) 0,0592861 1
Табл. 4 составлена из столбцов, содержание которых аналогично содержанию
столбцов табл. 1.
Международный научно-технический журнал
«Проблемы управления и информатики», 2019, № 5 101
Рис. 3
На рис. 3 дана пузырьковая диаграмма, в которой первый параметр (гори-
зонтальная ось) — значение 1k , второй (вертикальная ось) — значение 2k ,
третий (размер пузырька) — вероятность осуществления события *
1 1 1{ ( ) ,t t k
2( 1 ) ( 0 })t t t t k , представленная в процентах.
5.2. Иллюстрация использования равенства (17) . В табл. 5 и на рис. 4
приведено использование соотношения (17) для 1/ 2p q , малой выборки
длины ,n 20,n и некоторых значений 1,k 2k .
Таблица 5
(k1, k2) P Pc
(k1, k2) P Pc
(3, 6) 0,011425 0,099241257 (4, 0) 0,0352583 0,363793373
(3, 1) 0,0120115 0,111252785 (6, 2) 0,0405884 0,404381752
(3, 5) 0,0139112 0,125164032 (4, 4) 0,040679 0,44506073
(3, 2) 0,0145435 0,139707565 (4, 1) 0,0458231 0,490883827
(5, 5) 0,0150604 0,15476799 (4, 3) 0,0493002 0,540184021
(3, 4) 0,0154448 0,170212746 (4, 2) 0,0516081 0,591792107
(3, 3) 0,0157051 0,185917854 (5, 3) 0,0564699 0,648262024
(7, 1) 0,0161695 0,202087402 (6, 1) 0,0605555 0,708817482
(4, 6) 0,0171032 0,219190598 (6, 0) 0,0657034 0,774520874
(6, 3) 0,0193596 0,238550186 (5, 0) 0,0684748 0,842995644
(7, 0) 0,027894 0,266444206 (5, 2) 0,0760345 0,91903019
(4, 5) 0,0288258 0,295269966
(5, 1) 0,0809698 1
(5, 4) 0,0332651 0,32853508
Табл. 5 состоит из столбцов, содержание которых аналогично содержа-
нию столбцов табл. 1.
– 1
0
1
2
3
4
5
6
7
8
9
1 2 3 4 5 6 7 k 1
10
11
12
13
14
k 2
102 ISSN 0572-2691
Рис. 4
На рис. 4 представлена пузырьковая диаграмма, в которой первый параметр
(горизонтальная ось) — значение 1,k второй (вертикальная ось) — значение 2 ,k
третий (размер пузырька) — вероятность осуществления события *
1 1 1{ ( ) ,t t k
2( ) },t t t k которая представлена в процентах.
5.3. Иллюстрация использования равенства (18). В табл. 6 и на рис. 5 при-
ведено использование соотношения (18) для 1/ 2,p q малой выборки дли-
ны ,n 20,n и некоторых значений 1,k 2.k
Таблица 6
(k1, k2) P Pc
(k1, k2) P Pc
(2, 0) 0,0118675 0,075144768 (5, 4) 0,0383215 0,332155228
(7, 4) 0,016923 0,092067719 (3, 1) 0,0517502 0,383905411
(7, 5) 0,0171833 0,109251022 (5, 1) 0,0579596 0,441864967
(3, 2) 0,0206223 0,129873276 (6, 4) 0,0593233 0,501188278
(6, 5) 0,0233202 0,153193474 (6, 3) 0,066824 0,568012238
(6, 2) 0,0338459 0,187039375 (4, 2) 0,1008682 0,668880463
(4, 0) 0,0340939 0,221133232 (4, 1) 0,1047363 0,773616791
(3, 0) 0,0362511 0,2573843 (5, 3) 0,1050091 0,87862587
(4, 3) 0,0364494 0,293833733 (5, 2) 0,1213741 1
Табл. 6 составлена из столбцов, содержание которых аналогично содержанию
столбцов табл. 1.
На рис. 5 дана пузырьковая диаграмма, в которой первый параметр (горизон-
тальная ось) — значение 1,k второй (вертикальная ось) — значение 2 ,k третий (раз-
мер пузырька) — вероятность осуществления события *
1 1 1{ ( ) ,t t k
*
2( ) },t t t k
которая представлена в процентах.
– 1
0
1
2
3
4
5
6
7
8
9
1 2 3 4 5 6 7 k 1
10
11
12
13
k 2
– 2
8 9
Международный научно-технический журнал
«Проблемы управления и информатики», 2019, № 5 103
Рис. 5
5.4. Иллюстрация использования равенства (19). В табл. 7 приведено ис-
пользование соотношения (19) для 1/ 2,p q малой выборки длины ,n 20,n
и некоторых значений 1,k 2k и 3.k
Таблица 7
k1 k2 k3 P Pc k1 k2 k3 P Pc
7 0 4 0,010347 0,432714 5 3 2 0,018559 0,670737
6 1 2 0,010829 0,443543 6 1 4 0,018897 0,689634
5 2 1 0,011859 0,455402 4 3 1 0,01915 0,708784
4 5 2 0,012703 0,468105 4 3 2 0,019386 0,72817
6 2 3 0,01318 0,481285 5 0 1 0,02039 0,74856
5 4 3 0,013247 0,494532
4 1 1 0,02113 0,76969
4 4 1 0,013325 0,507856 5 3 3 0,021782 0,791471
4 1 2 0,013573 0,521429 5 1 3 0,022125 0,813597
5 0 3 0,01358 0,535009 4 2 1 0,022333 0,83593
6 0 4 0,01442 0,549429 6 1 3 0,022564 0,858494
6 2 4 0,014892 0,564321 6 0 3 0,025177 0,883671
4 0 1 0,016785 0,581105 5 2 3 0,025787 0,909458
4 4 2 0,017544 0,598649 5 0 2 0,028 0,937458
4 2 2 0,017824 0,616473 5 2 2 0,029125 0,966583
5 1 1 0,017853 0,634326
5 1 2 0,033417 1
6 0 2 0,017853 0,652179
В табл. 7 в первом, втором и третьем столбцах приведены все возможные ва-
рианты значений 1,k 2k и 3,k для которых вероятность *
1 1 1 2P{ ( ) , ( ) ,t t k t t t k
0
1
2
3
4
5
6
7
8
1 2 3 4 5 6 7 k 1
k 2
8
– 1
104 ISSN 0572-2691
*
3( ) 0,01,}t t t k а содержание четвертого и пятого столбцов аналогично
содержанию соответственно второго и третьего столбцов табл. 1 (см. 3.1).
Заключение
В работе установлены совместные распределения числа 2-цепочек и числа
3-цепочек фиксированного вида случайной битовой последовательности. Даны
примеры использования этих распределений. Возможным применением полу-
ченных формул может быть проверка гипотезы случайности расположения
нулей и единиц в (0, 1)-последовательности конечной длины.
В.І. Масол, С.В. Поперешняк
СТАТИСТИЧНИЙ АНАЛІЗ ЛОКАЛЬНИХ
ДІЛЯНОК БІТОВИХ ПОСЛІДОВНОСТЕЙ
Розглянуто сумісні розподіли числа 2-ланцюжків і числа 3-ланцюжків фіксова-
ного вигляду випадкової (0, 1)-послідовності, які дозволяють здійснювати ста-
тистичний аналіз локальних ділянок цієї послідовності. Сформульовано і дове-
дено дві теореми. У теоремах 1, 2 для числа s-ланцюжків вигляду *,t t *1 ,t t *0 ,t t
*
1 1 ,t t *
1 11t t ( *
1 1,t t 1 ,t t 0 ,t t ,t t t , * ),t t t що зʼявилися у випадковій бітовій послідо-
вності довжини n, 0,n встановлено явні вирази сумісних розподілів таких подій:
* * *
1 2{ ( ) , ( 1 ) ( ) },0t t k t t t t k * *
1 1 1 1 1 2{ ( ) , },( )t t k t t t k *
1{ ( ) ,t t k
* *
2 3( 1 ) , ( 0 ) },t t k t t k *
1 1 1 2}({ ( ) , ) ,( 1 ) ( 0t t k t t t t k *
1 1 1{ ( ) ,t t k
2( ) },t t t k * *
1 1 1 2{ ( ) , ( },)t t k t t t k * *
1 1 1 2 3{ ( ) , ( ) (, })) ,t t k t t t k t t t k
де
1 2( ... )st t t — число s-ланцюжків вигляду
1 2 ... st t t у вихідній n-ви-
мірній (0, 1)-послідовності;
1k ,
2 ,k
3k — відповідні цілі невідʼємні числа.
Одне з основних припущень кожної теореми полягає у тому, що нулі і оди-
ниці бітової послідовності — це незалежні однаково розподілені випадкові
величини. Доведення формул для розподілів зазначених подій побудовано
на підрахунку числа відповідних сприятливих подій за умови, що (0, 1)-пос-
лідовність містить фіксовану кількість нулів і одиниць. В якості прикладів
використання явних виразів сумісних розподілів наведено таблиці, в яких
розміщено значення ймовірностей перерахованих вище подій для випадко-
вої (0,1)-послідовності довжини ,n 20,n і деяких значень параметрів
1k ,
2k і
3k за припущенням, що нулі і одиниці зʼявляються рівноймовірно. Для
наочності, частина таблиць проілюстрована бульбашковими діаграмами.
Знайдені формули можуть становити інтерес для задач тестування локаль-
них ділянок, які формуються на виході генераторів псевдовипадкових чи-
сел, для деяких задач захисту інформації від несанкціонованого доступу, а
також в інших сферах, де виникає необхідність в аналізі бітових послідов-
ностей.
Ключові слова: s-ланцюжки, бітова послідовність, випадковість, локальні ді-
лянки, сумісний розподіл.
V.I. Masol, S.V. Popereshnyak
STATISTICAL ANALYSIS
OF LOCAL PLOTS OF BITS SEQUENCES
The joint distributions of the number of 2-chains and the number of 3-chains of a
fixed form of a random (0, 1)-sequence, which allow a statistical analysis of local
Международный научно-технический журнал
«Проблемы управления и информатики», 2019, № 5 105
sections of this sequence, were examined. Two theorems are formulated and
proved. Consider s-chains of the form *,t t *1 ,t t *0 ,t t *
1 1 ,t t *
1 11t t ( *
1 1,t t 1 ,t t 0 ,t t
,t t t , * ),t t t which appeared in random bit sequence of fixed length in Theo-
rems 1, 2. For these s-chains, explicit expressions for the joint distributions of
such events were established: * * *
1 2{ ( ) , ( 1 ) ( ) },0t t k t t t t k *
1 1 1{ ( ) ,t t k
*
1 1 2( },)t t t k * * *
1 2 3{ ( ) , ( 1 ) , ( 0 ) },t t k t t k t t k *
1 1 1({ ( ) , ( 1 )t t k t t
2( 0 ) },t t k *
1 1 1 2{ ( ) , ) }( ,t t k t t t k * *
1 1 1 2{ ( ) , ( },)t t k t t t k *
1 1{ ( )t t
*
1 2 3,, ( ) ( ) }),k t t t k t t t k where
1 2( ... )st t t is the number of s-chains of
the form
1 2 ... st t t in the initial n-dimensional (0, 1)-sequence;
1k ,
2k and
3k
are suitable non-negative integers. One of the main assumptions of each theorem
is that zeros and ones in a bit sequence are independent identically distributed
random variables. The proofs of the formulas for the distributions of these
events are based on counting the number of corresponding conductive events,
provided that the (0, 1)-sequence contains a fixed number of zeros and ones. As
examples of the use of explicit expressions of joint distributions, tables that con-
tain the probabilities of the above events for a random (0, 1)-sequence of length
,n 20,n and some values of the parameters
1k ,
2k and
3k under the assump-
tion that zeros and units appear equally likely are given. For illustrative purpos-
es, some of the tables are illustrated by bubble chart. The established formulas
may be of interest for tasks like testing local sections formed at the output of
pseudorandom number generators. Also, they may be suitable for some tasks of
protecting information from unauthorized access, as well as in other areas where
it becomes necessary to analyze bit sequences.
Keywords: s-chains, bit sequence, randomness, local segments, joint distribu-
tion.
1. Гайдышев И.П. Программное обеспечение анализа данных AtteStat. Руководство пользова-
теля. Версия 13. 2012. 505 с.
2. A statistical test suite for random and pseudorandom number generators for cryptographic
applications. Andrew Rukhin, Juan Soto, James Nechvatal, Miles Smid, Elaine Barker, Stef-
an Leigh, Mark Levenson, Mark Vangel, David Banks, Alan Heckert, James Dray, San Vo.
National Institute of Standards and Technology. Special Publication 800-22 revision 1a.
2010. 131 p.
3. Масол В.И. О распределении некоторых статистик (0, 1)-вектора. Исслед. операций и АСУ.
Вып. 29. 1987. С. 23–27.
4. Yueqi Hu, Tom Polk, Jing Yang, Ye Zhao, Shixia Liu. Spot-tracking lens: A zoomable user
interface for animated bubble charts. IEEE Pacific Visualization Symposium (PacificVis).
2016. P. 16–23.
Получено 22.02.2019
|