Произвести оценку последовательности

[Liverpool]

Есть некая последовательность из 0 и 1. Для этой последовательности предложить критерий, является ли последовательность случайной, равновероятной и независимой. Можете помочь уважаемые форумчане, как это сделать. Я представляю, что это связано. Центральной предельной теоремой, если память не подводит...

[Brukvalub]

Liverpool в сообщении #1251218 писал(а):

Есть некая последовательность из 0 и 1. Для этой последовательности предложить критерий, является ли последовательность случайной

То есть, по конечному набору нулей и единиц требуется узнать, не выборка ли это значений двузначной с.в.? А это возможно?

[Liverpool]

Brukvalub А разве невозможно? Как я понимаю, при равновероятном условии последовательность содержит одинаковое или близкое к этому количество нулей и единиц. Вероятность исхода которого составляет 1/2.

[teleglaz]

Таких тестов полно. Посмотрите, например, так называемые, статистические тесты NIST. Они не абы кем придуманы, и я думаю вам помогут. Но если нет, то и это не всё. Есть достаточно литературы по этой теме.

А начать можно с какого-нибудь простенького частотного, например.

[Dmitriy40]

Для конечной последовательности это невозможно, все тесты выдадут лишь ограничение снизу (или сверху) на вероятность, что эта последовательность случайна или нет. Ни до 0 ни до 1 вероятность не дотянется, т.к. всегда останется возможность что это именно или абсолютно случайные числа, или они получены по детерменированному (но неизвестному нам) алгоритму (т.е. абсолютно не случайны). И ни один из тестов не сможет 100% исключить ни то, ни другое.

[Brukvalub]

teleglaz в сообщении #1251230 писал(а):

Посмотрите, например, так называемые, статистические тесты NIST.

Это хорошие тесты для проверки гипотезы "действительно ли число нулей и единиц в последовательности приблизительно одинаковы, как это можно было бы предположить в случае истинно случайной бинарной последовательности."
Но речь-то шла о другом:

Liverpool в сообщении #1251218 писал(а):

Для этой последовательности предложить критерий, является ли последовательность случайной

[Xaositect]

Brukvalub в сообщении #1251238 писал(а):

Это хорошие тесты для проверки гипотезы "действительно ли число нулей и единиц в последовательности приблизительно одинаковы, как это можно было бы предположить в случае истинно случайной бинарной последовательности."

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

Но, конечно, никакой тест не скажет, действительно ли поледовательность является случайной.

[Liverpool]

Как я понимаю здесь все упирается в центральную предельную теорему. Только вот как описать все с помощью неё, я пока не знаю..

[teleglaz]

Что-то я действительно не понял в вопросе. А что значит

Xaositect в сообщении #1251239 писал(а):

действительно ли поледовательность является случайной.

Что имеется ввиду?

Любая гипотеза принимается на некотором уровне значимости. Соответственно и гипотеза о случайности будет приниматься или отвергаться на некотором уровне значимости. И никак иначе.

Для проверки того, что выборка удовлетворяет распределению Бернулли с параметром 0,5, а в данном случае именно оно и есть, критерия согласия Пирсона хватает вполне. И тут можно вполне без ЦПТ обойтись. Посчитать статистику Пирсона, посмотреть попадает ли она в критическую область. Если попадает, то гипотеза отвергается, если нет - то принимается (на соответствующем уровне значимости!!!). Для данного распределения считается удобно и для больших объёмов (а они нужны).

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

[Brukvalub]

teleglaz в сообщении #1251278 писал(а):

Что имеется ввиду?

Любая гипотеза принимается на некотором уровне значимости. Соответственно и гипотеза о случайности будет приниматься или отвергаться на некотором уровне значимости. И никак иначе.

Для проверки того, что выборка удовлетворяет распределению Бернулли с параметром 0,5, а в данном случае именно оно и есть, критерия согласия Пирсона хватает вполне.

Вы предлагаете проверять гипотезу: "последовательность является выборкой с.в., подчиняющейся распред. Бернулли с вер. успеха 0.5".
Но исходный вопрос стоял иначе:

Liverpool в сообщении #1251218 писал(а):

Для этой последовательности предложить критерий, является ли последовательность случайной

[vicvolf]

Liverpool в сообщении #1251218 писал(а):

Есть некая последовательность из 0 и 1. Для этой последовательности предложить критерий, является ли последовательность случайной, равновероятной и независимой.

Вы задали интересный вопрос. Вам правильно ответили, что показать на 100%, что данная последовательность является случайной с помощью критерия согласия нельзя. Вы сможете доказать это только с определенной вероятностью, равной значимости критерия. Но это и не требуется. Для этого Колмогоровым была создана аксиоматика теории вероятности. Вам надо только построить вероятностное пространство для данной величины и пользуйтесь на здоровье мощным аппаратом теории вероятности. Но учтите все доказательства в теории вероятности будут (в лучшем) для почти всех случаев, а не для всех. Поэтому, если можете доказать какое-то утверждение без использования теории вероятности (для всех случаев), то доказывайте.
Теперь о независимости. Для использования различных предельных теорем теории вероятности совсем не обязательно доказывать независимость случайной последовательности. Часто бывает достаточно показать, что последовательность обладает свойствами слабой зависимости (например, стационарности или перемешивания).

[realeugene]

Liverpool в сообщении #1251218 писал(а):

Для этой последовательности предложить критерий, является ли последовательность случайной, равновероятной и независимой.

Хорошие алгоритмы генерации псевдослучайных чисел выдают битовые последовательности, которые согласно всем известным критериям выглядят как случайные, равновероятные и независимые. Являясь при этом полностью детерминированными.