Как написать функцию для генерации случайного числа 0/1 использовать другую случайную функцию?

Если у меня есть функция с именем rand1(), которая генерирует число 0 (вероятность 30%) или 1 (вероятность 70%), то как написать функцию rand2(), которая генерирует 0 + 1 равновероятность использования rand1()?

Update:

Наконец, я обнаружил, что это проблема в книге "Введение в алгоритмы" (2-й) (я купил китайское издание этой книги), "Упражнение 5.1-3", оригинальная проблема:

5.1-3 Предположим, что вы хотите вывести 0 с вероятностью 1/2 и 1 с вероятностью 1/2. В вашем распоряжении - процедура BIASED-RANDOM, которая выводит либо 0, либо 1. Это выходы 1 с некоторой вероятностью p и 0 с вероятностью 1- p, где 0 < p < 1, но вы не знаете, что такое p. Дайте алгоритм, который использует BIASED-RANDOM как подпрограмма, и возвращает непредвзятый ответ, возвращая 0 с вероятностью 1/2 и 1 с вероятностью 1/2. Какое ожидаемое время работы вашего алгоритма как функция p?

решение: (см.: http://www.cnblogs.com/meteorgan/archive/2012/05/04/2482317.html)

Чтобы получить непредвзятый случайный бит, учитывая только вызовы BIASED-RANDOM, вызовите BIASED-RANDOM дважды. Неоднократно делайте это до тех пор, пока два вызова не возвратятся значения, и когда это произойдет, верните Þrst из двух бит:

UNBIASED-RANDOM
while TRUE
do
x ← BIASED-RANDOM
y ← BIASED-RANDOM
if x != y
then return x

Чтобы увидеть, что UNBIASED-RANDOM возвращает 0 и 1 каждый с вероятностью 1/2, наблюдайте что вероятность того, что заданная итерация вернет 0, равна

Pr {x = 0 and y = 1} = (1 − p)p ,

и вероятность того, что данная итерация вернет 1, равна

Pr {x = 1 and y = 0} = p(1 − p) .

(Мы полагаемся на биты, возвращаемые BIASED-RANDOM, независимыми.) Таким образом, вероятность того, что заданная итерация вернет 0, равна вероятности того, что она вернет 1. Поскольку для UNBIASED-RANDOM нет другого способа вернуть значение, он возвращает 0 и 1 с вероятностью 1/2.

Ответ 1

Создайте два числа, a и b.

Если a равно 0, а b равно 1 (вероятность 21%), сгенерируйте 0.
Если a равно 1 и b равно 0 (вероятность 21%), сгенерируйте 1.

Для всех остальных случаев (вероятность 58%) просто создайте новые a и b и повторите попытку.

Ответ 2

Если вы дважды вызываете rand1, вы получаете равные шансы получить [1 0] и [0 1], поэтому, если вы вернете первую из каждой пары несоответствия (и отбросите пары соответствия), вы получите в среднем, 0.5(1 - p² - (1-p)²) выходных битов на входной бит (где p - вероятность возврата rand1 1; 0,7 в вашем примере) и независимо от p, каждый выходной бит будет равен 1 с вероятностью 0,5.

Однако мы можем сделать лучше.

Вместо того, чтобы выбрасывать совпадающие пары, мы можем помнить их в надежде, что за ними следуют противоположные совпадающие пары. Последовательности [0 0 1 1] и [1 1 0 0] также одинаково вероятны, и снова мы можем вернуть первый бит, когда мы видим такую последовательность (все еще с выходной вероятностью 0,5). Мы можем бесконечно комбинировать их, ища такие последовательности, как [0 0 0 0 1 1 1 1] и т.д.

И мы можем пойти еще дальше - рассмотрим входные последовательности [0 0 0 1] и [0 1 0 0] в том же выпуске ([0]), но эти две последовательности также были одинаково вероятны, поэтому мы можем извлечь дополнительный бит вывода из этого, возвращая [0 0] для первого случая и [0 1] для второго. Здесь все усложняется, так как вам нужно будет начать буферизацию выходных битов.

Оба метода могут быть применены рекурсивно и приняты до предела, он становится без потерь (т.е. если rand1 имеет вероятность 0,5, вы получаете среднее значение по одному выходному биту на входной бит.)

Полное описание (с математикой) здесь: http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf

Ответ 3

Ниже rand2 функция обеспечит 50% вероятность появления нуля или одного.

#define LIMIT_TO_CALCULATE_PROBABILITY 10 //set any even numbers

int rand2()
{
    static int one_occurred = 0;
    static int zero_occured = 0;
    int rand_value = 0;
    int limit = (LIMIT_TO_CALCULATE_PROBABILITY / 2);

    if (LIMIT_TO_CALCULATE_PROBABILITY == (one_occured + zero_occured))
    {
        one_occured = 0;
        zero_occured = 0;
    }

    rand_value = rand1();   

    if ((1 == rand_value) && (one_occured < limit))
    {
        one_occured++;
        return rand_value;
    }
    else if ((0 == rand_value) && (zero_occured < limit))
    {
        zero_occured++;
        return rand_value;
    }
    else if (1 == rand_value)
    {
        zero_occured++;
        return 0;
    }
    else if (0 == rand_value)
    {
        one_occured++;
        return 1;
    }   
}

Ответ 4

Вам нужно будет выяснить, как близко вы хотите добраться до 50% 0 50% 1.

Если вы добавите результаты повторных вызовов в rand1. если результат равен 0 или 2, то возвращаемое значение равно 0, если оно равно 1, а затем возвращает 1. (в коде вы можете использовать по модулю 2)

int val = rand1();   // prob 30%      0, and 70%      1

val=(val+rand1())%2; // prob 58%      0, and 42%      1  (#1 see math bellow)
val=(val+rand1())%2; // prob 46.8%    0, and 53.2%    1  (#2 see math bellow)
val=(val+rand1())%2; // prob 51.28%   0, and 48.72%   1
val=(val+rand1())%2; // prob 49.488%  0, and 50.512%  1
val=(val+rand1())%2; // prob 50.2048% 0, and 49.7952% 1

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

Если вам нужна математика для вероятностей:

1

prob ((val+rand1()%2) = 0) = (prob(val = 0)*prob(rand1() = 0)) + (prob(val = 1)*prob(rand1() = 1)
                           = (0.3*0.3)+(0.7*0.7)
                           = 0.09 + 0.49
                           = 0.58
                           = 58%

prob ((val+rand1()%2) = 1) = (prob(val = 1)*prob(rand1() = 0)) + (prob(val = 0)*prob(rand1() = 1)
                           = (0.7*0.3)+(0.3*0.7)
                           = 0.21 + 0.21
                           = 0.42 
                           = 42%

2

 prob ((val+rand1()%2) = 0) = (prob(val = 0)*prob(rand1() = 0)) + (prob(val = 1)*prob(rand1() = 1)
                            = (0.58*0.3)+(0.42*0.7)
                            = 0.174 + 0.294
                            = 0.468
                            = 46.8%

 prob ((val+rand1()%2) = 1) = (prob(val = 1)*prob(rand1() = 0)) + (prob(val = 0)*prob(rand1() = 1)
                            = (0.42*0.3)+(0.58*0.7)
                            = 0.126 + 0.406
                            = 0.532
                            = 53.2%