О закономерностях структуры бинарной последовательности

Размещено на http://www.allbest.ru/

О закономерностях структуры бинарной последовательности

Филатов Олег Владимирович,

инженер-программист НТЦ «Модуль»,

Филатов Илья Олегович,

ученик 9 класса школы № 457 г. Москва



Скользящим окном переменной длины в бинарных последовательностях равновероятных событий ищутся структурообразующие логические цепочки. Даны формулы расчёта и распределения логических цепочек (первичных, вторичных) как функции длины последовательности. Рассчитаны характеристики цепочек (чётно-нечётная асимметрия, средняя длина, пропорции). Приведён алгоритм программного поиска при моделировании. Расчётные и опытные результаты совпадают (использовались выборки по элементарных событий).

Ключевые слова: бинарная последовательность, бинарное событие, элементарное событие, элементар, потоковая последовательность, потоковый поиск, составное событие, цуга, мода, метод скользящего окна.

Используемые сокращения: последовательность = п-ть.

В технике распознавания известен алгоритм «Скользящего окна». При включении аппаратуры производят калибровку по встроенным тестам, используются разные алгоритмы. В том числе и алгоритм «Скользящего окна», переменной длины. В тестовых данных применялся и поток случайных бинарных событий. При анализе калибровочных результатов от этого потока были сделаны интересные обобщения, о которых речь пойдёт в этой статье.

Статья описывает способ поиска упорядоченных подмножеств в генеральной п-ти случайных бинарных событий. Предлагаемый способ поиска, назван «Потоковым», отличается от классического поиска упорядоченных подмножеств, тем, что не делит п-ть (исследуемый образец) на фрагменты заданной длины. Потоковый способ позволяет найти больше упорядоченных подмножеств, чем классический, в одной и той же рассматриваемой п-ти (в заданной области). Говоря технологическим языком - потоковый поиск эффективнее классического. В процессе освоения потокового способа поиска были наработаны новые термины и формульные зависимости. Их число росло по мере развития практических работ. Но формат статьи не позволяет изложить всё наработанное.

В начале статьи вводятся используемые термины.

Следует обратить внимание на представленный алгоритм поиска (вариант класса алгоритмов «Скользящее окно»). Так как он является описанием «Потокового» способа поиска. И по результатам его работы получена эмпирическая формула 1, являющаяся фундаментом излагаемого материала. Следует отметить, что в ограниченной форме все описанные результаты можно получить без применения компьютера. Набрав выборку вытаскиванием из мешочка одного из двух шаров (белого или чёрного).

В теории вероятностей [1] принято обозначать элементарное событие буквой , а пространство элементарных событий ?. Выделим из ? множество ?1, такое, что . Причём . Для упрощения раскрытия закономерностей структуры бинарной п-тивведём ниже новые понятия [2].

Элементар (эл) и его свойства

Обозначим элементар буквой «е». Назначение элементаров (элов) - хранить величины из . Подчеркнём, что элементар не является случайным событием. Он является футляром для хранения случайного события. И к вопросам генерации случайных событий он отношения не имеет, он всего лишь хранитель элементарных событий , которые создаются отвечающим всем требованиям по генерации , генератором случайных величин.

Создание элементара (эла). Для создания нового эла проводится операция присвоения элементарного события из ?1 в символ эла: .

Обладание значением. Элементар может быть равен либо нулю, либо единице. Ни каких других значений эл принимать не может (и не может быть пустым).

Изменение значения (отличие от ). Величину эла можно менять, путём присвоения ему величин элементарных событий из ?1:

Сравнение элов. Элы и могут быть равны, либо не равны: .

Сравнение эла с числом. Эл всегда равен либо нулю, либо единице. Поэтому можно сравнивать значение эла непосредственно с числами 0 и 1: .

Потоковая последовательность F и её свойства:

По аналогии с ?, введём понятие «Потоковой п-ти», которую будем обозначать большой буквой F (от Flow).

Состав. F состоит из упорядоченного последовательного множества элов: .

Рост числа элов в F. Рост происходит по мере появления элементарных событий множества и присвоения их элам .

Длина (N). Число эл составляющих F может быть любым, но больше нуля . Удобно обозначать F и N вместе: F(N).

Составные события

