Учитывая монету с неизвестным уклоном, эффективно генерировать отличия от справедливой монеты

10

Учитывая монету с неизвестным смещением , как я могу генерировать переменные - настолько эффективно, насколько это возможно - которые распределены Бернулли с вероятностью 0,5? То есть, используя минимальное количество сальто на сгенерированный вариант.p

Нил Г
источник
3
Простое решение состоит в том, чтобы перевернуть монету два раза: если это сопоставьте ее с головами, если это сопоставьте ее с хвостами. В противном случае повторите эксперимент, пока не будет достигнут один из этих двух. HTTH
кардинал
1
@ Cardinal: Отлично! Почему бы не добавить ответ?
Нил Дж
2
@Glen_b: Хорошо, но вы можете сделать это с минимальным количеством сальто на сгенерированный вариант?
Нил Г
3
@MichaelLugo: Я бы сказал, что это определенно зависит от . :-) Если мы знаем, что можем сделать это одним щелчком. Если мы знаем, что можем сделать это в два раза, и мы знаем, что это оптимально в обоих случаях. Ответ должен быть связан с энтропией . Если мы ничего не знаем о кроме этого , то я подозреваю, что простой результат теории игр даст что-то близкое к схеме в моем первом комментарии как «оптимальной» соответствующим образом. pp=1/2p=1/4р р ( 0 , 1 )H(p)pp(0,1)
кардинал
4
Здравствуйте, Giorgio1927, и добро пожаловать на сайт! Пожалуйста, добавьте тег «самообучения» к этому вопросу, поскольку он позволяет людям понять, что они должны направлять вас к ответу, а не просто давать его.
jbowman

Ответы:

6

Это хорошо известная проблема с несколькими хорошими решениями, которые обсуждались здесь и в stackoverflow (кажется, что я не могу опубликовать более одной ссылки, но быстрый поиск в Google дает вам несколько интересных записей). Посмотрите на запись в Википедии

http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin

Карлос Фуэнтес
источник
Извините, я изменил вопрос так, чтобы он не был так легко в Google ...
Нил Дж
Если вы хотите ответить на вопрос, обратите внимание, что этот ответ не является оптимальным для моего отредактированного вопроса.
Нил Г
3

Это классическая проблема, я считаю, изначально приписанная фон Нейману. Одно из решений состоит в том, чтобы подбрасывать монету парами до тех пор, пока пары не станут разными, а затем отложить до результата первой монеты в паре.

позвольте быть результатом броска , где является первой монетой, а является второй монетой. Каждая монета имеет вероятность голов. Тогда из-за симметрии, из которой следует . Чтобы ясно увидеть эту симметрию, обратите внимание, что подразумевает, что результаты - или , оба из которых одинаково вероятны из-за независимости.(Xi,Yi)iXiYipP(Xi=H|XiYi)=P(Xi=T|XiYi)P(Xi=H|XiYi)=1/2 ( Н , Т ) ( Т , Н )XiYi(H,T)(T,H)

Эмпирически время ожидания такой неравной пары

1/P(XY)=11p2(1p)2=12p(1p),

который взрывается, когда становится ближе к 0 или 1 (что имеет смысл).p

Алекс Р.
источник
2

Я не уверен, как эффективно суммировать термины, но мы можем остановиться, когда общее число бросков и общее количество успехов таковы, что даже, поскольку мы можем разделить разные порядки, которые мы могли бы достичь и в две группы с равной вероятностью, каждая из которых соответствует разным выводимым меткам. Мы должны быть осторожны, что мы еще не остановились на этих элементах, то есть на том, что ни у одного элемента нет префикса длины с такими успехами , что является четным. Я не уверен, как превратить это в ожидаемое количество сальто.t ( nnt(nt)ntnt(nt)

Проиллюстрировать:

Мы можем остановиться на TH или HT, поскольку они имеют равную вероятность. Двигаясь вниз по треугольнику Паскаля, следующие четные члены находятся в четвертом ряду: 4, 6, 4. Это означает, что мы можем остановиться после бросков, если выпала одна голова, так как мы можем создать двойственное соответствие: HHHT с HHTH и технически HTHH с THHH хотя мы бы уже остановились на тех. Точно так же выдает соответствующий HHTT с TTHH (остальное мы бы уже остановили, прежде чем дойти до них).(42)

Для все последовательности остановили префиксы. Это становится немного интереснее в где мы сопоставляем FFFFTTFT с FFFFTTTF.(52)(83)

Для после 8 бросков вероятность не остановиться составляет с ожидаемым количеством бросков, если мы остановились на . Для решения, в котором мы продолжаем катить пары, пока они не различаются, вероятность того, что вы не остановитесь, равна с ожидаемым числом бросков, если мы остановились на 4. По рекурсии - верхняя граница ожидаемых бросков для представленного алгоритма это . p=12112853161161281275316=424127<4

Я написал программу на Python для вывода точек остановки:

import scipy.misc
from collections import defaultdict


bins = defaultdict(list)


def go(depth, seq=[], k=0):
    n = len(seq)
    if scipy.misc.comb(n, k, True) % 2 == 0:
        bins[(n,k)].append("".join("T" if x else "F"
                                   for x in seq))
        return
    if n < depth:
        for i in range(2):
            seq.append(i)
            go(depth, seq, k+i)
            seq.pop()

go(8)

for key, value in sorted(bins.items()):
    for i, v in enumerate(value):
        print(v, "->", "F" if i < len(value) // 2 else "T")
    print()

печатает:

FT -> F
TF -> T

FFFT -> F
FFTF -> T

FFTT -> F
TTFF -> T

TTFT -> F
TTTF -> T

FFFFFT -> F
FFFFTF -> T

TTTTFT -> F
TTTTTF -> T

FFFFFFFT -> F
FFFFFFTF -> T

FFFFFFTT -> F
FFFFTTFF -> T

FFFFTTFT -> F
FFFFTTTF -> T

FFFFTTTT -> F
TTTTFFFF -> T

TTTTFFFT -> F
TTTTFFTF -> T

TTTTFFTT -> F
TTTTTTFF -> T

TTTTTTFT -> F
TTTTTTTF -> T
Нил Г
источник
Когда неизвестно, любое решение должно работать для ограничения значений и . Это должно прояснить, что решение @ Cardinal является оптимальным. Ожидаемое количество сальто (с учетом неизвестного , конечно) составляет .pp0p1p2/((p(1p))
whuber
@whuber: я не понимаю, почему это должно быть оптимальным. Мое решение останавливается во всех тех же случаях, что и его. Тем не менее, он будет продолжать катиться, например, после ththh, тогда как можно остановиться.
Нил Г
Каково ваше решение? Я не вижу описанного здесь. Я думаю, что у нас могут быть разные концепции решения @ Cardinal. Я понимаю, что это означает «остановка всякий раз, когда число голов равно количеству хвостов, и сопоставьте это со значением первого результата в последовательности».
whuber
@whuber: Вы имеете в виду следующее: «Простое решение состоит в том, чтобы перевернуть монету два раза: если это HT, сопоставьте ее с головами, если это TH, сопоставьте ее с хвостами. В противном случае повторяйте эксперимент, пока не будет достигнут один из этих двух». Это не остановит HHTT. Он ждет пары HT или TH по четному индексу.
Нил Г
Мое решение состоит в том, чтобы найти двудольное совпадение равновероятных префиксов (ни один из которых не является префиксом другого) и связать каждую половину совпадения с головами или хвостами.
Нил Г