2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 16:07 
Аватара пользователя
B@R5uk в сообщении #1499665 писал(а):
Пусть у нас есть возможность получить бесконечную случайную последовательность нулей и единиц.
Нет, Вы подразумеваете, что у нас есть возможность получить бесконечно много бесконечных последовательностей нулей и единиц, только тогда имеет смысл говорить о распределении чисел. Это еще дальше от начала, чем два прогона. Речь же шла об ОДНОЙ последовательности, и можно ли ее идентифицировать как случайную, по ней самой, безотносительно к другим последовательностям и методам формирования.

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

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

 
 
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 22:54 
Аватара пользователя
B@R5uk в сообщении #1499665 писал(а):
Вопрос: будут ли такие числа иметь равномерное распределение на отрезке?

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

 
 
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение09.01.2021, 15:29 
Аватара пользователя
Более того, датчик вида
Код:
int RRRRRandom(int *x)
{
    return (x+1)%N;
}

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

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

 
 
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение10.01.2021, 12:43 
Аватара пользователя
alisa-lebovski в сообщении #1500037 писал(а):
Понятно, что все перечисленное входит в число необходимых условий. Вопрос: можно ли сформулировать набор утверждений (конечный или счетный), который будет давать достаточные условия?
Эти все условия имеют вид "последовательность не принадлежит какому-то множеству нулевой меры" (множеству последовательностей, для которых нарушается ЗБЧ, закон повторного логарифма) и т.д. "Достаточные условия" - это, соответственно, наибольшее множество нулевой меры. Его существование зависит от того, какие множества мы рассматриваем, если все - то его понятно не существует, если только эффективно нулевые - то существует.

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

 
 
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение10.01.2021, 21:32 
Аватара пользователя
alisa-lebovski в сообщении #1500099 писал(а):
Под условиями подразумеваются события из хвостовой сигма-алгебры
Такими тоже несложно покрыть весь отрезок (условие вида "последовательность совпадает с данной, начиная с некоторой позиции").
Я разумных вариантов ограничений, кроме требования вычислимости, придумать не могу.

 
 
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение10.01.2021, 22:07 
alisa-lebovski в сообщении #1500037 писал(а):
Вопрос: можно ли сформулировать набор утверждений (конечный или счетный)

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

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

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

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

 
 
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение10.01.2021, 22:21 
Вот, кстати, что к сожалению.

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

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

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

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

Евгений Машеров в сообщении #1500161 писал(а):
Изменили программу, запустили ещё раз тесты - и чтобы быть уверенным в том, что изменение результата вызвано именно изменением программы, надо запускать ГСЧ с теми же начальными установками.

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

 
 
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение10.01.2021, 23:47 
Аватара пользователя
ewert в сообщении #1500158 писал(а):
Конечный или счётный?
Счётный, разумеется, невозможен.
Конечный -- заведомо не будет исчерпывающим.
А что это более точно значит, с учетом того, что сколь-нибудь разумно составленный счетный список легким движением руки превращается в одноэлементный?

 
 
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение11.01.2021, 10:06 
Аватара пользователя
mihaild в сообщении #1500143 писал(а):
Такими тоже несложно покрыть весь отрезок (условие вида "последовательность совпадает с данной, начиная с некоторой позиции").
Так я и говорю, что не надо цепляться ни к какой данной, индивидуальной последовательности, а только к их классам, выделяемым по каким-то пределам и т.п. По поводу вычислимости, не очень поняла - пределы же не вычислимы (за конечное время).
mihaild в сообщении #1500174 писал(а):
сколь-нибудь разумно составленный счетный список легким движением руки превращается в одноэлементный?
Да, счетное число однотипных утверждений можно объединять в одно, например, сходимость к 1/2 условных частот 0 и 1 при условиях, что известны любые конечные наборы каких-то предшествующих или последующих элементов. Но достаточно ли этого будет для независимости? Подозреваю, что нет.

 
 
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение11.01.2021, 11:56 
Аватара пользователя
alisa-lebovski в сообщении #1500212 писал(а):
Так я и говорю, что не надо цепляться ни к какой данной, индивидуальной последовательности, а только к их классам, выделяемым по каким-то пределам и т.п.
А как это формализуется? Вы сказали - "принадлежит хвостовой сигма-алгебре", это я понимаю, что значит. Что значит "выделяется по каким-то пределам" - не понимаю.
Ну скажем пусть $x$ - некоторая конкретная последовательность, тогда, если $y$ - случайная, то с вероятностью $1$ будет $\limsup\limits_{i \to \infty} |x_i - y_i| = 1$. Это считается "выделением по пределам"?
alisa-lebovski в сообщении #1500212 писал(а):
По поводу вычислимости, не очень поняла - пределы же не вычислимы
Вычислимы не пределы, а множества нулевой меры, которые являются критериями.
Формально, множество называется эффективно нулевым, если существует алгоритм, который по (рациональному) $\varepsilon$ выдает покрытие этого множества интервалами суммарной длины меньше $\varepsilon$.
Например множество последовательностей, для которых нарушается ЗБЧ, является эффективно нулевым.
alisa-lebovski в сообщении #1500212 писал(а):
Но достаточно ли этого будет для независимости?
Независимости чего?

 
 
 [ Сообщений: 60 ]  На страницу Пред.  1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group