CODEWITHSUNDEEP
algorithmprobability
dangerChihuahua007
dangerChihuahua007

Reputation: 20875

What is the expected number of biased coin tosses for this algorithm?

Suppose I have a biased coin. When flipped, the probability of yielding heads is 4/5.

To fake a fair toss, I pursue the following algorithm that models this situation. Suppose True models heads, and False represents tails.

P(doUnfairFlip() = 0) = 0.8
and
P(doUnfairFlip() = 1) = 0.2

def fakeFairToss():
    flip1 = 0
    flip2 = 0
    while (flip1 == flip2):
        flip1 = doUnfairFlip()
        flip2 = doUnfairFlip()
    return (True if (flip1 == 0) else False)

It makes use of the fact that one is equally likely to get a heads-tails or a tails-heads after two coin flips.

How many individual flips of this biased coin should I expect every time this function runs?

Upvotes: 3

Views: 1519

Answers (3)

Patrick87
Patrick87

Reputation: 28292

If what you're saying is that 

P(rand() % 2 = 0) = 0.8
P(rand() % 2 = 1) = 0.2

Then the probability of meeting the loop condition is

0.8*0.8 + 0.2*0.2 = 0.68

You will execute the loop as many times as the expected number of times to get a failure when p = 0.68, which is 3.125. So you should expect to run the loop 3.125 times, and call rand() a total of 6.25 times.

Upvotes: 1

phs
phs

Reputation: 11051

The odds of equality are 1/5^2 + 4/5^2 = 17/25 = 68%, assuming samples from doUnfairFlip() are IID.

Instead of thinking of loop iterations per function invocation, we can look at the situation as a unbounded sequence of iterations occasionally "punctuated" by function returns. Notice a function return occurs precisely when equality fails, 100 - 68 = 32% of the time.

We can now identify the situation as a discrete Poisson process, with lambda = 0.32. The mean of corresponding distribution is also lambda: we can expect about 0.32 function invocations per loop iteration, or 1.0 / 0.32 = 3.125 iterations per invocation, or 6.25 calls to doUnfairFlip() per invocation.

Upvotes: 4

Kendall Frey
Kendall Frey

Reputation: 44316

I think its about 1.5 runs of the while loop, or 3 calls to rand(). My math may be wrong though.

Upvotes: 0

Related Questions