Author |
Topic: Unfair coin (Read 524 times) |
|
ameba
Guest
|
An unfair coin ( probability p of showing heads ) is tossed n times. What is the probability that the number of heads will be even?
|
|
 IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Re: Unfair coin
« Reply #1 on: Oct 21st, 2003, 4:47am » |
 Quote  Modify
|
(hidden; highlight the following area with mouse to see)
::
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) pk(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)
::
|
| « Last Edit: Oct 21st, 2003, 5:35am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Unfair coin
« Reply #2 on: Oct 21st, 2003, 5:05am » |
Quote Modify
|
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.
|
| « Last Edit: Oct 21st, 2003, 5:07am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Unfair coin
« Reply #3 on: Oct 21st, 2003, 5:08am » |
Quote Modify
|
::
given William's
Pr(X = k) = C(n,k) pk(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) pk(1-p)n-k = 2 * Pr(X = k) if k is even, else 0.
now
2 * Pr(even) = [sum]k C(n,k) pk(1-p)n-k+ [sum]k C(n,k) (-p)k(1-p)n-k
= (p+(1-p))n + (-p+(1-p))n
so Pr(even) = (1 + (1-2p)n)/2 unless I screwed things up horribly..::
|
| « Last Edit: Oct 21st, 2003, 5:15am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Unfair coin
« Reply #4 on: Oct 21st, 2003, 5:33am » |
Quote Modify
|
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)n = [sum]k=0 to n C(n,k)xkyn-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
|
| « Last Edit: Oct 21st, 2003, 5:40am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Unfair coin
« Reply #5 on: Oct 21st, 2003, 6:40am » |
Quote Modify
|
on Oct 21st, 2003, 5:33am, 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
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Unfair coin
« Reply #6 on: Oct 21st, 2003, 7:24am » |
Quote Modify
|
It's seems it's easily extended.. for multiples of three we can use the roots of a3=1 :
a1 = -1/2 - [sqrt]3 i/2,
a2 = -1/2 + [sqrt]3 i/2 and
a3 = 1
and we get ((a1p+(1-p))n + (a2p+(1-p))n + (a3p+(1-p))n)/3
and for multiples of 4 we can use the roots of a4=1 (i,-i,1,-1) , etc
|
| « Last Edit: Oct 21st, 2003, 7:25am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove