Программный генератор статистически безупречных случайных чисел
Проблема создания таких программ широко обсуждалась в математической литературе в 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