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

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

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

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


random math generator number-theory
person T. Fo    schedule 17.01.2018    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

Если ваш поддиапазон имеет длину 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 с соответствующими корректировками формулы (этот подход дает любое необходимое рациональное значение смещения).

person MBo    schedule 17.01.2018

arrow_upward
0
arrow_downward

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

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

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

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

P.S. IANAL, но мошенничество в азартной игре может быть незаконным.

person SergGr    schedule 17.01.2018