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

[alisa-lebovski]

B@R5uk в сообщении #1499665 писал(а):

Пусть у нас есть возможность получить бесконечную случайную последовательность нулей и единиц.

Нет, Вы подразумеваете, что у нас есть возможность получить бесконечно много бесконечных последовательностей нулей и единиц, только тогда имеет смысл говорить о распределении чисел. Это еще дальше от начала, чем два прогона. Речь же шла об ОДНОЙ последовательности, и можно ли ее идентифицировать как случайную, по ней самой, безотносительно к другим последовательностям и методам формирования.

[Евгений Машеров]

Вообще, я бы посоветовал почитать Кнута. 2 том, 4 глава. Там есть раздел с обсуждением понятия случайности применительно к ГСЧ.
Ну и само требование "равномерно распределённых случайных чисел" содержит в себе некоторое противоречие (недодавленый философ во мне пищит: "Диалектическое!"). Равномерность это некая предсказуемость, а случайность - напротив. Отсюда претензии к "недостаточной случайности" действительно случайных чисел, попытки выстроить систему выигрыша в казино, исходя из того, что после N красных должно же быть чёрное, иначе нет равномерности и т.п. При этом для одних задач важнее равномерность (интегрирование Монте-Карло), для других непредсказуемость (криптография).

[Someone]

Евгений Машеров в сообщении #1499678 писал(а):

Равномерность это некая предсказуемость, а случайность - напротив. Отсюда претензии к "недостаточной случайности" действительно случайных чисел

Ага. Они имеют "противоестественную" склонность собираться в тесные группы, противоречащие интуитивным представлениям о равномерном распределении. Например, если на отрезке $[0,L]$ выбрать $n>1$ равномерно распределённых случайных чисел, то неожиданно оказывается, что математическое ожидание наименьшего интервала между ними равно $\frac L{n^2-1}$ (формулу воспроизвёл по памяти; надеюсь, не наврал), хотя интуитивно ожидается что-нибудь не сильно меньше $\frac L{n+1}$. Задача о днях рождения тоже это хорошо демонстрирует.

[ИСН]

B@R5uk в сообщении #1499665 писал(а):

Вопрос: будут ли такие числа иметь равномерное распределение на отрезке?

Равномерное распределение современные датчики ПСЧ создают. Но это даже не пол-дела.

[Евгений Машеров]

Более того, датчик вида

int RRRRRandom(int *x)
{
    return (x+1)%N;
}

будет при последовательных вызовах выдавать идеально равномерную последовательность от 0 до $N-1$, вот только со случайностью что-то не то...

[alisa-lebovski]

Абстрагируемся от компьютерных дел и генераторов случайных чисел, и рассмотрим чисто математическую задачу. Допустим, у нас есть актуально бесконечная последовательность 0 и 1. Если это последовательность независимых одинакового распределенных случайных величин, принимающих значения 0 и 1 с вероятностями по 1/2, то для нее будет выполняться ряд утверждений с вероятностью 1: усиленный закон больших чисел, закон повторного логарифма, пределы условных вероятностей 0 и 1 при условиях, что до этого шли какие-то наборы 0 и 1, или что после этого будут и т.д. Допустим, есть функция, проверяющая эти утверждения. Понятно, что все перечисленное входит в число необходимых условий. Вопрос: можно ли сформулировать набор утверждений (конечный или счетный), который будет давать достаточные условия?

[mihaild]

alisa-lebovski в сообщении #1500037 писал(а):

Понятно, что все перечисленное входит в число необходимых условий. Вопрос: можно ли сформулировать набор утверждений (конечный или счетный), который будет давать достаточные условия?

Эти все условия имеют вид "последовательность не принадлежит какому-то множеству нулевой меры" (множеству последовательностей, для которых нарушается ЗБЧ, закон повторного логарифма) и т.д. "Достаточные условия" - это, соответственно, наибольшее множество нулевой меры. Его существование зависит от того, какие множества мы рассматриваем, если все - то его понятно не существует, если только эффективно нулевые - то существует.

[alisa-lebovski]

mihaild, речь действительно идет об исключении некоторых множеств нулевой меры, но не любых множеств нулевой меры, потому что так можно дойти до исключения любых индивидуальных последовательностей, имеющих нулевую меру, а в сумме дающих все пространство, и ничего не получится. Под условиями подразумеваются события из хвостовой сигма-алгебры, т.е. типа пределов (в том числе, верхних и нижних, как в ЗПЛ), так что любую последовательность можно менять в любом конечном числе знаков.

