<s>[INST] Approximations of $\sum_{i=0}^k\binom{2k+1}{i}p^i(1-p)^{k-i}$ Given a biased coin with a probability $p$ of coming up heads, what is the probability that strictly more than half of $2k+1$ flips turn up heads?
This probability can be modelled as
$$\sum_{i=k+1}^{2k+1}\binom{2k+1}{i}p^{i}(1-p)^{2k+1-i} = p^k\sum_{i=0}^{k}\binom{2k+1}{i}p^i(1-p)^{k-i}\qquad(1)$$
This last sum is quite close to the following identity
$$1  = (p + (1-p))^k = \sum_{i=0}^k\binom{k}{i}p^i(1-p)^{k-i} \qquad (2)$$
which leads me to think there is some way of approximating $(1)$ using $(2)$, but I am coming up short with good approaches. How might I approximate the aforementioned probability?
 [/INST] It looks similar but it really isn't. The binomial identity sum is, of course, always $1$, whereas the probability you are interested in has behavior that differs dramatically depending on whether $p > \frac{1}{2}, p = \frac{1}{2}$, or $p < \frac{1}{2}$.
Instead we can use the Chernoff bound. Let $X \sim \text{Bin}(2k+1, p)$ be the number of heads that occur when we flip a coin $2k+1$ times whose bias is $p$. Then the Chernoff bound gives that if $p \le \frac{1}{2}$ then
$$\mathbb{P} \left( \frac{X}{2k+1} \ge \frac{1}{2} \right) \le \exp \left( -(2k+1) KL \left( \frac{1}{2}, p \right) \right)$$
where $KL \left( \frac{1}{2}, p \right) = - \frac{1}{2} \log 4p(1 - p)$ is a KL divergence. (Strictly speaking we want $\mathbb{P} \left( \frac{X}{2k+1} \ge \frac{k+1}{2k+1} \right)$ which will give a slightly better bound but it'll be messier to work with.) This gives
$$\boxed{ \mathbb{P} \left( \frac{X}{2k+1} \ge \frac{1}{2} \right) \le (4p(1-p))^{\frac{2k+1}{2} } }$$
which tells us that for $p < \frac{1}{2}$ the probability decays exponentially quickly in $n$, with the base of the exponential depending on $p$, such that the exponential decay is faster the smaller $p$ is, which should be fairly intuitive. For example if $p = \frac{1}{3}$ the base of the exponential is $\frac{4}{3} \cdot \frac{2}{3} = \frac{8}{9}$. Note that $4p(1 - p) \le 1$ and attains its maximum at $p = \frac{1}{2}$, which should also be fairly intuitive.
By substituting $1 - p$ for $p$, or by applying the Chernoff bound in the other direction, we similarly get that if $p \ge \frac{1}{2}$ then
$$\mathbb{P} \left( \frac{X}{2k+1} \le \frac{1}{2} \right) \le \exp \left( -(2k+1) KL \left( \frac{1}{2}, 1 - p \right) \right) = \exp \left( -(2k+1) KL \left( \frac{1}{2}, p \right) \right)$$
which now gives that if $p > \frac{1}{2}$ then
$$\boxed{ \mathbb{P} \left( \frac{X}{2k+1} > \frac{1}{2} \right) \ge 1 - (4p(1-p))^{\frac{2k+1}{2}} }.$$
So we get the opposite behavior: instead of a probability that decays exponentially we get a probability which is exponentially close to $1$, which should again be intuitive.
The case $p = \frac{1}{2}$ should be analyzed separately; both of the above bounds trivialize in this case but of course we can just exactly compute the answer, which is $\frac{1}{2}$ by symmetry.
</s>