Программный генератор статистически безупречных случайных чисел

Проблема создания таких программ широко обсуждалась в математической литературе в 1965-1975 годах, тогда же отмечалась сложность этой задачи.

Современная математика имеет значительные достижения в этом вопросе.

Они доступны узким специалистам, но сложны для понимания, и удалились из широкого обсуждения.

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

Мне удалось создать программу, генерирующую последовательность символов '0' и '1', имеющую безупречно хорошие статистические свойства.

Конструкция программы проста и легко доступна для понимания.

Случайная последовательность нулей и единиц должна обладать следующими свойствами:

• количество нулей и единиц во всех фрагментах этой последовательности примерно одинаково;
• количество вхождений фрагментов 00, 01, 10 и 11 всегда примерно одинаково;
• то же касается всевозможных фрагментов длины 3, 4, 5 и так далее.
  Ясно, что программа может подсчитывать количество вхождений таких фрагментов в уже сформированную последовательность и генерировать очередной символ так, чтобы поддерживать перечисленные равенства.

Если анализировать эти равенства в порядке возрастания длины фрагмента, то программа быстро зацикливается.

Однако, если их анализировать в обратном порядке, то всё получается замечательно хорошо.

Что же в итоге получилось?

Задаётся некоторая начальная последовательность символов '0' и '1' (начальный отрезок), которую программа будет достраивать до заранее заданной предельной длины, после чего остановится.

Такая организация программы целесообразна в связи с тем, что по мере роста длины сформированной последовательности скорость формирования очередного символа уменьшается.
Для формирования очередного символа программа организует цикл, по различным длинам маски (идентификатор lenmask).

Маска в этом цикле задаётся как фрагмент сформированной последовательности, состоящий из lenmask её последних символов.

Такая маска циклически передвигается вдоль сформированной последовательности.
В ходе этого вложенного цикла передвижений подсчитываются суммы s0 и s1, это количество появлений нуля или соответственно единицы в сформированной последовательности непосредственно после обнаруженного совпадения маски с ней.

Если по окончании подсчёта при очередной заданной длине маски значения s0 и s1 оказываются различными, то при s0>s1 очередной символ формируется как 1, иначе как 0 и цикл по длинам масок прерывается.

Если же при всех длинах маски значения сумм s0 и s1 окажутся одинаковыми, то очередной символ сформируется по значению резервной переменной, принимающей одно из двух значений 0 или 1 и меняющей значение после каждого использования.

Эта ситуация, конечно, маловероятна.

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

Детально комментированный текст этой программы на языке JAVA представлен в приложении.
Программа состоит из двух частей.

Это собственно формирование псевдослучайной последовательности и статистический контроль результата.

Для контроля формируется некоторое количество масок различной длины.

Эти маски наполнены нулями и единицами.

Подсчитывается количество вхождений этих масок в сформированную последовательность.
Как и следовало ожидать, результаты контроля демонстрируют, что количество таких вхождений зависит от длины маски и почти не зависит от её наполнения.

Удивительно, что такая вполне элементарная программа позволяет получить результат, казавшийся недостижимым простыми средствами.

Приложение

Текст программы на языке JAVA

//gerase = generator random sequence
//генератор статистически безупречной 
//случайной последовательности нулей и единиц
package ikojar;
public class gerase {
public static void main(String[] args) {
//управляющие параметры программы
//число, кодирующее начальный отрезок формируемой последовательности
//двоичное представление числа beg станет 
//началом формируемой последовательности
int beg=5,
//длина формируемой последовательности
lenrez=2048,
//maxpower это максимальная длина контрольной маски 
//в процессе статистического контроля сформированной последовательности
//контрольная маска скользящим образом 
//накладывается на сформированную последовательность
//подсчитывается количество вхождений 
//различных вариантов наполнения маски
//для разных вариантов наполнения маски 
//количество её вхождений в сформированную последовательность 
//должно быть приблизительно одинаковым
maxpower=10;

//декларация рабочих переменных программы
//rs это random symbol, может быть использован, 
//если очередной символ не был определён алгоритмом формирования
//алгоритм не сможет сформировать очередной символ, если 
//в результате расчёта окажется, что и нуль и единица одинаково допустимы
byte rs=0;
//массив result будет содержать сформированную последовательность 
//нулей и единиц
byte[] result=new byte[lenrez];
//массив mask будет вместилищем контрольной маски, используемой 
//как при формировании последовательности, 
//так и при её статистическом контроле
//длина маски будет изменяться внутри программы, 
//здесь просто резервируется максимально необходимое место для неё
byte[] mask=new byte[lenrez];

//собственно формирование псевдослучайной последовательности
//распаковка управляющего числа beg
//двоичное представление управляющего числа beg будет помещено 
//в начало формируемой псевдослучайной последовательности result
int p=beg,bp=0;
for(;;)
{//cir raspak
result[bp]=(byte)(p%2);
bp++;
if(p<2)break;
p/=2;
}//cir raspak
//печать начального отрезка
String so="начальный фрагмент ";
for(int i=0;i<bp;i++)so+=String.valueOf(result[i]);
System.out.println(so);
//подготовка печати результата
System.out.println("сформирована последовательность");

//цикл формирования выходной последовательности
for(int pos=bp;pos<lenrez;pos++)
{//circlepos
//признак hs(hard symbol) это 
//признак того, что очередной символ формируемой выходной 
//последовательности определился в результате расчёта
//если расчёт не сможет определить очередной символ, 
//то он будет задан из переменной rs
int hs=0;
//цикл по убывающему размеру маски
//lenmask это длина маски
for(int lenmask=pos-2;lenmask>=0;lenmask--)
{//lenmask
//заполнение маски последними символами 
//ранее сформированной последовательности
for(int i=0;i<lenmask;i++)mask[i]=result[pos+i-lenmask];
//s0 и s1 станут результатами подсчёта 
//количества вхождений нулей и единиц соответственно
//непосредственно после очередного вхождения образа маски 
//в уже сформированную последовательность
//при скользящем наложении маски на эту последовательность
int s0=0,s1=0;
//цикл скользящего продвижения маски вдоль 
//сформированной последовательности псевдослучайных символов
for(int i=lenmask;i<pos;i++)
{//calcS01
//eqm это признак совпадения фрагмента 
//сформированной последовательности с наложенной маской
int eqm=1;
//вычисление eqm
for(int i1=0;i1<lenmask;i1++)if(mask[i1]!=result[i+i1-lenmask]){eqm=0;break;}
//собственно акт подсчёта количества нулей или единиц, следующих 
//непосредственно после вхождения образа маски
if(eqm==1)if(result[i]==0)s0++;else s1++;
}//calcS01

//формирование очередного символа выходной последовательности 
//в зависимости от соотношения между s0 и s1
//признак hs станет равным 1, если 
//таким образом будет сформирован очередной символ
if(s0<s1){result[pos]=0;hs=1;break;}
if(s1<s0){result[pos]=1;hs=1;break;}
}//lenmask
if(hs==1)continue;
//если расчёт не определил очередной символ, 
//то он формируется из переменной rs
result[pos]=rs;rs=(byte)(1-rs);
}//circlepos

//выходная последовательность готова
//осталось выдать её на печать
so="";
for(int i=0,c=0;i<lenrez;i++)
{//out rez
so+=String.valueOf(result[i]);
c++;
if(c==64){c=0;System.out.println(so);so="";}
}//out rez
System.out.println(so);

//а теперь статистический анализ сформированной последовательности
System.out.println
("статистический анализ сформированной последовательности");

//цикл по различным размерам контрольных масок
//pw это длина контрольной маски, 
//накладываемой на сформированную последовательность
for(int pw=1;pw<maxpower;pw++)
{//pw
//контрольные маски будут наполняться 
//всевозможными комбинациями нулей и единиц
//эти комбинации можно интерпретировать как двоичные представления 
//того или иного неотрицательного целого числа
//будут перебираться все 
//такие представляющие числа в пределах от 0 до pm-1
//верхняя граница pm для такого перебора сейчас будет определена
int pm=1;for(int i=0;i<pw;i++)pm*=2;
//печатаем заголовок серии чисел, равных количеству вхождений 
//очередной маски в сформированную последовательность
System.out.println("для маски длиной "+String.valueOf(pw));
int mincount=lenrez,maxcount=0;
//цикл последовательного перебора целых чисел от 0 до pm-1, 
//двоичное представление которых станет содержимым очередной маски
for(int im=0;im<pm;im++)
{//im
//заполнение маски двоичным представлением числа im
p=im;
for(int i=pw-1;i>=0;i--)
{mask[i]=(byte)(p%2);p/=2;}

//цикл скользящего наложения контрольной маски 
//на сформированную последовательность 
//переменная s станет равной количеству совпадений 
//контрольной маски с сформированной последовательностью
int s=0;
for(int i0=pw;i0<=lenrez;i0++)
{//i0
//проверка совпадения маски с содержимым под маской
int eqm=1;
for(int i1=0;i1<pw;i1++)if(result[i0+i1-pw]!=mask[i1]){eqm=0;break;}
if(eqm==1)s++;
}//i0
//печатаем очередное число вхождений 
//маски в сформированную последовательность
//этот громоздкий вариант печати здесь дезактивирован
//System.out.println(String.valueOf(s));

//подготовка укороченных оценок качества результата
if(s<mincount)mincount=s;
if(s>maxcount)maxcount=s;
}//im
System.out.println("минимум вхождений="+String.valueOf(mincount));
System.out.println("максимум вхождений="+String.valueOf(maxcount));
}//pw

return;
}//main

}//class