Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose I toss a coin with some probability $p$ of heads $n$ times. I want to know the probability that I get at least $n/2$ heads. I know I can take the sum of bernoulli trials, but is there some way of solving this without a summation?

EDIT: Here's the specific problem. I'm trying to show that if I flip n coins that flip tails with $p=1/4$, that I get more than $n/2$ tails with probability at least $1/2^{n}$. I'm not a probability wiz but I can prove a theorem for my randomized algorithms class if I can show this is true.

share|improve this question
1  
For general $p$, I do not see how to avoid a summation of binomial distribution probabilities. For $p=1/2$ one can get a simple expression. –  André Nicolas Feb 24 at 1:35
    
At most you can approximate it by a Gaussian integral for large $n$. –  leonbloy Feb 24 at 1:56
    
Have you tried using the Chernoff bound? –  Hoda Feb 24 at 2:34

1 Answer 1

up vote 2 down vote accepted

Divide the coins into pairs. Each pair produces at least one head with probability $1-(\frac{3}{4})^2 > 2^{-2}$. Now the probability that all the coins produce at least $\frac{1}{2}n$ heads is more than the probability that every pair produces at least one head. If you want to deal with odd number of coins, check that the probability that 3 coins produce at least two heads is $(\frac{1}{4})^3 + 3(\frac{1}{4})^2(\frac{3}{4}) > 2^{-3}$, and divide the coins into pairs or triples. This in fact shows that if the number of coins is a multiple of three it produces at least $\frac{2}{3}$ heads with probability at least $2^{-n}$.

share|improve this answer
    
Awesome solution! –  zaloo Feb 24 at 2:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.