Случайное число в диапазоне с равной вероятностью

Это может быть больше, чем Math, чем С#, но мне нужно решение С#, поэтому я помещаю его здесь.

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

Я знаю, что существует метод Random.Next(int, int), который возвращает число между первым целым и последним (с последним исключением).

Random.Next() [без перегрузок] вернет значение от 0 до Int32.MaxValue(которое равно 2147483647) - 1, поэтому 2147483646.

Если мне нужно значение от 1 до 10, я мог бы вызвать Random.Next(1, 11), чтобы сделать это, однако имеет ли значение от 1 до 10 вероятность равной вероятности?

Например, диапазон равен 10, поэтому 2147483646 не делится на 10, поэтому значения 1-6 имеют чуть более высокую вероятность возникновения (потому что 2147483646 % 10 = 6). Это, конечно, предполагает, что каждое значение внутри Random.Next() [без перегрузок] с равной вероятностью возвращает значение от 0 до 2147483646.

Как можно гарантировать, что каждое число в пределах диапазона имеет равную вероятность возникновения? Скажем, для системы типа лотереи, где для некоторых людей было бы несправедливо иметь более высокую вероятность, чем другие, я не говорю, что использовал бы С#, встроенный в RNG для этого, я просто использовал его в качестве примера.

Ответ 1

Я отмечаю, что никто на самом деле не ответил на мясистый вопрос в вашем посте:

Например, диапазон равен 10, поэтому 2147483646 не делится на 10, поэтому значения 1-6 имеют несколько более высокую вероятность возникновения (потому что 2147483646% 10 = 6). Это, конечно, предполагает, что каждое значение в Random.Next() [без перегрузок] с равной вероятностью возвращает значение от 0 до 2147483646.

Как можно гарантировать, что каждое число в пределах диапазона имеет равную вероятность возникновения?

Правильно, поэтому вы просто выбрасываете значения, которые вызывают дисбаланс. Например, скажем, что у вас был RNG, который мог бы обеспечить равномерное распределение по { 0, 1, 2, 3, 4 }, и вы хотели использовать его для создания равномерного распределения по { 0, 1 }. Наивная реализация: draw from {0, 1, 2, 3, 4}, а затем возвращает значение % 2; это, однако, очевидно, приведет к смещенному образцу. Это происходит потому, что, как вы заметили, 5 (количество элементов) не равномерно делится на 2. Итак, вместо этого выкиньте любые ничьи, которые производят значение 4. Таким образом, алгоритм будет

 draw from { 0, 1, 2, 3, 4 }
 if the value is 4, throw it out
 otherwise, return the value % 2

Вы можете использовать эту основную идею для решения общей проблемы.

однако имеет ли каждая ценность от 1 до 10 вероятность равной вероятности?

Да, да. Из MSDN:

Псевдослучайные числа с равной вероятностью выбираются с конечным набором чисел.

Изменить: По-видимому, документация НЕ соответствует текущей реализации .NET. В документации указано, что ничья одинаковы, но код предполагает, что это не так. Однако это НЕ отрицает тот факт, что это разрешимая проблема, и мой подход - это один из способов ее решения.

Ответ 2

С#, построенный в RNG, является, как вы ожидаете, равномерно распределенным. Каждое число имеет равную вероятность возникновения, учитывая диапазон, который вы указываете для Next(min, max).

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

Также обратите внимание, что каждое число с равным правдоподобием не означает, что каждое число будет происходить столько же раз. Если вы смотрите на случайные числа от 1 до 10, то в 100 итераций, это не будет равномерное распределение в 10 раз для каждого числа. Некоторые цифры могут появляться 8 раз, а другие - 12 или 13 раз. Однако, с большим количеством итераций, это имеет тенденцию немного выровняться.

Кроме того, поскольку он упоминается в комментариях, я добавлю: если вы хотите что-то более сильное, найдите криптографические PRNG. Mersenne Twister особенно хорош в том, что я видел (быстрый, дешевый для вычисления, огромный период), и он имеет версии с открытым исходным кодом на С#.

Ответ 3

Программа тестирования:

var a = new int[10];
var r = new Random();
for (int i = 0; i < 1000000; i++) a[r.Next(1, 11) - 1]++;
for (int i = 0; i < a.Length; i++) Console.WriteLine("{0,2}{1,10}", i + 1, a[i]);

Вывод:

 1      99924
 2     100199
 3     100568
 4     100406
 5     100114
 6      99418
 7      99759
 8      99573
 9     100121
10      99918

Вывод:

Каждое значение возвращается с равной вероятностью.

Ответ 4

Пепла и dtb неверны: вы правы, чтобы подозревать, что некоторые числа будут иметь больше шансов, чем другие.

Когда вы вызываете .Next(x, y), существуют y - x возможные возвращаемые значения. Класс .NET 4.0 Random вычисляет возвращаемое значение на основе возвращаемого значения NextDouble() (это немного упрощенное описание).

Очевидно, что множество возможных двойных значений является конечным и, как вы заметили, оно не может быть кратным размеру набора возможных возвращаемых значений .Next(x, y). Поэтому, предполагая, что набор входных значений равномерно распределен, некоторые выходные значения будут иметь немного большую вероятность возникновения.

Я не знаю, как много числовых двойных значений (т.е. исключая бесконечность и значения NaN), но оно, конечно, больше, чем 2 ^ 32. В вашем случае, если мы примем значения 2 ^ 32, для аргумента, то нам нужно отобразить 4294967296 входов на 10 выходов. Некоторые значения имели бы большую вероятность возникновения, или 0.00000023283064397913028110629 процентов больше. Фактически, поскольку число входных состояний больше 2 ^ 32, разница в вероятности будет еще меньше.