Derivation of formulas for Golomb postulates. A method for creating pseudo-random sequence of frequencies Mises. Basics "Combinatorics of  long sequences."

Filatov O.

Вывод формул для постулатов Голомба. Способ создания псевдослучайной последовательности из частот Мизеса. Основы «Комбинаторики длинных последовательностей».

Филатов О.В.

Филатов Олег Владимирович / Filatov Oleg - инженер-программист НТЦ Модуль, г. Москва.

 

Аннотация:  Приведён вывод формул для постулатов Голомба из «Комбинаторики длинных последовательностей» ( КДП) - теории описывающей природу вероятности с позиций частот Мизеса и комбинаторики. Перечислены основополагающие для КДП понятия, определено случайное событие в КДП. Приведён способ алгоритмического создания псевдослучайной последовательности на КДП платформе при помощи частот Мизеса.

Abstract: The above derivation of formulas for the postulates of Golomb" Combinatorics long sequences' (KDP) - which describes the nature of probability theory with the frequency position of Mises and combinatorics. Listed fundamental concepts for the KDP, defined random event in KDP. The above method of algorithmic create pseudo-random sequence on the KDP platform using Mises frequencies.

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

Keywords: the postulates of Golomb, the frequency of Mises, series Golomb, a pseudo-random sequence, combinatorics long sequences, KDP, a train, a composite event, el, binary event, random binary sequence, Penny game.

Сокращения:     пос-ть – последовательность;        эл – элементарное бинарное событие («0», «1»).

Введение.

Случайная бинарная последовательность может быть разделена на образующие её «кирпичики» - составные события и цуги. Комбинаторика длинных последовательностей ( КДП) изучает пропорции составных событий и цуг, которые образуют своеобразную «структуру» длинных пос-тей (с числом элементарных событий от 1,5 тысяч). Так, например, в случайной пос-ти доля всех нечётных «кирпичиков»  (составных событий)  равна  66% , а доля всех чётных событий в этой же пос-ти – 33% [3].

Всё большую известность приобретает парадокс (игра) Пенни. Парадокс этой игры заключается в том, что при бросании монетки игрок обладающий знанием как взаимодействуют друг с другом цуги, всегда будет выигрывать при подбрасываниях монеты. Игра Пенни является общепризнанным примером того, что от знаний правил образования составных событий и цуг, из результатов выпадений монеты, можно сконструировать такие правила игры в орлянку, которые обеспечивают гарантированный выигрыш обладающему этими знаниями. Правила и комбинации, приводящие к победам и поражениям в игре Пенни, были раскрыты довольно быстро, но формулы для количественного расчёта чисел побед и поражений в зависимости от числа подбрасываний монетки открыла КДП теория [7].

В КДП было показано, что правила поиска цуг влияют на число их нахождений в случайной бинарной пос-ти. За одно и то же количество попыток угадываний, для выпадений монеты, но по разным правилам (не только по правилам игры Пенни), можно угадать разное количество событий объединённых в цуги [8].

В текущей статье показано, что базовые основы КДП не только хорошо описывают не исследованную традиционной теорией вероятности структуру  длинных случайных последовательностей, но являются фундаментальными. Так как из КДП удалось получить формулы описывающие постулаты Голомба, которые были своеобразными, ни откуда  не выводимыми аксиомами для прикладной комбинаторики.

 

Основная часть

Постулаты Голомба содержат три постулата, рассмотрим два первых.

Первый постулат Голомба:  «Количество "1" в каждом периоде должно отличаться от количества "0" не более, чем на единицу».

Второй постулат: «В каждом периоде половина серий (из одинаковых символов) должна иметь длину один («1»; «0»), одна четверть должна иметь длину два («11»; «00»), одна восьмая должна иметь длину три («111»; «000») и т.д. Более того, для каждой из этих длин должно быть одинаковое количество серий из "1" и "0"».

Требование одинакового количества серий из "1" и "0"  (выделено жирным в постулатах) приводит к количественной симметрии серий из единиц «1» и нулей «0». Эту симметрию можно отобразить на листе бумаги, слева и справа, от нарисованной вертикальной черты, написав число единичных и нулевых серий длины n. Эти числа будут одинаковыми для серий из нулей и серий из единиц. Пример отображающий такую симметрию приведён в таблице 1. В таблице 1 сгруппированы вместе  серии, которые были разбросаны по псевдослучайной последовательности. Таблица 1 представлена в виде выделенного столбца и в таблице 2.

