Здравствуйте!

Предположим, есть лотерея "m из n", т.е. в каждый тираж попадает m из n равновозможных номеров.
Интересует вопрос - возможно ли каждый тираж представлять в виде очередного случайного числа, с тем чтобы получить _равномерное распределение_ в интервале возможных значений?
Первое, что пришло в голову, использовать сумму всех номеров тиража, но, оказалось, сумма не даст равномерного распределения (а некое подобие распределения Симпсона)... Вторая мысль (после гугления) - получать последовательность из m бит по принципу "четный номер - 0, нечетный - 1", но тут возникают некоторые неудобства (если m < 8, если n нечетно).
Может есть более правильный способ агрегирования m случайных величин тиража в одну величину?

982183Цель?
Разрабатывается свой ГСЧ (вихрь Мерсенна), не мною, моя задача - проверить качество. Предварительно определились с тестами - это TestU01 и NIST Statistical Test Suite . Но оказалось что, например, достаточно хороший (но по ряду причин не подходящий для нашей задачи) дотнетовский ГСЧ (Random) не идеально проходит эти тесты.
Современная лотерея, несомненно, очень хороший источник случайных значений. К тому же, доступны приличные массивы тиражей, например, у итальянской пятиминутной "10 e Lotto ogni 5 minuti" с 2010 года накопилось около 0.7 млн, т.е., вполне достаточное количество, чтобы прогнать эти тесты и понять насколько они "серьезны". Это главная цель. Помимо этого, "очень хороший источник случайных чисел" в нашей задаче так или иначе пригодится (как образец для сравнения, или, например, "засевать" вихрь Мерсенна).

AkinaСоколинский БорисЕсли точно знаешь вид распределения, его можно свести к равномерному.Для суммы выигравших номеров распределение известно - ступенчатый треугольник.
Ага, спасибо за идею.

Соколинский БорисТогда нет проблем.
Подставляем в функцию распределения случайный аргумент и получаем U[0,1].
Наверное, в обратную функцию?

Соколинский Борис,

А, ну конечно, спасибо! Будем искать математика, пусть "нарисует" нам "ступенчатый треугольник")
Всем спасибо за помощь!

Соколинский БорисВ общем случае будет смесь полиномов порядка (n-1). А поскольку в лотерее выбор без повторений, получится еще более сложная форма.
Да, очевидно, что числа тиража "не-независимые" величины...

982183,

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

kealon(Ruslan)вихрь Мерсенна засевается одним числом, насколько мне известно, зачем для него такие объёмы?

стандартный рекурентный генератор, конечно для серьёзных задач не пойдёт, но и вихрь Мерсенна не криптостойкий.
что делаете то?
Не, вроде 624 для изначального алгоритма или более для последующих модификаций (для нашей, кажется 4096, не я делаю, могу ошибиться).
Делаем моделирование для страхового бизнеса, там без быстрого и качественного ГСЧ никак (расчетную часть реализуем в OpenCL).

kealon(Ruslan)с задачей понятно, обычный ММК короче, тогда RANECU хватит за глаза, если уж для церна хватает :-)
Откуда такая уверенность? Занимались моделированием страхования? Проганяли RANECU по каким-либо тестам? Если это этот церн то о каких количествах частиц идет речь? (Спросил напарника о RANECU, давно занимается этим, он лишь отмахнулся)

kealon(Ruslan)он просто как и вы не в теме, вот книжку почитает и будет готов к делам
Да, тема для меня новая, за книжку спасибо)

генератор шума,

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

982183LRЕсть конечно, вот и новый интеловский DRNG хвалят... некоторые, а некоторые ругают... )

Это вроде программное, а не аппаратное решение.
Ну х.з., вроде аппаратное
2.5 Introducing the Digital Random Number Generator (DRNG)Unlike software approaches, it includes a high-quality entropy source implementation that can be sampled quickly to repeatedly seed the CSPRNG with high-quality entropy. Furthermore, it represents a self-contained hardware module that is isolated from software attacks on its internal state. The result is a solution that achieves RNG objectives with considerable robustness: statistical quality (independence, uniform distribution), highly unpredictable random number sequences, high performance, and protection against attack.

982183У меня нет доступа к холодильнику, но есть доступ к гардеробу.
Могу ли я в гардеробе поесть......
Могу, если найду в чьем-либо кармане бутерброд или конфетку)

982183,

нет, лучше сначала обшарить карманы, если ничего не найдется - тогда уж тешить себя надеждой на скорый доступ к холодильнику))

982183,

Дай миллион! или Где взять истинно случайные числа?

кажется, нашел холодильник - https://www.random.org/bytes/ - оказался с мелкими карманами по 16,384))) попробую угоститься!

kealon(Ruslan)Я моделировал прохождение нейтронов и прочей мелкой нечисти, расчёты неделями идут - я не думаю что у вас особо больше
Расчеты у заказчика на старом софте тоже неделями идут, сейчас 10-100млн., но в новом (разрабатываемом) софте расчеты производятся на GPU (OpenCL), пробный/примерный расчет на тех же количествах занял меньше минуты (nvidia 1080) - поэтому количества могут существенно вырасти, заказчик захочет считать больше (конечно, не выскочит за 2^60 ~ 10^18, но чем больше количество, тем больше шансов проявиться "дефектам" генератора). У напарника есть опыт моделирования процессов в аэродинамической трубе, и на тех количествах он наблюдал "дефекты" различных генераторов воочию. Еще он сказал, что "вихрь" хорош и тем, что у него нет начального периода "раскачки" (первая порция "плохих" значений, как у некоторых других, как в самогонном аппарате).

BarloneМожно, в виде одного случайного числа из диапазона n!/(n-m)!
Диапазон не важен, нетрудно привести к нужному, но важно "как получить это одно случайное число (из m в тираже)?"

Впрочем, уже нашел альтернативный источник , надеюсь не хуже чем лотерея: "The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs". Не знаю, как они транслируют атмосферный шум в случайную последовательность бит, но, в конце концов, и в лототроне ведь тоже может оказаться какой-нибудь дефект (подшипник выработался с одной стороны и т.п.).

kealon(Ruslan),

Понятно, спасибо за разъяснения! Вряд ли я серьезно буду заниматься разработкой генератора (это парафия достаточно сведущего в этих делах напарника). Но "быть в курсе" конечно важно. Мое дело в этом проекте на сегодняшний день - оттестировать качество генератора (подобрать тесты, аккуратно прогнать, сравнить результаты, попытаться сделать правильные выводы и т.д.), вот примерно такая работа - Part 4 Random Tests