# Calculate probability of at least n/2 heads if there are n coin tosses

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.

-
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

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}$.

-
Awesome solution! – zaloo Feb 24 '14 at 2:39