Может кто-нибудь сказать мне, как смоделировать , где , используя подбрасывание монеты (столько раз, сколько вам нужно) с ?
Я думал об использовании выборки отклонения, но не мог прибить это.
Может кто-нибудь сказать мне, как смоделировать , где , используя подбрасывание монеты (столько раз, сколько вам нужно) с ?
Я думал об использовании выборки отклонения, но не мог прибить это.
[self-study]
тег и прочитайте его вики . Обратите внимание, что нет необходимости ставить просьбу о помощи в конце вашего вопроса - мы знаем, что все, кто публикует здесь, надеются на помощь!Ответы:
Поскольку существует бесчисленное множество решений, давайте найдем эффективное .
Идея, лежащая в основе этого, начинается со стандартного способа реализации переменной Бернулли: сравнить равномерную случайную переменную с параметром a / b . Когда U < a / b , вернуть 1 ; в противном случае верните 0 .U a/b U<a/b 1 0
Мы можем использовать монету как генератор случайных чиселp . Чтобы сгенерировать число равномерно в любом интервале [ x , y ) , подбросьте монету. Когда это головы, рекурсивно генерировать равномерное значение X в первой части p интервала; когда это хвосты, рекурсивно генерировать X из последних 1 - рU [x,y) X p X 1−p часть интервала. В какой-то момент целевой интервал станет настолько маленьким, что на самом деле не имеет значения, как вы выбираете из него число: именно так начинается рекурсия. Очевидно, что эта процедура генерирует однородные переменные (с любой желаемой точностью), что легко подтверждается индукцией.
Эта идея неэффективна, но приводит к эффективному методу. Поскольку на каждом этапе вы собираетесь рисовать число из некоторого заданного интервала , почему бы сначала не проверить, нужно ли вообще его рисовать? Если целевое значение лежит за пределами этого интервала, вы уже знаете результат сравнения между случайным значением и целью. Таким образом, этот алгоритм имеет тенденцию быстро завершаться. (Это может быть истолковано как процедура отбора проб , указанная в вопросе.)[x,y)
Мы можем оптимизировать этот алгоритм дальше. На любом этапе у нас на самом деле есть две монеты, которые мы можем использовать: перемаркировав нашу монету, мы можем превратить ее в монету с вероятностью . Следовательно, в качестве предварительного вычисления мы можем рекурсивно выбрать тот, который приведет к перемаркировке, что приведет к меньшему ожидаемому числу бросков, необходимых для завершения. (Этот расчет может быть дорогим шагом.)1−p
Например, неэффективно использовать монету с для прямой эмуляции переменной Бернулли ( 0,01 ) : в среднем это занимает почти десять бросков. Но если мы используем монету с p = 1 - 0.0 = 0.1 , то всего за два броска мы обязательно это сделаем, и ожидаемое количество бросков будет всего 1.2 .p=0.9 (0.01) p=1−0.0=0.1 1.2
Вот подробности.
Разбиение любого заданного полуоткрытого интервала на интервалыI=[x,y)
Это определяет два преобразования и s ( ∗ , T ), которые действуют на полуоткрытых интервалах.s(∗,H) s(∗,T)
С точки зрения терминологии, если - любое множество действительных чисел, пусть выражениеI
означает , что является нижней границей для I : т < х для всех х ∈ I . Аналогичным образом , т > I означает , что т является верхней границей для ввода .t I t<x x∈I t>I t I
Напишите . (Фактически, это не будет иметь значения, если t будет действительным, а не рациональным; нам нужно только, чтобы 0 ≤ t ≤ 1. )a/b=t t 0≤t≤1
Вот алгоритм для получения переменной с желаемым параметром Бернулли:Z
Установите и I n = I 0 = [ 0 , 1 ) .n=0 In=I0=[0,1)
While {Бросить монету, чтобы получить X n + 1 . Установите I n + 1 = S ( I n , X n + 1 ) . Инкремент n .}(t∈In) Xn+1 In+1= S( ЯN, Xn + 1) . N
Если тогда установить Z = 1 . В противном случае установите Z = 0 .т > In + 1 Z= 1 Z= 0
Реализация
Чтобы проиллюстрировать это, здесь приведенаT [ х , у) [ 0 , 1 ) s
R
реализация алгоритма как функцииdraw
. Его аргументами являются целевое значение и интервал [ x , y ) , изначально [ 0 , 1 ) . Он использует вспомогательную функцию, реализующую s . Хотя это и не нужно, но также отслеживает количество брошенных монет. Он возвращает случайную величину, количество бросков и последний проверенный интервал.s
В качестве примера его использования и испытания его точности, возьмите случай и р = 0,9 . Обратим 10 , 000 значения , используя алгоритм, отчет о среднем (и ее стандартной ошибки), и указать среднее число перестроек используется.т = 1 / 100 р = 0,9 10 , 000
В этом моделировании сальто были головы. Несмотря на то, что показатель ниже 0,01 , Z-показатель - 0,5154 не является значимым: это отклонение можно объяснить случайностью. Среднее количество сальто составило 9,886 - чуть меньше десяти. Если бы мы использовали 1 - р монетку, средний было бы 0,0094 --still не значительно отличается от цели, но только 1,177 щелчки были бы необходимы в среднем.0,0095 0,01 - 0,5154 9.886 1−p 0.0094 1.177
источник
Вот решение (немного грязное, но это мой первый удар). Вы можете фактически игнорировать и без потери общности , предположим , Р ( Н ) = 1 / 2 . Почему? Существует умный алгоритм для генерации несмещенного подбрасывания монет из двух предвзятых подбрасываний монет. Таким образом , мы можем предположить , P ( H ) = 1 / 2 .P(H)=p P(H)=1/2 P(H)=1/2
Для того, чтобы сгенерировать я могу придумать два решения (первое не мое, а второе обобщение):Bernoulli(ab)
Решение 1
Переверните несмещенную монету раз. Если а голова нет, начните заново. Если через головку может присутствовать, возвратом первой монетой является ли головами или нет (потому что Р ( первая монета головы | а головы в б монетах ) =b a a )P(first coin is heads | a heads in b coins)=ab
Решение 2
Это может быть распространено на любое значение . Напишите p в двоичной форме. Например, 0,1 = 0,0001100110011001100110011 ... основание 2Bernoulli(p) p 0.1=0.0001100110011001100110011...base 2
Мы создадим новое двоичное число, используя броски монет. Начните с и добавьте цифры в зависимости от того, появляются ли головы (1) или хвосты (0). При каждом броске сравнивайте новое двоичное число с двоичным представлением p до той же цифры . В конце концов они будут расходиться и возвращаться, если b i n ( p ) больше вашего двоичного числа.0. p bin(p)
В Python:
Некоторые доказательства:
около 0,4 (не быстро, однако)
источник
Я вижу простое решение, но, без сомнения, есть много способов сделать это, некоторые предположительно проще, чем этот. Этот подход можно разбить на два этапа:
(Здесь нужно сделать некоторые вычисления, чтобы показать это, но вы можете довольно легко вывести вероятности, работая с рекуррентными соотношениями ... или вы можете сделать это, суммируя бесконечные ряды ... или есть другие способы.)
источник