Таблица 1. «Симметрия серий из «0» и «1» в периоде Т=52».

16 серий длины 1

8 «0»

0101010101010101

 8 «1»

 8 серий длины 2

 4 «00»

0011001100110011

 4 «11»

 4 серии длины 3

 2 «000»

000111000111

 2 «111»

 2 серии длины 4

 1 «0000»

00001111

 1 «1111»

Очевидно, что следствием симметрии серий является то, что должны существовать всегда две серии максимальной и равной друг другу длины  (одна из нулей «00…0» другая из единиц «11…1»). Через эту длину  рассчитывается период  псевдослучайной пос-ти Голомба, ф.1:

ф.1

Произведём вывод ф.1 из формулы ф.2. Ф.2 показывает распределение составных событий  [1,2, 3, 4] в случайной пос-ти из N бросков монеты.

Ф. 2

 

Где:  – мат. ожидание числа бросков монеты, для практических расчётов его выбирают больше 1.5103, верхний предел  неограничен;   – длина составного события  (длина серии Голомба), наименьшее значение – единица, максимальное – неограниченно.

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

Формула 2 (из которой будет осуществлён вывод ф.1) принадлежит «Комбинаторике длинных последовательностей» (КДП), это её первое применение для коротких псевдослучайных пос-тей (меньше 103).

Базовые понятия КДП, сжато, приведены здесь:

1)    Рассматривается конечное число бросков монеты .

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

3)    Число составных событий (серий)  стремится к бесконечности , так как , но вклад большинства составных событий (серий) бесконечно мал: .

4)    Сумма всех  составных событий (серий) равна N / 2, действительно: .

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

6)     Сумма длин , где  равна N, действительно:
.

7)    Связь ф.2 с мизесовскими частотами  достигается через избавление от числа бросков : . Расчёт мат ожидания выпадения составных событий (серий) через мизесовскую частоту:  .

8)    Вероятностью  выпадения составного события длины  является не мизесовкая частота , а произведение частота  на  - длину составного события (серии):  . Действительно:  .

 

Вывод формулы расчёта периода  псевдослучайной пос-ти Голомба.

В таблице 1 был показан пример, как уменьшаются в два раза численности каждой последующей серии, до тех пор, пока количество серий не уменьшается до двух. По постулату № 2 эти две серии имеют одинаковую длину , наибольшую среди серий периода Т.

Найдём из КДП, по ф.2,  мат ожидание числа   (бросков монеты) для выпадений двух серий  длины , прировняв , к двум, ф.2.1:

 

Ф. 2.1

 

Из ф.2.1 выразим  - мат ожидание числа бросков монеты, ф.3:

 

Ф. 3

 

По КДП, в число бросков  входят броски и всех «расчётных» серий с длиной . Найдём число «расчётных» серий  суммировав значения  (ф.2) от  до ,  ф.4:

ф. 4

Каждая серия длины  будет содержать  бросков монеты. Большинство из этих значений имеют не целую величину, или их величина меньше единицы. В сумме они дадут число бросков монеты , которое является виртуальным «расчётным». При сложении периода Т и  получим   из ф.3. Число бросков монеты  серий с длиной , ф.5:

ф. 5

 

Найдём Т - величину периода серии Голомба.  Для этого из общего числа бросков монеты  вычтем  - число бросков монеты приходящиеся на серии длиннее , ф5.1: 

ф. 5.1

Ставя в ф.5.1 вместо  значение из ф.3, а вместо  значение из ф.5, получаем искомую ф.1:  .

Отметим, что ф. 1 и ф.5 следуют из суммы первых  членов ф.2:  .

 

В таблице 2, для справки, приводятся начальные раскладки серий для соответствующих периодов Голомба (начиная с самой короткой пос-ти Голомба, Т=8), а также даны формулы, по которым рассчитываются параметры псевдослучайных пос-тей построенных по постулатам Голомба.

 

