реализовать случайный 0 1 с пользовательским параметром - PullRequest
Новая
       6

реализовать случайный 0 1 с пользовательским параметром

0 голосов
/ 18 октября 2018

Я пытаюсь решить следующую проблему:

У меня есть функция, которая генерирует 0 или 1 с равной вероятностью = 0.5 , и я хочу реализовать другую функцию, используя предыдущуюодна и основные математические манипуляции, которые делают то же самое, но с заданной вероятностью p ( 0 <= p <= 1 </em>)

Это не моя домашняя работа или что-то,Я просто наткнулся на это и был бы очень признателен за любые подсказки!

Ответы [ 2 ]

0 голосов
/ 18 октября 2018

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

, которое я реализовал здесь на Python. 

>>> # Create a function which returns 0 or 1 with equal probability.
>>> from random import random
>>> f = lambda: int(random()<0.5)

>>> # Check
>>> sum(f() for i in range(1000000))
500251
>>> # Use that to create a biased function. You can use this
>>> # either with a rational number expressed as numerator, denominator
>>> # or with a value of p between 0 and 1. Python doesn't care whether
>>> # numbers are integers but other languages might.
>>> def biased(numer, denom = 1):
...    while True:
...      numer += numer
...      if numer >= denom:
...        numer -= denom
...        if f(): return 1
...      else:
...        if f(): return 0
... 
>>> sum(biased(0,19) for i in range(1900000))
0
>>> sum(biased(1,19) for i in range(1900000))
100096
>>> sum(biased(5,19) for i in range(1900000))
500255
>>> sum(biased(18,19) for i in range(1900000))
1799988
>>> sum(biased(19,19) for i in range(1900000))
1900000

По сути, цикл создает двоичное представление числителя / знаменателя одинпоочередно, удваивая текущее значение числителя и сравнивая со знаменателем.Затем он сравнивает это с лениво сгенерированной случайной двоичной дробью, пока не может определить, является ли случайная дробь большей или меньшей.

Хотя число вызовов базовой функции f теоретически не ограничено, ожидаемое числоtimes biased вызывает f, равное 2, независимо от аргументов смещения.(Это потому, что вероятность того, что случайный поток битов будет соответствовать k двоичным цифрам, составляет 2 -k независимо от фактических значений двоичных цифр.)

0 голосов
/ 18 октября 2018

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

  1. Интерпретировать p как рациональное число a / b в нижнемтермины.Если p - это просто число с плавающей запятой в диапазоне от 0 до 1, то b - это просто степень 10 со стольким количеством нулей, сколько мест после десятичной дроби, и a - это число, образованное путем взятия строки цифр после десятичной дроби и исключения начальных нулей.
  2. Создание случайной строки битов длиной потолок (log (b - 1)) где основаниелогарифм равен 2, а потолок округляет любое нецелое число до следующего целого числа.Сделайте это, вызвав предоставленную функцию и записав ответы.
  3. Если случайная битовая строка, исключая начальные нули, представляет целое число от 0 до b - 1 включительно, затем продолжите;в противном случае, если число больше b , вернитесь к шагу 2, генерируя случайные битовые строки до тех пор, пока не получите работающую.
  4. Если случайная битовая строка, исключая начальные нули, представляетцелое число от 0 до a - 1 включительно, затем возвращается 0;в противном случае верните 1.

Это должно вернуть конечное ожидаемое время, но неограниченное время наихудшего случая, число 0 с вероятностью p = a / b и число 1 с вероятностью p = (b - a) / b , в точности, учитывая, что p - рациональное число (обратите внимание, что все числа типа double являются рациональными, как описано в шаге 1).

...