Головоломка C: сделать честную монету из необъективной монеты

Это классическая вероятностная головоломка, и, насколько мне известно, вы не можете решить ее всего двумя вызовами функции. Однако вы можете сделать это с небольшим ожидаемым числом вызовов функции.

Наблюдение состоит в том, что если у вас есть смещенная монета, которая выпадает орлом с вероятностью p, и если вы подбрасываете монету дважды, то:

• Вероятность того, что решка выпадет дважды, равна p².
• Вероятность того, что сначала выпадет орёл, а потом решка, равна p(1-p).
• Вероятность того, что сначала выпадет решка, а затем решка, равна (1-p)p.
• Вероятность того, что дважды выпадет решка, равна (1-p)².

Теперь предположим, что вы несколько раз подбрасываете две монеты, пока они не получат разное значение. Если это произойдет, какова вероятность того, что первая монета выпадет орлом? Ну, если мы применим закон Байеса, мы получим, что

P(первая монета решка | обе монеты разные) = P(обе монеты разные | первая монета решка) P(первая монета решка) / P(обе монеты разные)

Вероятность того, что первая монета выпадет орлом, равна p, так как при любом подбрасывании монеты выпадет орел с вероятностью p. Вероятность того, что обе монеты различны при условии, что первая монета выпадет решкой, равна вероятности того, что вторая монета выпадет решкой, которая равна (1 - p). Наконец, вероятность того, что обе монеты различны, равна 2p(1-p), поскольку, если вы посмотрите на приведенную выше таблицу вероятностей, это может произойти двумя способами, каждый из которых имеет вероятность p(1-p). Упрощая, получаем, что

P(первая монета решка | обе монеты разные) = p (1-p) / (2p(1-p)) = 1/2.

Но какова вероятность того, что первая монета выпадет решкой, если монеты разные? Что ж, это то же самое, что и вероятность того, что первая монета не выпадет орлом, когда обе монеты разные, то есть 1 - 1/2 = 1/2.

Другими словами, если вы продолжаете подбрасывать две монеты до тех пор, пока они не получат разные значения, а затем берете значение первой подброшенной монеты, вы в конечном итоге получаете честную монету из необъективной монеты!

В C это может выглядеть так:

bool FairCoinFromBiasedCoin() {
    bool coin1, coin2;

    do {
        coin1 = function_A();
        coin2 = function_A();
    } while (coin1 == coin2);

    return coin1;
}

Это может показаться ужасно неэффективным, но на самом деле это не так уж и плохо. Вероятность того, что он завершится на каждой итерации, равна 2p(1 - p). При ожидании это означает, что нам нужно 1/(2p(1-p)) итераций, прежде чем этот цикл завершится. Для p = 40% это 1/(2 x 0,4 x 0,6) = 1/0,48 ~= 2,083 итерации. Каждая итерация подбрасывает две монеты, поэтому нам нужно, как ожидается, около 4,16 подбрасываний монеты, чтобы получить честный бросок.

Надеюсь это поможет!

Вот подход, который будет работать, но он требует повторных испытаний.

1. вероятность того, что function_A вернет 1: P(1) = p (например, p=60%)
2. вероятность того, что function_A вернет 0: P(0) = 1 - p
3. вероятность определенной последовательности возвращаемых значений a,b,... при последовательных вызовах function_A равна P(a)P(b)...

4. Обратите внимание, что определенные комбинации будут возникать с равными шансами, например:

         P(a)*P(b) === P(b)*P(a)
    P(a)*P(b)*P(c) === P(b)*P(c)*P(a)
   
    etc.
   

5. мы можем использовать этот факт при выборе только последовательностей (1,0) или (0,1), тогда мы знаем, что вероятность любого равна

       P(1)*P(0)/(P(1)*P(0) + P(0)*P(1)) 
    => x / (x + x)
    => 1 / 2
   

Это становится рецептом реализации function_B:

• вызывать function_A несколько раз, пока не получим последовательность (0,1) или (1,0)
• мы последовательно возвращаем либо первый, либо последний элемент последовательности (оба будут иметь равные шансы быть 0 или 1)

function_B()
{
    do
    {
        int a = function_A();
        int b = function_A();
    } while( (a ^ b) == 0 ); // until a != b

    return a;
}

Дано:

1. События = {голова, хвост}
2. монета нечестная => P (орел) = p и P (решка) = 1-p

Алгоритм:

1. Сгенерируйте выборку событий N1 (орел или решка), используя нечестную монету.
2. оценить его выборочное среднее значение m1 = (#heads)/N1
3. Создайте еще одну выборку событий N2 (орел или решка), используя нечестные монеты.
4. оценить выборочное среднее значение m2 = (#голов)/N2
5. если (m1 > m2) вернуть голову, иначе вернуть хвост

Примечания:

1. События, возвращенные на шаге № 5 выше, равновероятны (P (голова) = P (хвост) = 0,5)
2. Если #5 повторяется много раз, то его выборочное среднее --> 0,5 независимо от p
3. Если N1 --> бесконечность, то m1 --> true означает p
4. Чтобы сгенерировать выход честной монеты, вам нужно много независимых выборок (здесь бросаний) нечестной монеты. Чем больше, тем лучше.

Интуиция. Хотя монета нечестна, отклонение оценочного среднего значения от истинного является случайным и может быть как положительным, так и отрицательным с равной вероятностью. Поскольку истинное среднее значение не указано, оно оценивается по другой выборке.

Выполнимо. Однако двух вызовов этих функций будет недостаточно. Подумайте о том, чтобы вызывать функцию снова и снова, и приближаться к 50/50.

Я задавался вопросом, должно ли работать что-то рекурсивное, с увеличением глубины шанс для 0 или 1 должен быть все ближе и ближе к 0,5. На 1 уровне модифицированный шанс равен p'=p*p+(p-1)*(p-1)

depth = 10;
int coin(depth) {
    if (depth == 0) {
        return function_A();
    }
    p1 = coin(depth-1);
    p2 = coin(depth-1);
    if (p1 == p2) {
        return 1;
    } else {
        return 0;
    }
}

def fairCoin(biasedCoin):
coin1, coin2 = 0,0
while coin1 == coin2:
coin1, coin2 = biasedCoin(), biasedCoin()
return coin1

Это изначально умная идея фон Неймана. Если у нас есть смещенная монета (то есть монета, которая выпадает решкой с вероятностью, отличной от 1/2), мы можем смоделировать честную монету, подбрасывая пары монет, пока два результата не станут разными. Учитывая, что у нас разные результаты, вероятность того, что первый выпадет «орел», а второй — «решка», такая же, как вероятность выпадения «решки», а затем «орла». Так что, если мы просто вернем значение первой монеты, мы получим «орел» или «решку» с одинаковой вероятностью, т.е. 1/2. Этот ответ взят из - http://jeremykun.com/08/02/2014/симуляция-честной-монеты-с-пристрастной-монетой/ подробнее об этом читайте на http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin