Где взять истинно случайную последовательность?

На первый взгляд, эта задача очень проста. Можно, например, вычислить случайный адрес памяти и взять оттуда данные. Или можно вычислить случайный номер сектора на диске и взять данные оттуда. Эти данные, бесспорно, будут случайными. Но какое распределение будут иметь члены полученной случайной последовательности? Неизвестно. Если полученные случайные данные представляют собой фрагмент текстового файла, то распределение символов, представляемых байтами файла, будет одно, если это фрагмент машинного кода - совсем другое. Одно можно сказать точно - это распределение почти никогда не будет равномерным. Ниже приведены гистограммы встречаемости символов для различных видов информации.

Как видите, из всех приведенных гистограмм только последняя более-менее похожа на гистограмму равномерного распределения. Однако, если приглядеться повнимательнее, в ней можно заметить пик вдоль оси (впрочем, этот пик нетипичен для архивов pkzip - он объясняется тем, что выбранный архив включал в себя очень много коротких файлов).

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

Как видите, распределения отличаются довольно сильно. Получается, что если в документе есть картинки, исходное распределение одно, а если нет - совсем другое.

Кроме того, в осмысленных текстах (в том числе и в текстах exe-файлов, баз данных и т.д.) обязательно присутствуют статистические закономерности более высокого порядка. Если построить гистограмму встречаемости биграмм и триграмм, она будет еще менее похожа на горизонтальную линию (что должно иметь место при равномерном распределении), чем гистограмма встречаемости отдельных символов. Например, в exe-файле, скомпилированном с помощью Visual C, машинный код подавляющего большинства функций (подпрограмм) начинается байтами

55 8B EC 83 EC2)

и заканчивается байтами

8B E5 5D C3.3)

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