Генератор псевдослучайных чисел с небольшим смещением

Question

Я думал об этом некоторое время безрезультатно...

Как можно было бы создать генератор псевдослучайных чисел с небольшим (мы говорим только очевидным после миллионов, может быть, миллиардов итераций / тестов) смещением в сторону одного числа. Так, например, если наш генератор производит числа от 0,1,2,...,98,99 и мы хотим небольшое смещение для 47.

Я чувствую, что должно быть умное решение для теории чисел, но я не смог ничего найти. Любопытно посмотреть, что вы все думаете!

Answer 1

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

Если ваш поддиапазон имеет длину N, сгенерируйте значения в диапазоне 0..K*N+1 (не включая правую границу). Если результат R меньше чем K*N, выход R mod N, иначе выведите предпочтительное значение.

В этом случае мы имеем вероятность для всех элементов p=K/(K*N+1) и для вероятности предпочтительного элемента q = p + delta = K/(K*N+1) + 1/(K*N+1) = (K+1)/(K*N+1),

Если у вас есть N и некоторые критерии смещения, вычислите K, чтобы получить значение смещения.

Если вам нужно больше точности, используйте случайный диапазон 0..K*N+F с соответствующими поправками формулы (этот подход дает любое необходимое рациональное значение смещения).

Answer 2

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

if(controlGeneator.generate01Float() < Eps) {
     return 42;
}
else {
    return mainGenerator.generateNextInRange()
}

Приятно то, что это работает, даже если целевой диапазон действительно весь 32-битный диапазон или что-то еще. Также, изменив Eps Вы можете контролировать уклон.

Очевидным недостатком является то, что для того, чтобы это работало действительно хорошо, controlGeneator а также mainGenerator Лучше быть абсолютно независимым, что довольно сложно. Одной из идей может быть использование разных семян (например, seed а также seed + 1), чтобы инициализировать их, а затем использовать разные циклы, например, при каждом вызове фактически извлечь 2 случайных числа из controlGeneator и 3 из mainGenerator вместо пропорции 1:1,

PS IANAL, но мошенничество в игре на удачу может быть незаконным.

Answer 3

Линейный конгруэнтный генератор является наиболее распространенным и старейшим алгоритмом генерации псевдослучайного числа, вы должны знать рекуррентное соотношение

Xn+1 = (aXn + c) mod c
where X is the sequence of pseudo-random values
m, 0< m- modulus 
a, 0< a <m- multiplier
c, 0< = c<m- increment
x0, 0<=x0<m- the seed or start value

    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h> 
    int main()
    {
       srand(time(NULL));
       int i;
       for(i = 0; i<5; i++)
      printf("%d\t", rand()%10);
    }