Не очень случайные числа

[G-Shadow]

Однажды я написал такую программу. Был файл, в каждой строчке - набор слов. Программа из каждой строки брала случайное слово. Получался такой случайный текст.

Запуская её много раз для одного файла я заметил, что часть слов выпадает часто, а другая часть - редко или почти ни разу. Я сделал тест распределения случайных чисел. Генерировал тысячи чисел и считал сколько каждое выпало. Вышел ровный равномерный график.

Выходит, сами по себе числа очень равномерно выпадают, а на деле - то ли повторяющиеся цепочки в них, то ли ещё что-то.

Вопрос - в чем могло быть дело. И какие есть критерий оценки случайности генератора псевдо-случайных чисел кроме такого распределения сколько раз какое выпадет? Уже прошло лет 10+, а эта фигня всё всплывает иногда в памяти. В теории вероятности я не особо силен (хотя, если без этого не понять, может найду время подучить)

@темы: Математика, Компьютеры

Comments

[Albertia Inodorum]

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

[курлы-курлы]

генерация псевдослучайных чисел
нэ?
и цепочки чисел - да. поэтому они и псевдослучайные)

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

нас учили только распределениями оценивать, но их давалось штуки 3-4. По названиям вспоминаются: Пуассона... Логарифмическое. и еще какие-то.

[alba-longa]

Ну так все правильно при уходе в бесконечность получается равномерное распределение, а малую выборку нельзя считать достоверной.
Вопрос в минимальном объеме выборки, при котором оно будет работать правильно. Я полагаю, для того чтобы хорошо работал рандом в списке из не более чем сотню треков, необходимо подбирать ГПСЧ для каждого числа записей индивидуально, что, как сами понимаете, невыгодно. Поэтому во все такие устройства встроен простенький универсальный, который имеет хорошие характеристики при уходе в бесконечность, но для альбома в 13 песен выбирает в 90% случаев из 5-6. Ну и Ваша программа была сделана по тому же принципу

[Foul thing]

Я не сильно вдавался в тему, но если перед функцией random() в с++ вызвать функцию randomize(), то случайные числа генерируются гораздо более случайным образом )

[Albertia Inodorum]

ну там треков триста, но видимо недостаточно этого

[alba-longa]

Foul thing
я думаю, что дело не в этом, ибо если рандомайзер не включен, то уже после пары запусков заметно, что всегда одно и то же генерируется

[Trotill]

Если 10 лет назад, то какой-нибудь Turbo Pascal 7.0, а в старых компиляторах были реализованы генераторы на простом линейном конгруэнтном генераторе. Статические свойства у них, в принципе, хорошие. Какой компилятор был?

[I-lang]

alba-longa
Хм... И при уходе за 1000 звучит в лучшем случае - сотня.
Этого количества так же недостаточно?
Кстати, справедлива обратная зависимость: чем меньше в альбоме, тем больше шансов на проигрывание всех.


Помню, как раз около 10 лет назад в КвикБейсике для генерации "более случайных" чисел писали именно "рандомайзер" вместо обычно "рэндом". Правда, дело было в школе, и нам кроме пояснения, что одни случайные числа бывают более случайные, чем другие, ничего не сказали.

[alba-longa]

I-lang

Этого количества так же недостаточно?

Дело не только в количестве треков, но и в количестве наблюдений. Если у Вас альбом в 15 треков, то надо минимум несколько сотен наблюдений, чтобы треки выдавались действительно с одинаковой вероятностью (цифры примерные). Теперь представьте, сколько надо наблюдений, чтобы проследить эту зависимость на тысяче треков. Мне лень писать подробные выкладки, но суть в том, что равномерность выпадения гарантируется при числе проигрываний, которое стремится к бесконечности.

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

Нет, тем больше шансов, что у Вас хватит терпения их услышать

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

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

[Trotill]

В тему - есть хорошая и интересная книга про генераторы ПСП: Теория, применение и оценка качества генераторов псевдослучайных последовательностей. Валяется в сети в электронном виде.

[I-lang]

alba-longa
Ага! Ок! Спасибо.