Учитывая монету с неизвестным смещением , как я могу генерировать переменные - настолько эффективно, насколько это возможно - которые распределены Бернулли с вероятностью 0,5? То есть, используя минимальное количество сальто на сгенерированный вариант.
random-generation
Нил Г
источник
источник
Ответы:
Это хорошо известная проблема с несколькими хорошими решениями, которые обсуждались здесь и в stackoverflow (кажется, что я не могу опубликовать более одной ссылки, но быстрый поиск в Google дает вам несколько интересных записей). Посмотрите на запись в Википедии
http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin
источник
Это классическая проблема, я считаю, изначально приписанная фон Нейману. Одно из решений состоит в том, чтобы подбрасывать монету парами до тех пор, пока пары не станут разными, а затем отложить до результата первой монеты в паре.
позвольте быть результатом броска , где является первой монетой, а является второй монетой. Каждая монета имеет вероятность голов. Тогда из-за симметрии, из которой следует . Чтобы ясно увидеть эту симметрию, обратите внимание, что подразумевает, что результаты - или , оба из которых одинаково вероятны из-за независимости.(Xi,Yi) i Xi Yi p P(Xi=H|Xi≠Yi)=P(Xi=T|Xi≠Yi) P(Xi=H|Xi≠Yi)=1/2 ( Н , Т ) ( Т , Н )Xi≠Yi (H,T) (T,H)
Эмпирически время ожидания такой неравной пары
который взрывается, когда становится ближе к 0 или 1 (что имеет смысл).p
источник
Я не уверен, как эффективно суммировать термины, но мы можем остановиться, когда общее число бросков и общее количество успехов таковы, что даже, поскольку мы можем разделить разные порядки, которые мы могли бы достичь и в две группы с равной вероятностью, каждая из которых соответствует разным выводимым меткам. Мы должны быть осторожны, что мы еще не остановились на этих элементах, то есть на том, что ни у одного элемента нет префикса длины с такими успехами , что является четным. Я не уверен, как превратить это в ожидаемое количество сальто.t ( nn t (nt) n t n′ t′ (n′t′)
Проиллюстрировать:
Мы можем остановиться на TH или HT, поскольку они имеют равную вероятность. Двигаясь вниз по треугольнику Паскаля, следующие четные члены находятся в четвертом ряду: 4, 6, 4. Это означает, что мы можем остановиться после бросков, если выпала одна голова, так как мы можем создать двойственное соответствие: HHHT с HHTH и технически HTHH с THHH хотя мы бы уже остановились на тех. Точно так же выдает соответствующий HHTT с TTHH (остальное мы бы уже остановили, прежде чем дойти до них).(42)
Для все последовательности остановили префиксы. Это становится немного интереснее в где мы сопоставляем FFFFTTFT с FFFFTTTF.(52) (83)
Для после 8 бросков вероятность не остановиться составляет с ожидаемым количеством бросков, если мы остановились на . Для решения, в котором мы продолжаем катить пары, пока они не различаются, вероятность того, что вы не остановитесь, равна с ожидаемым числом бросков, если мы остановились на 4. По рекурсии - верхняя граница ожидаемых бросков для представленного алгоритма это .p=12 1128 5316 116 128127⋅5316=424127<4
Я написал программу на Python для вывода точек остановки:
печатает:
источник