использовать rand1 для реализации randx

Question

У вас есть int rand1(), который выдает 0 или 1 с равной вероятностью.

Вам необходимо реализовать int randx(int x), который выдает 0,1,2,3,4, ..., x, каждое значение должно иметь равную вероятность.

Легко установить биты на основе вывода rand1 для таких функций, как rand3 или rand7. Для rand3 просто позвоните rand1 дважды и установите бит 0 и 1 на основе вывода, а 00,01,10,11 будут иметь равную вероятность получить выбор (25%). Но как насчет таких функций, как rand4?

Answer 1

В этой задаче вам нужно будет сохранить несколько фиктивных выходов (выбор отбраковки, как указано в @Gene), на котором вы повторяете выполненный эксперимент.

Здесь я представил две реализации. первый является субоптимальным, но его легче понять. второй более оптимальный, но немного сложнее. Наконец, я пробовал набросал доказательство и связался с ответом Math StackExchange.

---

Первый подход -

Шаг 1 - Запуск rand1()x + 1 раз.

Шаг 2 - Проверьте, что выход разогревается. По одной горячей я имею в виду, только 1 из x + 1 работает в 1 и всех остальных 0. Если это не так, повторите шаг 1. Остальное перейдите к этапу 3.

Шаг 3 - Индекс печати 1 как ваш выход.

код питона будет выглядеть следующим образом -

def randx(x): 
    choice = -1 
    while choice == -1: 
     for i in range(0, x+1): 
      c = rand1() 
      if c == 1 and choice == -1: 
       choice = i 
      elif c == 1 and choice != -1: 
       choice = -1 
       break 

---

Второй подход -

Конечно, первый способ является неоптимальным. Вы можете сделать это намного лучше, но для этого потребуется намного больше кода. Предположим, мы хотим сделать прогноз между значениями x+1 (0 - x). Вам нужно будет провести эксперимент по крайней мере k = ceil(log(x+1)) раз. Теперь каждый из результатов будет иметь равную вероятность 1/2^k.

Из этих 2^k возможностей присвоить номера номерам (из-за нашего выбора k вы увидите, что вы можете присвоить номер, по крайней мере, половину возможностей). Позвоните другим возможностям манекен выход.

Когда вы получаете вывод dummy, вы просто повторяете эксперимент. Если вы этого не сделаете, вы выводите число, соответствующее этому результату.

В качестве примера, если x = 4, x + 1 = 5. Следовательно, нам нужно k = 3. Назначьте 0, 1, 2, 3, 4 свои двоичные представления (от 000 до 101) и оставьте оставшиеся 3 в качестве соски.Псевдо-код будет выглядеть следующим образом,

function randx(x): 
    choice = -1 
    runs = ceil(log(x+1)) 
    while choice == -1: 
     output = 0 
     for i in range(0, runs): 
      output += pow(2, i)*rand1() 
     if output <= x: 
      choice = output 

---

Почему это работает?

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

Let p = 1/2^k 
Let q = 1 - (x+1)*p 
Total probability of getting i = p + q*p + q*q*p + q*q*q*p ... 
= p/(1-q) 
= 1/(x+1) 
Hence this sums up to 1/(x+1). 

Для более полного объяснения с MathJax см https://math.stackexchange.com/questions/2356/is-it-possible-to-split-coin-flipping-3-ways

Answer 2

Вы имеете право идею. Вам нужно будет генерировать двоичное число, большее, чем тот, который вам нужен, путем конкатенации случайных бит. Но тогда, если x+1 не имеет значения 2, вам необходимо использовать rejection sampling, чтобы гарантировать, что каждое значение будет возвращено randx с равной вероятностью. Чтобы вероятность вероятного отклонения мала, скажем, менее 2^-p, мощность 2, которую вы генерируете, должна иметь p+1 бит больше, чем необходимо. Метод отказа будет выглядеть следующим образом:

int rand(int x) { 
    choose b such that m = 2^b >= x+1 
    let r_max = m - m mod (x+1) 
    do { 
    r = base-2 number of r pseudo-random bits 
    } while (r > r_max) 
    return r mod (x+1) 
} 

Обратите внимание, что когда x+1 является степенью 2, цикл всегда выполняется ровно один раз. Когда это не так, вероятность каждой итерации зависит от b. Добавление 1 в b уменьшает вероятность другой итерации.