bounding probability of biased coin.

Suppose I have a biased coin where heads have probability $p$. I flip it 10000 times and it comes up heads 5000 times. Now I wish to bound the probability that 5000 out of 10000 comes up as heads and that the next coin flip is heads, that is $$ \mathbb{P}(5000/1000 \text{ heads and next coin flip is also heads}) $$

Clearly the two "events" are independent. I read that it can be bounded by $0.08$ (not that the bound would realistically be of much interest), but I don't quite see how one would go about doing that. Can you apply Hoeffding's inequality?

Solution 1:

In $2n$ tosses, the probability of getting exactly $n$ heads is given by $\binom{2n}n p^n (1 - p)^n$, just by counting all possibilities. To get another head, you just need to multiply by $p$. So your final probability is equal to $$ \binom{2n}{n} p^{n+1} (1 - p)^n. $$ Plug in $n = 5000$. Note that if you want to do this on a computer/calculator, you should probably apply Stirling's formula to the Binomial to get an approximation.

Regarding absolute bounds, it's easy to see that $p(1-p) \le \tfrac14$ whenever $p \in [0,1]$. So you can upper bound this by $$ \binom{2n}{n} 4^{-n} = \binom{2n}{n} 2^{-2n}. $$ As pointed out by @aschepler in the comments, differentiating gives an exact maximum at $$ p = \frac{n+1}{2n+1} = \frac12 \biggl(1 + \frac1{2n+1}\biggr). $$