Составными событиями в потоковой п-ти F(N) называются неразрывные области равных эл. Буква n - обозначает число эл образующих составное событие, она ставится сверху перед значком составного события S.

Пример 1. Фрагмент п-ти в виде случайных событий: «11100010100». Этот же фрагмент в виде символов составных событий: . Поясняющая раскладка фрагмента из примера 1 приведена в таблице 1.



Таблица 1

k = № в F(11)		Фрагмент п-ти	Длина (n)	Мода
1		111	3
2		000	3
3		1	1
4		0	1
5		1	1
6		00	2

Мода

Составные события одинаковой длины n объединяются в множества, называемыми модами. Мода .

В «Таблице 1» первой моде принадлежат три составных события: ; второй моде принадлежит одно событие: ; третьей моде два: .

Поиск составных событий моды в F(N).

Описание компьютерного эксперимента. Была сгенерирована и записана на диск бинарная п-ть F(). В ней производился программный поиск составных событий раздельно по каждой из мод . Суммарное число найденных выдавалось в виде результата. Представленный алгоритм поиска отражает только суть работы программы, естественно он не является пошаговым языковым алгоритмом.

Алгоритм поиска (длиной n эл) в F()

1) Задаётся число эл n (длина), для и для двух шаблонов «Эталон». В первом n нулей, во втором n единиц. Создаётся пустой массив «Образец» длиной в n эл. Переход в пункт 2.

2) Если нельзя считать n новых эл из , то конец программы. В других случаях переход в пункт 3.

3) Считать n новых эл из в «Образец». Переход в пункт 4.

4) Если «Образец» совпал с «Эталоном», то учесть находку и переход в пункт №2. В других случаях переход в пункт 5.

5) Если нельзя считать новый эл из , то конец программы. В других случаях переход в пункт 6.

6) Из «Образца» удаляется первый эл, а в конец ставится новый эл из F). Переход в пункт №4.

Рис. 1

На рисунке 1 изображены количества экспериментально обнаруженных и теоретически рассчитанных составных событий. По оси Х отложены длины n мод. По оси Y отложены числа составных событий в модах. Столбцы со сплошной заливкой отображают количества найденных в компьютерном эксперименте событий («Эксперимент»). Столбцы с переменной заливкой отображают теоретически рассчитанные числа («Теория»). Расчёт допусков явно излишен.

Над столбцами размещены числа. Верхние числа соответствуют экспериментальным данным (столбцы сплошной заливки). Нижние числа получены по формуле 1 (столбцы переменной заливки). Характеристики п-ти, в которой производился поиск:

- число нулей: 9999751;

- число единиц: 10000249;

- число элов в п-ти: 20000000;

- сумма всех составных событий: 10003027;

Теорема распределения составных событий по модам. Распределение составных событий по модам подчиняется формуле 1:

(1)

где: N - число эл в F(N), n - длина составного события (номер моды).

Доказательство:

Так как число элов в составном событии будет: , то формула 2 будет формулой расчёта числа элов в моде :

(2)

Просуммировав все элы во всех модах, убедимся, что их будет N, то есть столько же, сколько и элов в F(N):

Рис. 2

На рисунке 2 показано теоретически рассчитанное по формуле 2 распределение элов по составным событиям мод п-ти F().По оси Х отложены номера мод - n. По оси Y отложено число эл.

Интересно отметить, что число эл в первой и второй модах одинаково.

Теорема о количестве составных событий в F(N). Количество всех составных событий в F(N) рассчитывается по формуле 3, и равно половине N.

(3)

Доказательство: просуммируем все составные события в каждой моде :



Лемма о средней длине составного события. Средняя длина составного события равна двум элам и рассчитывается по формуле 4.

(4)

Доказательство. Разделим число эл в F(N) на число составных событий в F(N):

Лемма. Математическое ожидание числа элов для выпадения одного составного события моды рассчитывается по формуле 5.

Вывод формулы 5. Для расчёта числа элов математического ожидания используем формулу 1. Приравняв к единице, а N к :

Отсюда находим математическое ожидание числа элов:

(5)

Асимметрия чётных - нечётных составных событий.

Из рисунка 1 можно заметить, что нечётных составных событий численно больше, чем чётных:

Обозначим число всех нечётных составных событий п-ти - , а число всех чётных составных событий .

