Search code examples
recursionruntimeprobability

Analysing runtime

I came across a question to implement an unbiased random function which outputs 0 or 1 using a biased output function which outputs 0 or 1 with probability P for outputting 1. And to predict how the runtime varies in accordance with P

I implemented it as follows

Random() {
     i = BRand();
     j = BRand();

    if(i!=j)
          Return i;
    else
           Random();
    }

But I'm unable to figure out how the runtime would vary in terms of P.

Solution

  • Say BRand has a 70% chance (P = 0.7) to produce a one (1), and thus a 30% chance (1 - P) to produce a zero (0) -

    i = 1 1 1 1 1 1 1 0 0 0
j = 1 1 1 1 1 1 1 0 0 0

    We only return a result when i != j, so that rules out any combination where (i, j) both produce a zero, (0, 0), or both produce a one, (1, 1). The effect of running Random() once is thus -

    • 30% * 30% = 9% probability of (0, 0), recur
    • 70% * 70% = 49% probability of (1, 1), recur
    • 30% * 70% = 21% probability of (0, 1), return 0
    • 70% * 30% = 21% probability of (1, 0), return 1

    Where P = .7, 58% (49% + 9%) of the time we will recur. In the other 42%, there is an equal probability to return either zero or one. At the low cost of recursion, indeed this clever algorithm will make an unbiased random number generator out of a biased generator.

    Changing the probability to P = 0.1 we see a different result:

    i = 1 0 0 0 0 0 0 0 0 0
j = 1 0 0 0 0 0 0 0 0 0

    The effect of running Random() is

    • 90% * 90% = 81% probability of (0, 0), recur
    • 10% * 10% = 1% probability of (1, 1), recur
    • 90% * 10% = 9% probability of (0, 1), return 0
    • 10% * 90% = 9% probability of (1, 0), return 1

    Where P = 0.1, 82% of the time we will recur. In the other 18%, there is an equal probability to return zero or one.

    Exercise 1: Show why P = 0.9 has the same outcome has P = 0.1. What relationship do you see here?

    Exercise 2: What is the probability we will recur when P = 0.001? What about P = 0.999?

    Exercise 3: What is special about P = 0.5?

    After you have completed the exercises, reveal the text below -

    When P = 0.5 we see the lowest runtime for Random(), with only 50% chance to recur. This makes sense because P = 0.5 is already unbiased! Ie, the effect of running BRand already has equal chance to produce a zero or one. As P deviates from 0.5 we notice it there is a higher probability that Random() will recur, thus Random() requires a longer runtime to make an unbiased generator.

    Exercise 4: Write a formula that calculates probability of recursion based on P

    F(p) = p2 + (1 - p)2   —   where 0 <= p <= 1