2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 09:49 
Аватара пользователя


13/08/13

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

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 10:48 
Заслуженный участник
Аватара пользователя


05/12/09
1760
Москва
1. Нет.
2. Да (если не ссылаться пункт 1).

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 11:17 
Аватара пользователя


13/08/13

4323
alisa-lebovski в сообщении #1499578 писал(а):
1. Нет.
Почему?

-- 08.01.2021, 11:18 --

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

-- 08.01.2021, 11:19 --

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

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 13:06 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 13:20 
Заслуженный участник
Аватара пользователя


22/06/12
2129
/dev/zero

(Оффтоп)

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

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

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 13:26 
Заслуженный участник
Аватара пользователя


05/12/09
1760
Москва
StaticZero в сообщении #1499605 писал(а):
Псевдослучайное распределение?
Нет такого термина. Насколько я понимаю, они запретили некоторые последовательности.

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 13:46 
Заслуженный участник
Аватара пользователя


22/06/12
2129
/dev/zero

(Оффтоп)

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.

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 13:49 
Аватара пользователя


23/05/20
336
Беларусь
Sicker в сообщении #1499571 писал(а):
для любой последовательности может сказать, является ли она "случайной (т.е. получена с помощью генератора случайных чисел) с вероятностью почти $1$", или нет


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

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 14:22 
Заслуженный участник
Аватара пользователя


05/12/09
1760
Москва
StepV в сообщении #1499619 писал(а):
Запускаешь тест первый раз и распечатываешь первые двадцать сгенерированных случайных чисел, затем второй раз и опять распечатываешь опять первые двадцать чисел.
Если в обоих прогонах числа совпадают, то это генератор случайных чисел.
Конечно, потому что это генератор псевдослучайных чисел, рекуррентная последовательность, где каждое значение вычисляется по предыдущему (или нескольким предыдущим), начиная с первого, называемого "зерном". Если "зерно" не менять, получается одно и то же. Если менять, получается разное. Но исходный вопрос не предусматривал никаких двух прогонов. На этот счет есть анекдот: в автобусе человека спрашивают, когда будет такая-то остановка. Он отвечает: выходите за две остановки до меня.

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 14:38 


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

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 14:41 
Заслуженный участник


27/04/09
28128

(Оффтоп)

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

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

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

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 14:44 


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

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

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 15:04 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
alisa-lebovski в сообщении #1499598 писал(а):
Какая-то фирма добавила к плеерам функцию случайного выбора музыкальных треков, так люди стали жаловаться, что они не достаточно случайны (например, было много повторов). Пришлось изменить алгоритм, при новом выбор стал менее случайным на самом деле, но более случайным с человеческой точки зрения.
Только не к плеерам, а к онлайн-радио. Spotify, метод называется smart shuffle.
Sicker в сообщении #1499571 писал(а):
1. Существует такая функция $F$, которая для любой последовательности может сказать, является ли она "случайной (т.е. получена с помощью генератора случайных чисел) с вероятностью почти $1$", или нет
Уточните модель вычисления и требований к функции.
Еще можете попробовать почитать про случайность по Мартин-Лёфу, там формализуется понятие случайности для конкретной последовательности.

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 15:28 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Бесконечная последовательность нулей и единиц
Сообщение08.01.2021, 15:42 
Заслуженный участник
Аватара пользователя


11/03/08
9490
Москва
alisa-lebovski в сообщении #1499598 писал(а):
Раньше использовались генераторы действительно случайных чисел, основанные на радиоактивном распаде, но от них отказались из-за дороговизны и опасности.


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

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


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 60 ]  На страницу 1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group