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

[Sicker]

Если у нас есть бесконечная последовательность нулей и единиц, то насколько верны следующие утверждения
1. Существует такая функция $F$, которая для любой последовательности может сказать, является ли она "случайной (т.е. получена с помощью генератора случайных чисел) с вероятностью почти $1$", или нет
2. Для любого теста на случайность можно найти неслучайную последовательность (которая не является случайной с вероятностью почти $1$ из первого пункта), для которой тест даст положительный ответ на случайность последовательности

[alisa-lebovski]

1. Нет.
2. Да (если не ссылаться пункт 1).

[Sicker]

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

1. Нет.

Почему?

-- 08.01.2021, 11:18 --

Если ответ на первый пункт "нет", то получается у нас есть бесконечная последовательность неслучайных битов, неужели их нельзя опознать?

-- 08.01.2021, 11:19 --

И да, под "опознать" я имел ввиду существование неконструктивной функции "опознания"

[alisa-lebovski]

Кстати, так называемые генераторы случайных чисел, которые сейчас используются в компьютерах, это на самом деле генераторы ПСЕВДОслучайных чисел, которые на самом деле не случайны, а детерминированы, и тем не менее, широко используются, потому что обладают нужными на практике свойствами, проходят тесты и т.п. С какой-то точки зрения, это грандиозное жульничество. Раньше использовались генераторы действительно случайных чисел, основанные на радиоактивном распаде, но от них отказались из-за дороговизны и опасности.

Или вот возьмите двоичное разложение числа "пи", или даже десятичное разложение, в котором четные цифры заменены на нули, а нечетные на единицы. Думаете, сможете его опознать, если заранее не знаете?

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

[StaticZero]

(Оффтоп)

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

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

Псведослучайное распределение?

[alisa-lebovski]

StaticZero в сообщении #1499605 писал(а):

Псевдослучайное распределение?

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

[StaticZero]

(Оффтоп)

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

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

Термина нет, а вот алгоритмы такие есть (по крайней мере, широко известна одна из концептуальных реализаций):

https://dota2.gamepedia.com/Random_distribution писал(а): писал(а):

The pseudo-random distribution (often shortened to PRD) in Dota 2 refers to a statistical mechanic of how certain probability-based items and abilities work. In this implementation the event's chance increases every time it does not occur, but is lower in the first place as compensation. This results in the effects occurring more consistently.

[StepV]

Sicker в сообщении #1499571 писал(а):

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

Не знаю современных возможностей, т.к давно с генераторами случайных чисел не работал. Но в 90-е годы определить было очень просто с вероятностью равной 1. Запускаешь тест первый раз и распечатываешь первые двадцать сгенерированных случайных чисел, затем второй раз и опять распечатываешь опять первые двадцать чисел.
Если в обоих прогонах числа совпадают, то это генератор случайных чисел.
Кстати, в то время утверждали, что, по крайней мере, на каждом компе генератор генерит свою последовательность, в зависимости от номера компа и номера BIOS. Но я сам не проверял.

[alisa-lebovski]

StepV в сообщении #1499619 писал(а):

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

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

[Sender]

Исходный вопрос вообще слишком расплывчат, чтобы можно было ответить что-то определённое.

[arseniiv]

(Оффтоп)

StaticZero в сообщении #1499617 писал(а):

Термина нет, а вот алгоритмы такие есть

Да, конечно. В каждом таком случае нарушается в первую очередь независимость разных выданных генератором «случайных величин» (без кавычек если мы рассматриваем соответствующую модель). Я даже придумал одно семейство достаточно естественных алгоритмов случайного выбора из плейлиста, зависящее от параметра «памяти» о ранее проигранных песнях; на одном конце памяти совсем нет и мы имеем независимые равномерные распределения, на другом конце, насколько помню, генерируется случайная перестановка и после этого алгоритм нужно перезапускать, потому что присвоенные трекам веса обнуляются.

StepV в сообщении #1499619 писал(а):

Если в обоих прогонах числа совпадают, то это генератор случайных чисел.

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

Вообще конечно для некоторых ГПСЧ были теоретические доказательства их статистических свойств, хотя вряд ли всех, проверяемых соответствующими пакетами тестов.

[Osmiy]

Sicker в сообщении #1499571 писал(а):

1. Существует такая функция $F$, которая для любой последовательности может сказать, является ли она "случайной (т.е. получена с помощью генератора случайных чисел) с вероятностью почти $1$", или нет

У псевдослучайных чисел есть закономерность появления следующего числа от предыдущих. Если она элементарна, то это легко вычисляется. Если это удалось, то с вероятностью очень близкой к 1 это псевдослучайные числа. Если закон сложен, то вычислить его не получиться из-за комбинаторного взрыва.

[mihaild]

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

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

Только не к плеерам, а к онлайн-радио. Spotify, метод называется smart shuffle.

Sicker в сообщении #1499571 писал(а):

1. Существует такая функция $F$, которая для любой последовательности может сказать, является ли она "случайной (т.е. получена с помощью генератора случайных чисел) с вероятностью почти $1$", или нет

Уточните модель вычисления и требований к функции.
Еще можете попробовать почитать про случайность по Мартин-Лёфу, там формализуется понятие случайности для конкретной последовательности.

[B@R5uk]

Чтобы добавить больше смысла в дискуссию, давайте переформулируем вопрос топикстартера таким образом. Пусть у нас есть возможность получить бесконечную случайную последовательность нулей и единиц. Будем считать, что это цифры после запятой двоичного представления некоторого числа на отрезке $[0,1]$. Вопрос: будут ли такие числа иметь равномерное распределение на отрезке?

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

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

Раньше использовались генераторы действительно случайных чисел, основанные на радиоактивном распаде, но от них отказались из-за дороговизны и опасности.

В состав некоторых современных материнских плат входит генератор истинно случайных чисел (на тепловом шуме).

StepV в сообщении #1499619 писал(а):

Не знаю современных возможностей, т.к давно с генераторами случайных чисел не работал. Но в 90-е годы определить было очень просто с вероятностью равной 1. Запускаешь тест первый раз и распечатываешь первые двадцать сгенерированных случайных чисел, затем второй раз и опять распечатываешь опять первые двадцать чисел.
Если в обоих прогонах числа совпадают, то это генератор случайных чисел.
Кстати, в то время утверждали, что, по крайней мере, на каждом компе генератор генерит свою последовательность, в зависимости от номера компа и номера BIOS. Но я сам не проверял.

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