Тогда просуммировав численность составных событий во всех нечётных модах, получим:

По формуле 6 рассчитывают число всех нечётных составных событий F(N):

(6)

Просуммировав численность составных событий во всех чётных модах, получим:

По формуле 7 рассчитывают число всех чётных составных событий в F(N):

(7)

Проверка баланса. Сумма должна быть равна . Действительно:

(8)

Из формул 6 и 7 следует, что нечётных составных событий в два раза больше чем чётных.

Из этого отношения следует формула 9, связывающая численность четных и не чётных составных событий:

(9)

Расчёт баланса элов для нечётной и чётной области.

Численность элов принадлежащих нечётным :

По формуле 10 рассчитывают число всех эл в нечётных составных событиях :

(10)

Численность элов принадлежащих чётным :

По формуле 11 рассчитывают число всех эл в чётных составных событиях :

(11)

Проверка баланса. Сумма должна быть равна . Действительно:

Из формул 10 и 11 следует, что отношение к больше единицы, и это отношение равно 1,25:

Отсюда: нечётная область составных событий содержит в 1,25 раз больше эл, чем содержит в себе эл чётная область.

Отношение между численностью эл в нечётных и чётных областях составных событий, п-ти F(N), описывается формулой 12:

(12)

Вывод формулы отношения элов между соседними модами.

Отношение числа эл в более длинной моде к числу эл в более короткой соседней моде, можно проследить по цепочке подчинённости (моды - составные события - элементары):

Число эл для каждой моды рассчитывается по формуле 2. Обозначив номера смежных мод как m и n, причём , получим:

Отношение чисел эл двух соседних мод m и n (причём ) описывается формулой 13:

(13)

Теоретическое распределение эл по модам п-ти F() дано на рисунке 2.

Образование цуг из составных событий

Обычным явлением в п-ти F(N) является многократное выпадение событий моды друг за другом. В примере 1 присутствуют цуги двух мод. Цуга третьей моды представлена двумя событиями: . Цуга первой моды представлена тремя событиями: .

Цугой называют множество прилегающих друг к другу составных событий одной моды (иными словами: склеенные друг с другом составные события одинаковой длины). Или, цуга это группировка составных событий друг с другом.

Символьное обозначение цуг.

Символьное обозначение цуг состоит из трёх элементов: большой буквы С и двух символов к ней (n,k). Верхний символ n обозначает длину в элах базового составного события. Нижний символ k обозначает число составных событий в цуге.

В таблице 2 представлена цепочка событий , которая свёрнута в цепочку составных событий и в цепочку цуг.

Таблица 2

1	Цепочка случайных величин :	1110001010011110100000011
2	Цепочка составных событий :
3	Цуговая цепочка:

В строке 1 таблицы 2 дана п-ть . В начале п-ти стоят два события «111+000», которые составляют цуговую цепочку из двух событий по основанию 3.