Таблица 2. «Распределение серий  и периодов  по Голомбу».

 

n

- наибольшая длина парной серии в периоде

1

4

8

16

32

64

128

256

512

 - число серий из n событий

 

 - число единичных серий, n=1

 

 -  число всех серий

 

 - период пос-ти

2

2

4

8

16

32

64

128

256

3

 

2

4

8

16

32

64

128

4

 

2

4

8

16

32

64

5

 

 

2

4

8

16

32

6

 

2

4

8

16

7

 

2

4

8

8

 

2

4

9

 

2

 

2

3

4

5

6

7

8

9

 

8

22

52

114

240

494

1004

2026

    

 

6

14

30

62

126

254

510

1022

               

Выделенный в таблице  столбец является приведённой выше таблицей 1.

Поясним вывод формул из таблицы 2. Замечаем, что в КДП, ф.2, отношение численностей двух серий:  и  , различающихся друг с другом по длине на единицу (), равно двум:  .  Так как в ф. 2.1  было принято:, а число событий любой серии   по ф.2 в два раза больше: , то численность событий в коротких сериях рассчитывается умножением на два: .  Поэтому, число событий единичной серии («1», «0») рассчитывается возведением двойки в степень  (число событий для самой длинной пос-ти, следует из постулата №2, место выделено жирным), ф.5.2: 

ф. 5.2

Где  – длина максимальных двух серий в пос-ти Голомба.

Число событий серий длины два  («11», «00») будет: , и т.д. Поэтому число серий длины  рассчитывается по ф.5.3:

ф. 5.3

В «Комбинаторике длинных последовательностей»   содержит   составных событий (серий) разных длин, включая «неочищенные», виртуальные серии. Пример «очистки» - разделение виртуальных и реальных численностей событий дан в ф.5.1. Разделив  - число «неочищенных»  событий единичной длины на  (все «неочищенные» события), получим выполнение постулата №2:   .

Для любой модели случайной пос-ти, из ф.2 можно вывести  формульные описания. Лишь бы эта модель была достаточно не противоречива и в довольной мере правильно отражала бы действительность. Примером этому служит выше проведённое получение формульных описаний постулатов Голомба из ф.2. Для справки напишем отношения:

;         .

Очевидно, что постулаты Голомба и игра Пенни являются разновидностью «Поисковых условий» [1,2,7,8], и в этом равны между собой.

 

Цуговые частоты Мизеса.

        

Первичный материал о данном способе генерации напечатан в [2]. Бинарная случайная пос-сть складывается из цуг  – цепочек одинаковых составных событий [1,2,3,6]. Свойства цуговых цепочек, ф.6.3, применимы для генерации псевдослучайных пос-тей.

Напомним базовые понятия для цуг.

Последовательные серии составных событий  называют цугами. Обозначение цуги: nCw.  Число составных событий  в цуге обозначается буквой  w,  где  w = 1, 2, 3, … .

Рассмотрим цепочку составных событий «01010101 00110011 000111».  В ней группы событий одинаковой длины образуют цуги nCw, а точнее три цуги: цугу n=1C w=8 = «01010101»,   цугу n=2C w=4 =«00110011»,  цугу n=3C w=2 = «000111».  Одинарной цугой, w=1, называется составное событие  в окружении составных событий других длин,  пример: цуга n=1C w=1 =«00100», цуга n=4Cw=1 =«1011110001».

 

Случайные пос-ти, по Мизесу, обладают устойчивостью частот. Цуги , образующие любую случайную пос-ть, распределены по частотам Мизеса . Частоты Мизеса не зависят от длины пос-ти ф.6.1:

Ф.6.1

         Где, n – число элементарных событий в каждом составном событии  цуги;  w – число колен (составных событий) в цуге.   

         Число цуг  nCw линейно зависит от числа событий N пос-ти, ф.6.2:

Ф.6.2

Где:  – Мизесовская частота [5] для цуги ;   - число бросков монеты.

Раскрыв в ф.6.2 частоту по ф.6.1 получим ф.6.3:

Ф. 6.3

Из ф.6.2 следует равномерность появлений очередных цуговых событий nCw  при росте N, так как частота Мизеса  .

