Let $X \sim Binomial(n, p)$. If $p$ is bounded s.t. $p_{\text{min}} \le p \le 1/2$, is there a bound in the error in empirical probability compared to true probability? The empirical probability $\bar{p} = n_{\text{success}} / n$.
What I'm trying to find is a theorem of the form:
If $p_{\text{min}} \le p \le 1/2$, then $|\bar{p} - p| \le radius$ with high probability.
if one exists.
Edit: Since I must work with finite number of iterations, normal approximation guaranteed by the CLT for large $n$ does not hold. As such, I modeled the expected error as a beta distribution instead.
We can do this using the "generic Chernoff bound." Write $X = \sum_{i=1}^n X_i$ as the sum of $n$ iid Bernoulli variables $\text{Ber}(p)$, so that the empirical probability is the average $\frac{X}{n}$. Markov's inequality applied to $e^{tX}$ gives that for $t \ge 0$ we have
$$\mathbb{P} \left( \frac{X}{n} \ge a \right) = \mathbb{P}(e^{tX} \ge e^{tna}) \le \frac{\mathbb{E}(e^{tX})}{e^{tna}}.$$
which gives
$$\mathbb{P} \left( \frac{X}{n} \ge a \right) \le \inf_{t \ge 0} \frac{\mathbb{E}(e^{tX})}{e^{tna}}.$$
We now compute this infimum. We have $\mathbb{E}(e^{tX}) = \mathbb{E}(e^{tX_1})^n = \left( p e^t + (1 - p) \right)^n$ so taking the logarithmic derivative of the bound gives
$$\frac{d}{dt} \log \frac{\mathbb{E}(e^{tX})}{e^{tna}} = n \left( \frac{pe^t}{pe^t + (1 - p)} - a \right).$$
Setting this equal to zero and solving for $e^t$ gives $e^t = \frac{a(1-p)}{p(1-a)}$, which guarantees that $t \ge 0$ as long as $a \ge p$, and substituting this back in gives that if $a \ge p$ then
$$\boxed{ \mathbb{P} \left( \frac{X}{n} \ge a \right) \le \exp \left(- n KL(a, p) \right) }$$
where
$$\begin{align*} KL(a, p) &= - \log \left( a \frac{(1-p)}{1-a} + (1-p) \right) + a \log \frac{a(1-p)}{p(1-a)} \\ &= a \log \frac{a}{p} + (1 - a) \log \frac{1-a}{1-p} \end{align*}$$
is the rate function; this is an example of a large deviation inequality, I guess it is called the Chernoff-Hoeffding theorem, and $KL$ is the KL divergence between $\text{Ber}(a)$ and $\text{Ber}(p)$. We have $KL(a, p) \ge 0$ with equality iff $a = p$ as expected, so that when $a > p$ this tells us that the probability that the empirical probability exceeds the true probability by a fixed positive constant decays exponentially in $n$. Morever, Cramer's theorem tells us that this exponent $KL(a, p)$ is asymptotically optimal in the sense that $\lim_{n \to \infty} \frac{\log \mathbb{P} \left( \frac{X}{n} \ge a \right)}{n} = - KL(a, p)$.
We can get a bound on $\mathbb{P} \left( \frac{X}{n} \le a \right)$ from this bound by considering $Y = n - X = \sum_{i=1}^n (1 - X_i)$ which is again a sum of $n$ iid Bernoulli random variables $\text{Ber}(1 - p)$. Then $\mathbb{P} \left( \frac{X}{n} \le a \right) = \mathbb{P} \left( \frac{Y}{n} \ge 1 - a \right)$, which gives that if $a \le p$ then
$$\mathbb{P} \left( \frac{X}{n} \le a \right) \le \exp \left( - n KL(1-a, 1-p) \right) = \exp \left( - n KL(a, p) \right)$$
from which we conclude that
$$\boxed{ \mathbb{P} \left( \left| \frac{X}{n} - p \right| < \varepsilon \right) \ge 1 - \exp \left( - n KL(p + \varepsilon, p) \right) - \exp \left( - n KL(p - \varepsilon, p) \right) }.$$
This can be massaged into various other forms depending on what you need. For example if you want $\varepsilon = O \left( \frac{1}{\sqrt{n}} \right)$ then you'd want to investigate the first few terms of the Taylor series of $KL(p \pm \varepsilon, p)$ which will recover a CLT / Hoeffding-type bound.