Случайности - не случайны? Изучаем Random и пытаемся найти истину

[Lord_Alfred]

Интро​

В множестве своих шаблонов я использую 4 вида Генерации Случайных Значений (ГСЗ; ГСЧ - чисел):

• Кубик Random -> Число
• Кубик Обработка текста -> Spintax
• C# код с инициализацией Random с seed (сидом)
• C# код с инициализацией Random без сида

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

Наконец-то у меня выбрался свободный вечерок, когда я захотел отдохнуть от повседневной работы и разобраться с этим рандомом.
Но всё вышло не так, как я думал. Я перелопатил множество источников, испробовал кучу вариантов генерации случайных чисел, научил зенку строить графики (ну почти) и совсем запутался. Поэтому и решил, что лучше выложу свои мысли на форуме, авось придёт кто-то из разработчиков или форумчан, кто более подкован в теории вероятности (я что смог с давних времён универа, то сделал) и объяснит как это должно работать. И правильно ли в ZennoPoster реализовано.

Испробованные варианты​

Я немного "упоролся" и попытался сделать генерацию максимально доступного мне количества вариантов - вышло аж 18. Полный список:

1. action_random - кубик Random [0, 10)
   
2. action_random_cycle - кубик Random [0, 10), но он запускается в цикле внутри самого шаблона 5000 раз
   
3. action_spintax - кубик Spintax {a|b|c|d|e|f|g|x|y|z}
   
4. action_spintax_cycle - кубик Spintax {a|b|c|d|e|f|g|x|y|z}, но он запускается в цикле внутри самого шаблона 5000 раз
   
5. csharp_global_random - Global.Classes.rnd.Next(0, 10)
   
6. csharp_Mersenne_Twister - Вихрь Мерсенна, реализация: http://www.prowaretech.com/Computer/DotNet/Mersenne
   
7. csharp_Mersenne_Twister_2 - Вихрь Мерсенна, реализация: https://github.com/grmartin/Mersenne-Twister (чуть адаптированная под зенку, вроде не сломал ничего)
   
8. csharp_random_with_seed_DateTime_Millisecond - Random с сидом "DateTime.Now.Millisecond"
   
9. csharp_random_with_seed_DateTime_Ticks - Random с сидом "(int) DateTime.Now.Ticks & 0x0000FFFF"
   
10. csharp_random_with_seed_Rei_LCG - Linear Congruential Generator, реализация из библиотеки Rei.Random
    
11. csharp_random_with_seed_Rei_MersenneTwister - Вихрь Мерсенна, реализация из библиотеки Rei.Random
    
12. csharp_random_with_seed_Rei_MotherOfAll - Mother Of All, реализация из библиотеки Rei.Random
    
13. csharp_random_with_seed_Rei_RanrotB - Ranrot-B, реализация из библиотеки Rei.Random
    
14. csharp_random_with_seed_Rei_SFMT - Быстрый Вихрь Мерсенна, реализация из библиотеки Rei.Random
    
15. csharp_random_with_seed_Rei_Well - Well, реализация из библиотеки Rei.Random
    
16. csharp_random_with_seed_Rei_Xorshift - Xorshift, реализация из библиотеки Rei.Random
    
17. csharp_random_with_seed_RNGCryptoServiceProvider - Random с сидом "RNGCryptoServiceProvider"
    
18. csharp_random_without_seed - Random без сида

В аттаче выкладываю архив с 18 версиями ГСЧ с помощью кубиков и кода, а также шаблон, который сгенерирует красивый репорт с графиками. Ну и свой репорт в виде html файла тоже выложу.

Как это использовать​

• Добавляйте Rei.Random.dll в ExternalAssemblies
• Добавляйте все шаблоны к себе в ZennoPoster
• Выделяете все шаблоны кроме "_draw_charts.xmlz"
• Добавляйте 1 выполнение
• Убираете выделение с шаблонов, которые на конце содержат "_cycle" (action_random_cycle, action_spintax_cycle) - чтоб было выделено 16 шаблонов
• Ставите всем шаблонам "Максимум потоков": 20
• Ставите всем шаблонам "Сколько делать": 5000
• Ждёте завершения работы всех шаблонов
• Убираете выделение со всех шаблонов
• Запускаете шаблон _draw_charts, чтобы сгенерировать репорт с графиками

Шаблоны и генератор репорта написаны таким образом, что просто складывают данные в папку data/название_шаблона.txt, поэтому вы можете добавить свои версии ГСЧ.

Расшифровка графика​

Каждый тест (шаблон) генератора случайных чисел получает вот такой график:

В его заголовке - собственно название шаблона. В оси X - случайные значения из выбранного в шаблоне интервала, в оси Y - их количество для каждого значения.
Под шаблоном идет подсчёт некоторых параметров (что я смог придумать и вспомнить):

• Min - минимальное количество полученных значений из всего интервала (для текущего примера: это 460 раз мы получили число 8 )
• Max - максимальное количество полученных значений из всего интервала (для текущего примера: это мы 536 раз получили число 1)
• Diff - разница между максимальным и минимальным
• Arithmetic Mean - среднее арифметическое (сумма всех значений к их количеству)
• Diff in percents - разница между максимальным и минимальным в процентах по отношению к среднему (то есть среднее арифметическое - это 100%, а разница - это X%, собственно здесь и считается это X)

Думаю, что там скорее всего ещё нужна дисперсия, но совершенно не уверен. И возможно разницу в процентах нужно считать по медиане, а не по среднему арифметическому...

Итог​

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

Собственно поэтому и выкладываю это всё здесь. Давайте порассуждаем и подумаем как это должно быть?

