Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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 '14 at 1:35
At most you can approximate it by a Gaussian integral for large $n$. – leonbloy Feb 24 '14 at 1:56
Have you tried using the Chernoff bound? – Hoda Feb 24 '14 at 2:34
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|cite|improve this answer
Awesome solution! – zaloo Feb 24 '14 at 2:39

Your Answer


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.