Получение равномерного распределения вероятности с ограниченными средствами

Question

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

В общем случае у вас есть функция Random (0,1), которая возвращает 0 с вероятностью .5 и 1 с вероятностью .5. Используя эту функцию, сделайте Random (a, b), который с равной вероятностью возвращает любое целое число в диапазоне [a, b].

Любые идеи?

Answer 1

Легче создать случайный (0,3) случайный (0, 1). Случайный (0, 3) можно моделировать двумя последовательными монетами для генерации четырех ведер: 00, 01, 10, 11.

В общем, Random (0, 2^n-1) тривиально легко порождает заданное Случайный (0, 1) [т.е. справедливая монета]. Любое другое Случайное (0, n) будет сложно сгенерировать, а не по-настоящему «случайным», потому что вам придется заранее определить количество результатов, которые вы хотите считать принадлежащими «другим» ведрам.

Вы могли почти поддельной Random (0,2), как это (Ruby, как и псевдокод):

options = ['h', 't', 'n']  # heads, tails, neither 
hash = {'h' => 0, 't' => 0, 'n' => 0} # number of 'heads', 'tails', 'neither' 
rand = options[random(0, 1)] 
rand = 'n' if (hash[rand] % 3 == 2) # every third 'h' or 't' is an 'n' 
hash[rand] ++ # update buckets 

Опять же, это не 'случайный', так как каждый третий голову или хвост считается " ни».

ОБНОВЛЕНИЕ: см. Соответствующий вопрос для более элегантного ответа. Creating a random number generator from a coin toss