В той же п-ти есть фрагмент «101» = «1+0+1», состоящий из трёх составных событий единичной длины ( Эти события образуют цугу по основанию в 1 эл, и длиной в три составных события .

Цуги, как и составные события группируются по модам. Признаком принадлежности цуги к моде является число элов - n, образующих в цуге составные события .

Нулевая цуга .

Нулевой цугой называется множество всех цуг моды , где n=Const (номер моды и длина основания составного события): . То есть

(14)

Расчёт числа нулевых цуг для моды , п-ти F(N) производится по формуле:

(15)

где n - число элов, образующих составные события цуги; N - число эл п-ти F; Нижние символ 0 - обозначает нулевую цугу; N (или число): N - обозначает, что работа ведётся со всей п-тью; (число) - указывает количество эл в рассматриваемом участке.

Рис. 3

На рисунке 3 представлено распределение цуг (ось Y) по модам (ось Х). При сравнении распределений в рисунках 1 и 3 видно, что распределение цуг стремится в старших модах к значениям составных событий (уравниваются).

Отношение цуг моды к цугам моды определяется соотношением:

В F(N) сумма нулевых цуг во всех модах в три раза меньше, чем число элов N. То есть, в среднем одна цуга приходится на три эла, формула 16:

(16)

Таблица 3

Зависимость числа событий логической сущности (ЛС) от номера её уровня

Логический уровень ЛС в F(N)	№1 (Элы)	№2 (Составные события)	№3 (Цуги)
Число событий сущности	N / 1	N / 2	N / 3

Число событий логической сущности прямо пропорционально числу эл в F п-ти, и обратно пропорционально номеру логического уровня.

Приведём, без вывода, формулу 17, служащую для расчёта числа цуговых событий . Цуга образованна k составными событиями :

(17)

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

Полярные события. Число событий рассчитывается по формуле 1. Половину составных событий составляют объединения из единиц, которые обозначим, как . Половину составных событий составляют объединения из нулей, которые обозначим, как . А сами события будем называть полярными событиями (). Тогда формула 18 рассчитывает число полярных событий в моде :

(18)

Переход от числа составных событий к вероятности выпадения составного события в F(N) осуществляется по формуле 19:

(19)

Вероятность выпадения полярного составного события рассчитывается по формуле 20:

(20)

Рассмотрим, вид в элах для события из пяти нулей, то есть n=5: .И рассчитаем традиционным способом число событий находящихся в п-ти F(N=20000000). Для этого разделим F(N) на число нулей в , то есть на пять (n=5). 20000000 / 5 = 4000000. Так как вероятность выпадения «00000» будет 1 / 2^5, то число выпадений пяти нулей будет: 4000000 / 2^5 = 125000.

Действительно в 4000000 множествах будет 125000 множества из пяти нулей. Но в потоковой п-ти, по формуле 18, будет 156250 составных событий . То есть расчёты классическим способом и по формуле 18 не совпали.

Вспомним, что любое составное событие, в том числе и спереди и сзади обрамлено полярными элами. То есть, в обрамлении выглядит вот так: «1000001». Число элов увеличивается до семи (1+5+1), и вероятность выпадения семи событий подряд: 1 / 2^7 (а в знаменателе формулы 18 как раз и получается 2^7).

И, рассчитываем классическим способом число событий длиной семь в F(20000000): 20000000 / (7 * 2^7) = 22321.

Полученный результат не равен числу .

Что касается, цугового числа , то по внешнему виду формулы 17 ясно, что оно будет отличаться от числа, рассчитанного по классической формуле: N / ((n*k)*2^(n*k)).

К сожалению, формат статьи не позволяет описать применение найденных формульных зависимостей. Но авторы надеются, что будут иметь возможность напечатать в следующей статье продолжение.

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

В работе были достигнуты следующие результаты по описанию закономерностей структуры F(N) - бинарной п-ти равновероятных событий:

1) Введены новые понятия ( описывающие логическую структуру п-ти.

2) Предложено составные события и цуги группировать по модам .

3) Обнаружено, что число составных событий в моде зависит от номера моды и числа элов в потоковой п-ти (числа элементарных событий в бинарной п-ти), формула 1.

4) Найдено численное распределение элементарных событий по составным событиям п-ти, формула 2.

5) Найдено отношение элов двух соседних мод, формула 13.

6) Найдено число составных событий в п-ти, формула 3.

7) Найдена средняя длина составного события, формула 4.

8) Найдено математическое ожидание числа элов, для выпадения одного составного события моды , формула 5.

9) Обнаружена асимметрия чётных - нечётных составных событий, которая описывается формулами: 6, 7, 8, 9, 10, 11, 12.

10) Описано распределение цуг по модам в зависимости от числа элов потоковой п-ти, формула 17.

11) Описаны некоторые соотношения в цуговом пространстве, формулы: 15, 16, 18.

12) Показана не сводимость числа составных событий и цуг к результатам расчета по классической формуле вероятностей для симметричной монеты.

13) Обнаружена зависимость числа событий логической сущности от номера логического уровня, таблица 3.

14) Приведены формулы (19, 20) перехода от числа составных событий к вероятности выпадения составного события в F(N).

бинарный последовательность скользящий окно



Литература

1. Андронов А.М., Копытов Е.А., Гринглаз Л.Я. Теория вероятностей и математическая статистика. СПб.: Питер, 2004. С.461.

2. Филатов О. В., Филатов И.О, Макеева Л.Л. и др. «Потоковая теория: из сайта в книгу». М.: Век информации, 2014. С.200.

Размещено на Allbest.ru

...