PS: выкладываю это всё "вне конкурса", т.к. нет итога. Если был бы итог - выложил бы на конкурсе может даже.

 

[amyboose]

ThreadLocal<Random> rnd = new ThreadLocal<Random>(() => new Random(Guid.NewGuid().GetHashCode()));
int x = 0;
for (int i = 0;i < 1000000;i++)
{
      x += rnd.Value.Next(460, 536);
}
x = x / 1000000;

Ответ - 497

 

[7make]

По классике все ГПСЧ во всех ЯП условно имеют (нормальное) гауссовское распределение
Суммы этих значений будут рисовать "Купол Гаусса" на графике.

твой Arithmetic Mean подтверждает это))

Если хочешь по хардкору это все прожевать, то нужно копать в сторону спецификаций к процам/материнкам как там работают таймеры хардварные
Именно на этом уровне все это.
потом уже дрова/ОС делают имплементацию
и потом уже всякие ЯП

уже проскакивал темка подобная на форуме поищи, там помню человек спрашивал про рандом как устроен дискутировали, с графиками если не ошибаюсь

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

Поэтому если не преследуется конкретная цель, лучше использовать "из каропки" генерацию, потому что она "нормальная", в противном случае в зависимости от места использования такие данные будут вылазить как аномалия на общем фоне и будет палево

любые данные которые будут подвязаны на кастомную функцию генерации в каком-то срезе да спалят тебя.

к примеру. взял свой рандом который можно отобразить некоторой функцией. на основе этого рандома ты решил засабмитить форму регистрации. и делашеь паузы между полями формы. а ребята "всякие маркетологи " уже туда настроили свои воронки продаж. И в одном из срезов спалят "явную аномалию" любое повторяющееся в периоде событие...

 

[Lord_Alfred]

Ответ - 497

Вот честно, я вообще не понял зачем ты этот код тут привёл... Да ещё и без описания.
При чем тут среднее арифметическое для генерации значений от 460 до 536? Не понимаю.

По классике все ГПСЧ во всех ЯП условно имеют (нормальное) гауссовское распределение
Суммы этих значений будут рисовать "Купол Гаусса" на графике.

Вот я тоже косвенно помнил про "Купол Гаусса", но как он доказывается и выводится - не мог вспомнить. Как из суммы значений вывести такое?

Спойлер: Видео по теме

Я сам смотрел это видео давно, но в голове чуть отложилось про купол. Сейчас пересмотреть нет времени, но для интересующихся пригодится:

твой Arithmetic Mean подтверждает это))

Разве?) Я вот ещё больше подумал на этот счет и понял, что он показывает выставленное количество попыток. И начал сомневаться правильно ли я его считаю
Потому что я рассчитывал его как: сумма количеств всех значений (сумма столбцов с графика по оси Y) / количество значений (ось X, в моих примерах всегда 10).

Если хочешь по хардкору это все прожевать, то нужно копать в сторону спецификаций к процам/материнкам как там работают таймеры хардварные

Да, вчера наткнулся на RdRand (вики), но т.к. у меня старый проц, то не проверить было.

уже проскакивал темка подобная на форуме поищи, там помню человек спрашивал про рандом как устроен дискутировали, с графиками если не ошибаюсь

Речь об этом топике?

к примеру. взял свой рандом который можно отобразить некоторой функцией. на основе этого рандома ты решил засабмитить форму регистрации. и делашеь паузы между полями формы. а ребята "всякие маркетологи " уже туда настроили свои воронки продаж. И в одном из срезов спалят "явную аномалию" любое повторяющееся в периоде событие...

Вот это отличный пример, не подумал даже в тот момент об этом)
Единственное что хочется уточнить: чтобы не возникало таких ситуаций - нужно всё таки нормальное распределение или рандом с использованием криптостойкой функции, чтоб значения были как можно более случайны? (Я уже запутался немного просто)

 

[7make]

@Lord_Alfred
Да, тот топик.

По простому, не заморачивайся с рандомом , юзай из каропки то что генерят ЯП (нормальное распределение)

 

[backoff]

 

[Lord_Alfred]

По простому, не заморачивайся с рандомом , юзай из каропки то что генерят ЯП (нормальное распределение)

Так вот как раз и хотелось разобраться - кубик Random и Spintax генерят согласно нормальному распределению или нет, пока что так и не понял до конца )
То что в других языках точно нормальное распределение (да и на самом C# скорее всего тоже) - я не сомневаюсь)

@backoff, гифка не вставилась. Но я сходил по ссылке и оценил ))

 

[7make]

@Lord_Alfred Да, нормальное распределение они генерят

 

[kveldulv]

Awesome templates & topic

I've worked getting a software pRNG approved for use in live internet casinos (kahnawake CA), so, maybe I can help.

Sample Size
5000 is not enough tests to be statistically significant. 1M - 10M is ideal.
Smaller samples are easily swayed by variance, eg with slot machines, testing is done in batches of 100k spins (see attached image attached)

- When generating & selecting some random values, if you want things to be uniform/equal, always ensure;
-All values are possible
-All values are equally likely

- Merseine Twister is a very good quality RNG and fine to use.
We (I) spent $ 20k on hardware, argued with developers for 6 months, and we shipped mt_rand.php and it worked fine.

- Don't do any DIY bullshit for seed values, feed one rng into another, or use something like RDRAND. Compare output of 1M tests, using seeds from MT or CryptoServiceProvider C#
-vs- Milliseconds and Tics.

RE: Testing RNG/PRNG's
https://en.wikipedia.org/wiki/Diehard_tests
http://webhome.phy.duke.edu/~rgb/General/dieharder.php


Par sheet for a video poker game, showing the confidence in the machine's return rate, based on number of game cycles.