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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На самом деле используется тепловой/полупроводниковый шум внутренних компонентов. Просто на него может накладываться шум со стороны цифровой части и процессорного ядра (внутри кристалла), который по своей природе детермистичен. Я не знаю, как оценить этот вклад.

2 Dot

сотрю тема не новая... но если ты еще на нее поглядываешь, то хотелсоь бы у тебя спросить КАК ГЕНЕРИШЬ эту случайную последоватьельность? формула и\или схема есть? или хотя бы опиши словами. это меня интересует

т.е. это не ответ на твой вопрос, а мой вопрос...

а к твойму вопросу ответ - все правильно люди говорят - "случайность" зависит от задачи для которой генеришь : для криптографии, для игры, для ....

и еще - можешь прислать кусок этой последовательности в файле? попробую проанализировать... если будет время

Кристалл CY8C27xxx от Cypress.
Внутри есть аналоговые блоки на основе ОУ, которые могут давать шум сомнительной природы (при особой конфигурации).
Есть и цифровые блоки на основе сдв.регистров с обратными связями 8...32 бит, которые могут дополнительно "ослучаить" последовательность, что я и делаю для большей надежности.
Будет время, материал выложу на свою страничку.