Я тут микроконтроллером генерирую случайные последовательности.
Может кто подскажет, в каком направлении копать, чтобы доказать, что полученная последовательность является абсолютно случайной?

На текущий момент мне представляется один критерий -- гладкость фурье-спектра.
Но с другой стороны гладкость обеспечиватся и обычными генераторами псевдослуч. последовательностей на основе сдвиг.регистров с обратными связями.

Спектр полученного сигнала -- в приложении. F -- частота сэмплироания (битов).
Есть пики, с этим не поспоришь. Но они пропадают, если последовательность дополнительно пропустить через тот же регистр с обр. связями.

http://csrc.nist.gov/rng/rng9.html

Найдите и скачайте бесплатный пакет DieHard - там все тесты на случайность уже реализованы.

Спасибо.
Нашел безответный топик одной девушки
http://forums.software-testing.ru/index.php?showtopic=3896
В нем много интересных ссылок.

Как я понял случайность не доказуема. Проверяется только отсутствие той или иной случайности.

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

Ваш генератор - хаотическая система.
Если Вы не используете в нем какой-то другой источник шума, например, тепловой шум, то "добротность" Вашей системы можно проверить вычислением корреляционной размерности временного ряда сгенерированной "случайной последовательности".
Корреляционную размерность K=2 дает простейший класический генератор (формулу не помню).
Субъективно считаю что при K>6..8 уже сложно проверить чем сформирована "случайная последовательность" - хаотической системой, созданной человеком, или богом - ибо для проверки понадобиться "очень много оперативки и производительности вычислителя"

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

Микроконтроллер, и др. микропроцессорная система - конечный автомат, он может генерировать не случайную, а псевдослучайную последовательность (ПСП) с очень большим периодом, поскольку сам по себе является системой детерминированной. В зависимости от задачи, требования к последовательности (к статистическим и частотно-временным параметрам) могут быть разные. По поводу генераторов ПСП и критериев их "качества" много и доступно написано в книжке Аверилл М. Лоу и Дэвида Кельтона "Имитационное моделирование".

Сообщение отредактировал Pathfinder - Mar 1 2006, 20:28

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

Сообщение отредактировал Silent Observer - Mar 2 2006, 11:27

Автокорреляционная функция (АКФ) характеризует лишь частотно-временные свойства и не более того. АКФ является дельта-функцией только для БЕЛОГО шума. Если пропустить белый шум через фильтр, он не станет от этого менее "случайным", хотя корреляционная функция при этом изменится. Вообще "случайность" это противоположность детерминированности, и вопрос постановки задачи. Даже синус для нас является случайным если мы не знаем заранее что будет получен именно он.

А вот если этому конечному автомату дать вычислять Пи (3.14....) или корень из двух, то что (по Вашему) получится периодическая дробь? Да, последовательность цифр будет детерминирована, но вполне подойдет в качестве псевдослучайной.

Это была провокационная шутка. Извините. Странно, что никто не прореагировал.

Пропустив случайный процесс через фильтр, вы ограничите спектр этого процесса, а это уже элемент детерминированности. Спектр случайного процесса также должен быть случайным.

Так. Уважаемый Silent Observer, срочно открываем любой учебник по стат. радиофизике, или просто по статистике, и читаем что такое случайный процесс и какие у него есть характеристики, а также связь между ними. Если надо, могу в электронном виде прислать.
Случайность и детерминизм меряются относительно задачи - если мы не знаем какой сигнал будет принят - то он случайный. Любое невырожденное преобразование этого случайного процесса (линейное/нелинейное, с памятью/без памяти) не делает его детерминированным, даже если мы знаем как при этом изменятся его характеристики.
Что касается спектра - тут Вы сами себе противоречите - АКФ в виде дельта-функции соответствует спектр белого шума - абсолютно детерминированный спектр.

А чем не подходит шум зенера или иного теплового процесса? Что значит «абсолютно случайный»? Изначально некорректный вопрос, на мой вкус.