Например, число событий цуги 1C1 увеличивается на единицу с шагом N =16. Действительно, по ф.6.3:  ; 1C 1 (32) = 2;  1C 1 ( 48) = 3; 

 

         Для каждой цуги  nC w существует такой шаг  N, увеличение на который приводит к увеличению событий цуги  nC w на единицу, ф.7.1, ф.7.2:

Ф. 7.1

         Введём понятие «Цугового шага  », который зависит от n и w:  .Умножая частоту Мизеса на  получим один, ф.7.2:

Ф. 7.2

Цуговый шаг  и частота Мизеса обратнопропорциональны, ф.7.3:

Ф. 7.3

Разделив  - число элементарных событий в пос-ти на , получим мат ожидание цуг  пос-ти, ф.7.4:

Ф. 7.4

Из формул: 6.2 и 7.4, видно, что псевдослучайная последовательность с равномерным распределением цуг создаётся через контроль роста , путём расчёта величин . При достижение или превышение  порога очередного целого числа, производится внесение нового фрагмента в псевдослучайную пос-ть, путём дописывания цуги  в виде нулей и единиц в дополнение к её уже записанным нулям и единицам.

 

Способ построения псевдослучайной пос-ти из цуговых частот Мизеса.

 Способ основан на том, что с ростом числа бросков монеты N, в ф.6.3, растут значения цуг  nCw. По мере достижений новых пороговых величин, выраженных целыми числами (1, 2, 3, …), цуги дописываются в продолжение к уже имеющейся записи.  А именно, в файл записывается цуга nCw в виде нулей и единиц, когда рассчитанная  по ф.6.3 величина превысит или сравняется с очередным целым числом, начиная с единицы: 1, 2, 3, … .

Опишем компьютерную реализацию этого способа. Для каждой цуги  nCw создаётся своя переменная (регистр памяти) с нулевым начальным значением. После каждого увеличения N на единицу, с новым значением N рассчитываются заново все значения цуг nCw. Новые значения nCw сравнивают со старым значением, хранящимся в переменной. Если новое значение достигло или преодолело очередной целочисленный барьер, то эту цугу дописывают в продолжение имеющийся записи. Новое значение nCw в любом случае (не / достижения целочисленного порога) записывают вместо старой величины переменной. Дописывание цуги в продолжение, производится с учётом последнего записанной величины («0»,  «1»). Запись цуги производится с инверсного значения, что бы дописываемая цуга не слиплась с предыдущей цуговой записью, и не произошло бы, в результате, искажение составных событий. То есть, если последним записанным был «0», то цуга начинает писаться с «1».

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

 

В таблице 3 отражена генерация псевдослучайной пос-ти по ф.6.3 при  N  64.

По ф.6.3 цуга 2C 1 первая из всех цуг достигает значение единицы:  , поэтому принадлежащие ей элементарные события «00» первыми записываются в файл (строка 1).

Поскольку к цугам 2C 1 принадлежат две цепочки: «00» и «11», то выбор для записи цепочки «00» произволен.

 

При N=16 единичный барьер достигает цуга  1C 1:

  , поэтому единичная цуга дописывается в файл после «00». Значение этой цуги должно быть выбрано таким, что бы оно было противоположным значению последнего эла (он равен «0») у предыдущей записанной цуги. Поэтому, для записи 1C 1  выбираем «1» (строка 2 таблицы 3).

При N=21 единичный барьер преодолевает цуга   3C 1:

  ,  поэтому событие 3C 1  записывается вслед за «1». Что бы цуга 3C 1  не слилась с ранее записанной цугой 1C1  («1»), её элы должны быть инверсными по отношению к элам 1C 1 . Поэтому 3C 1  = «000» (строка № 3).

При N=29  цуга  2C 1 , строка 4, снова преодолела барьер равным двум:  .  Цуга в строке 1 и цуга в строке 4 составляют в сумме две цуги, как того требует ф.6.3 при N=29.  Для записи в файл 2C1 выбираем такую полярность её элов, что бы она не слилась в файле в одно с предшествующей цугой.