[mihaild]

alisa-lebovski в сообщении #1500099 писал(а):

Под условиями подразумеваются события из хвостовой сигма-алгебры

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

[ewert]

alisa-lebovski в сообщении #1500037 писал(а):

Вопрос: можно ли сформулировать набор утверждений (конечный или счетный)

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

Евгений Машеров в сообщении #1499669 писал(а):

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

Не для тестирования, а для воспроизводимости. Во всяком случае, ровно так обстоит дело для учебных задачек.
Которые должны быть непредсказуемы для пользователя. Но -- абсолютно воспроизводимы для составителя.

[Евгений Машеров]

Тестирования в смысле процесса отладки программы. Запустили тесты, получили не то. Изменили программу, запустили ещё раз тесты - и чтобы быть уверенным в том, что изменение результата вызвано именно изменением программы, надо запускать ГСЧ с теми же начальными установками.

[ewert]

Вот, кстати, что к сожалению.

RandSeed'ы нестабильны.
Даже в разных версиях Матлаба они выдают, кажется, разные вещи
(не говоря уж об уродливости в данном конкретном случае матлабовского синтаксиса).
А в Октаве -- который, в принципе-то, и синоним Матлаба -- так там и вовсе всё иначе.

Короче: в матлабоподобии полагаться на базы генератора совершенно невозможно, увы.

Да и даже в том же Паскале: я вынужден запускать Борланд под виртуалкой --
-- в первую очередь потому, что Фри уродлив; но ещё и потому, что не доверяю базе Фри-генератора.

-- Вс янв 10, 2021 23:24:25 --

Евгений Машеров в сообщении #1500161 писал(а):

Изменили программу, запустили ещё раз тесты - и чтобы быть уверенным в том, что изменение результата вызвано именно изменением программы, надо запускать ГСЧ с теми же начальными установками.

Ну это мелко, как мне кажется -- обычно расхождения в результатах вызывается гораздо более грубыми причинами. Но это совсем уж моё внутреннее ИМХО.

[mihaild]

ewert в сообщении #1500158 писал(а):

Конечный или счётный?
Счётный, разумеется, невозможен.
Конечный -- заведомо не будет исчерпывающим.

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

[alisa-lebovski]

mihaild в сообщении #1500143 писал(а):

Такими тоже несложно покрыть весь отрезок (условие вида "последовательность совпадает с данной, начиная с некоторой позиции").

Так я и говорю, что не надо цепляться ни к какой данной, индивидуальной последовательности, а только к их классам, выделяемым по каким-то пределам и т.п. По поводу вычислимости, не очень поняла - пределы же не вычислимы (за конечное время).

mihaild в сообщении #1500174 писал(а):

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

Да, счетное число однотипных утверждений можно объединять в одно, например, сходимость к 1/2 условных частот 0 и 1 при условиях, что известны любые конечные наборы каких-то предшествующих или последующих элементов. Но достаточно ли этого будет для независимости? Подозреваю, что нет.

[mihaild]

alisa-lebovski в сообщении #1500212 писал(а):

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

А как это формализуется? Вы сказали - "принадлежит хвостовой сигма-алгебре", это я понимаю, что значит. Что значит "выделяется по каким-то пределам" - не понимаю.
Ну скажем пусть $x$ - некоторая конкретная последовательность, тогда, если $y$ - случайная, то с вероятностью $1$ будет $\limsup\limits_{i \to \infty} |x_i - y_i| = 1$. Это считается "выделением по пределам"?

alisa-lebovski в сообщении #1500212 писал(а):

По поводу вычислимости, не очень поняла - пределы же не вычислимы

Вычислимы не пределы, а множества нулевой меры, которые являются критериями.
Формально, множество называется эффективно нулевым, если существует алгоритм, который по (рациональному) $\varepsilon$ выдает покрытие этого множества интервалами суммарной длины меньше $\varepsilon$.
Например множество последовательностей, для которых нарушается ЗБЧ, является эффективно нулевым.

alisa-lebovski в сообщении #1500212 писал(а):

Но достаточно ли этого будет для независимости?

Независимости чего?