C головоломка: сделайте честную монету из предвзятой монеты

Как определить вероятность того, что функция вернет 0 или 1 в следующем случае:

Пусть function_A возвращает 0 с вероятность 40% и 1 с вероятностью 60%. Создайте a function_B с помощью вероятности 50-50, используя только function_Aтолько.

Я подумал о следующем:

 function_B()
 {
     int result1=function_A();
     int result2=function_A();
     //two times 40% would result in 16% and 40%+60% would be 24%... two times 60%                        would be 36%
 }

Какая комбинация может дать 50-50?

Ответ 1

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

Наблюдение заключается в том, что если у вас есть предвзятая монета, которая поднимает головы с вероятностью 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 монетных флип, чтобы получить хороший флип.

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

Ответ 2

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

<суб >

вероятность того, что function_A возвращает 1: P (1) = p (например, p = 60%).

вероятность того, что function_A возвращает 0: P (0) = 1 - p

вероятность для определенной последовательности возвращаемые значения a, b,... на последовательных вызовы function_A - это P (a) P (b)...
наблюдать определенные комбинации возникают с равными коэффициентами, например:
      P(a)*P(b) === P(b)*P(a)
 P(a)*P(b)*P(c) === P(b)*P(c)*P(a)

 etc.
мы можем использовать этот факт при выборе только последовательности (1,0) или (0,1), то знайте, что вероятность того, что это либо
    P(1)*P(0)/(P(1)*P(0) + P(0)*P(1)) 
 => x / (x + x)
 => 1 / 2
суб >

Это, таким образом, становится рецептом для реализация функции_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;
}

Ответ 3

Дано:

События = {head, tail}
монета несправедлива = > P (head) = p и P (tail) = 1-p

Алгоритм:

Сгенерировать образец событий N1 (голова или хвосты) с использованием несправедливой монеты
оценить его среднее значение выборки m1 = (#heads)/N1
Создайте еще один образец событий N2 (головы или хвосты) с использованием несправедливых монет
оценивает его примерное среднее m2 = (#heads)/N2
if (m1 > m2) return head else return tail

Примечания:

События, возвращенные на шаге № 5 выше, одинаково вероятны (P (head) = P (tail) = 0.5)
Если # 5 повторяется много раз, то его примерное среднее → 0,5, независимо от p
Если N1 → бесконечность, то m1 → true среднее p
Чтобы создать честный выпуск монет, вам нужно много самостоятельной выборки (здесь броски) несправедливой монеты. Чем больше, тем лучше.

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

Ответ 4

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

Ответ 5

Я задавался вопросом, должно ли что-то рекурсивное работать, с увеличением глубины шанс на 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;
    }
}

Ответ 6

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

Это изначально умная идея фон Неймана. Если у нас есть предубежденная монета (т.е. Монета, которая придумывает головы с вероятностью, отличной от 1/2), мы можем имитировать справедливую монету, бросая пары монет до тех пор, пока два результата не будут разными. Учитывая, что у нас разные результаты, вероятность того, что первая - "голова", а вторая - "хвосты", совпадает с вероятностью "хвостов", затем "головами". Поэтому, если мы просто вернем значение первой монеты, мы получим "головы" или "хвосты" с той же вероятностью, то есть 1/2.Этот ответ от - http://jeremykun.com/2014/02/08/simulating-a-fair-coin-with-a-biased-coin/ подробнее об этом читайте http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin