Загадка C: сделайте из монеты предвзятую монету - PullRequest
Новая
       30

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

23 голосов
/ 25 марта 2011

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

Пусть function_A вернет 0 с вероятностью 40% и 1 с вероятностью 60%.Генерируйте 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?

Ответы [ 6 ]

70 голосов
/ 25 марта 2011

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

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

  • Вероятность того, что он поднимется головой дважды, равна p 2
  • Вероятность того, что он пойдет первым, а вторым - p (1-p)
  • Вероятность того, что он придет первым, а затем головой, составляет (1-p) p
  • Вероятность того, что он выползет дважды, равна (1-р) 2

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

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.

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

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

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

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

8 голосов
/ 25 марта 2011

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

  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

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

Дано:

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

Алгоритм:

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

Примечания:

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

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

0 голосов
/ 10 февраля 2015 
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

0 голосов
/ 25 марта 2011

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

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

...