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

Проблема создания таких программ широко обсуждалась в математической литературе в 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 будет помещено //в начало формируемой псевдослучайной последовательности resultint p=beg,bp=0;for(;;){//cir raspakresult[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) это //признак того, что очередной символ формируемой выходной //последовательности определился в результате расчёта//если расчёт не сможет определить очередной символ, //то он будет задан из переменной rsint 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;//вычисление eqmfor(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;}}//lenmaskif(hs==1)continue;//если расчёт не определил очередной символ, //то он формируется из переменной rsresult[pos]=rs;rs=(byte)(1-rs);}//circlepos//выходная последовательность готова//осталось выдать её на печатьso="";for(int i=0,c=0;i<lenrez;i++){//out rezso+=String.valueOf(result[i]);c++;if(c==64){c=0;System.out.println(so);so="";}}//out rezSystem.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//заполнение маски двоичным представлением числа imp=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;}//imSystem.out.println("минимум вхождений="+String.valueOf(mincount));System.out.println("максимум вхождений="+String.valueOf(maxcount));}//pwreturn;}//main}//class