wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Unfair coin
        
(Message started by: ameba on Oct 21^st, 2003, 3:25am)

Title: Unfair coin
Post by ameba on Oct 21^st, 2003, 3:25am

An unfair coin ( probability p of showing heads ) is tossed n times. What is the probability that the number of heads will be even?

Title: Re: Unfair coin
Post by william wu on Oct 21^st, 2003, 4:47am

(hidden; highlight the following area with mouse to see)
::[hide]
Let X be the random variable corresponding to the number of heads in n tosses. Then X is binomial random variable whose distribution is given by:

Pr(X = k) = C(n,k) p^k(1-p)^n-k

where C(n,k) is the binomial coefficient k! / (k!(n-k)!).

The probability of getting an even number of heads is then the sum of the probabilities of getting each possible even number from 0 to n:

Pr(even) = [sum]_k[in]evens Pr(X=k)

[/hide]
::

Title: Re: Unfair coin
Post by wowbagger on Oct 21^st, 2003, 5:05am

Just when I thought "Oh no, not again!" (too late), I saw that I can still contribute:
The binomial coefficient is C(n,k) = k! / ( n! (n-k)! ).

n! isn't well-defined for negative integer n, so maybe you just mixed up the arguments of C.

Title: Re: Unfair coin
Post by towr on Oct 21^st, 2003, 5:08am

::[hide]
given William's
Pr(X = k) = C(n,k) p^k(1-p)^n-k
Pr(even) = [sum]_k[in]evensPr(X = k)

Now let's use
C(n,k) (-p)^k(1-p)^n-k
which will be negative if k is odd,
then C(n,k) (-p)^k(1-p)^n-k + C(n,k) p^k(1-p)^n-k = 2 * Pr(X = k) if k is even, else 0.

now
2 * Pr(even) = [sum]_k C(n,k) p^k(1-p)^n-k+ [sum]_k C(n,k) (-p)^k(1-p)^n-k
= (p+(1-p))ⁿ + (-p+(1-p))ⁿ
so Pr(even) = (1 + (1-2p)ⁿ)/2 unless I screwed things up horribly..[/hide]::

Title: Re: Unfair coin
Post by william wu on Oct 21^st, 2003, 5:33am

That seems to be right .... it passes several sanity checks I tried on it (n=2,n=0,p=0,p=1). That's a neat trick towr. :) In case anyone is wondering how the second to last equality follows, it comes from the Binomial Theorem:

(x+y)ⁿ = [sum]_{k=0 to n} C(n,k)x^ky^n-k

C(n,k) also corresponds to the kth number (reading left to right) in the nth row of Pascal's triangle, where both rows and their elements are indexed starting from 0.

wowbagger: thanks, corrected ... yes it was a typo :)

Title: Re: Unfair coin
Post by towr on Oct 21^st, 2003, 6:40am

on 10/21/03 at 05:33:50, william wu wrote:

That seems to be right .... it passes several sanity checks I tried on it (n=2,n=0,p=0,p=1). That's a neat trick towr. :)

Thanks..
I wonder if it can be extended to other multiples.. f.i. the chance the number of heads is a multiple of three

Title: Re: Unfair coin
Post by towr on Oct 21^st, 2003, 7:24am

It's seems it's easily extended.. for multiples of three we can use the roots of a³=1 :
a₁ = -1/2 - [sqrt]3 i/2,
a₂ = -1/2 + [sqrt]3 i/2 and
a₃ = 1
and we get ((a₁p+(1-p))ⁿ + (a₂p+(1-p))ⁿ + (a₃p+(1-p))ⁿ)/3

and for multiples of 4 we can use the roots of a⁴=1 (i,-i,1,-1) , etc