При N=32 сразу две цуги:  1C1 и  1C2  достигают величины следующего для них целого числа. Если эти цуги записать в файл сразу одну за другой, то они сольются и будут не только не различимы, но и образуют новую цугу:  1C3=1C1+1C2= «0» + «10» = «010». Поэтому цугу первой моды 1C1 надо отделить от цуги 1C2 (то же первой моды) какой то другой цугой. Для этого годится любая цуга не принадлежащая первой моде. И так, в файл записывается цуга 1C1 (строка 5) и продолжается перебор (наращивание) N.

При N=37 приходит время цуги 4C1, которая вписывается в файл поле цуги 1C1. А за цугой 4C1 уже дописывается цуга 1C2, строка 7.

Вид пос-ти из таблицы 3 записанный в итоговый файл: «00100011011110100011011000110010000010110101111».

 

Таблица 3. «Генерация псевдослучайной пос-ти по ф.6.3 при  N  64»

№№

N

n

w

Запись в файл (N)

1

15

2

1

(15) «00»

2

16

1

1

(16) «1»

3

21

3

1

(21) «000»

4

29

2

1

(29) «11»

5

32

1

1

(32) «0»

6

32

1

2

 

7

37

4

1

(37) «1111» + (32) «01»

8

42

3

1

(42) «000»

9

43

2

1

(43) «11»

10

48

1

1

(48) «0»

11

57

2

1

(57) «11»

12

57

2

2

 

13

63

3

1

(63) «000» + (57) «1100»

14

64

1

1

(64) «1»

15

64

1

2

 

16

64

1

3

 

17

69

5

1

(69) «00000» + (64) «10»

18

72

2

1

(72) «11» +(64) «010»

19

73

4

1

(73) «1111»

 

Цуговая вероятность

Умножая на число цуг  пос-ти начисло   эл в цуге и суммируя, получим  - число эл пос-ти, ф.8.1: 

Ф.8.1

Где:  – цуговая частота Мизеса.

Разделим левую и правую часть 8.1 на N, 8.2:

Ф.8.2

 Величину:  , из ф.8.2, называется цуговой вероятностью , ф.8.3:

Ф.8.3

 

Выводы

1)      Постулаты Голомба однозначно описываются формулами.

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

3)      Комбинаторика длинных последовательностей хорошо описывает структуру случайных бинарных пос-тей с число элементарных событий свыше 103.

4)      При описании коротких, числом менее  103 элементарных событий, случайных пос-тей в КДП возникает значительная мнимая составляющая из «половинок» выпадений монеты.

5)       При отбрасывании мнимой части, с дробными составными событиями, уравнения КДП переходят в формулы классической теории вероятностей, в частности в формулы описывающие постулаты Голомба.

6)      Из дискретных образующих случайных пос-тей, а именно цуг, легко образовывать длинные  псевдослучайные последовательности.

 

Библиографический список

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

2.       Филатов О. В., Филатов И.О. «Закономерность в выпадении монет – закон потоковой последовательности». Германия, Издательский Дом: LAPLAMBERT Academic Publishing, 2015, с. 268. 

3.       Филатов О. В., Филатов И.О., статья «О закономерностях структуры бинарной последовательности»,   «Журнал научных публикаций аспирантов и докторантов»,  №5, 2014.

4.       Филатов О. В., статья «Теорема «О амплитудно-частотной характеристике идеальной бинарной случайной последовательности», «Проблемы современной науки и образования», № 1 (31), 2015 г.

5.       Филатов О. В., статья «Описание распределения составных событий и их мизесовских частот через число возможных исходов. Механизм сжатия некоторых «не сжимаемых на один» последовательностей», «Проблемы современной науки и образования», № 9 (39), 2015 г.

6.       Филатов О. В., Филатов И.О., Статья «О закономерностях структуры бинарной последовательности (продолжение)»,   «Журнал научных публикаций аспирантов и докторантов»,  № 6, 2014.

7.       Филатов О. В., статья «Расчёт численностей поисковых шаблонов в парадоксе Пенни»,  «Проблемы современной науки и образования», № 11 (41), 2015 г.

8.       Филатов О. В., статья «Описание схем управления вероятностью выпадения независимых составных событий», «Проблемы современной науки и образования», № 2 (44), 2016 г.