Chernoff-like bound for largest allowed deviation? Chernoff bound (for absolute error) gives a bound on probability of large deviation in terms of sample size and amount of deviation, but it doesn't seem possible to rewrite it to give an explicit bound on the amount of deviation. So, what is good way to bound the largest deviation from the mean in terms of sample size and probability of that deviation?
 A: 
in that notation, I'm looking for epsilon as a function of m

If I have not misunderstood, this indicates you want to solve an equation in $q~ (= p +\epsilon)$ of the form
$$q \log(p/q) + (1-q) \log((1-p)/(1-q)) = D(q\,\Vert\, p) = y;\ y \lt 0,$$
given $p$ and $y.$  ($y = \log(p)/m$ reveals the $m$-dependence.)
It is correct that we do not have a name for the solution, but that does not mean it cannot be found, and fairly easily at that.  A little algebra converts this equation into one of the form
$$H(q) = \alpha + \beta\,q$$ where
$$H(q) = -q \log(q) - (1-q) \log(1-q) $$ and $\alpha$ and $\beta$ depend only on $y$ ("probability of deviation") and $m$ ("sample size").
Geometrically this asks for the intersections of a concave downward curve and a line; the curve has endpoints at $(0,0)$ and $(1,0)$ and is symmetric in the unit interval.  There will therefore be up to two solutions.  Newton-Raphson ought to converge rapidly after an initial set of bisection steps finds a point between 0 and the left root and another between the right root and 1 (assuming either exists).
If you need them, theoretical properties of the solution(s) could be readily derived from the definitions of $H,$ $\alpha,$ and $\beta.$
A: I will try and answer your question for only one of the bounds. Chernoff bounds are given by:
$$Pr\left[\frac{1}{m} \sum_{i=1}^{i=m} X_i \ge p+\epsilon\right] \le e^{-D(p+\epsilon\Vert p)m}$$
where
$D(\cdot )$ is the Kullback-Leibler divergence
For the sake of convenience I will denote the rhs of the above inequality by $r(p,\epsilon,m)$. Thus, we have:
$$Pr\left[\frac{1}{m} \sum_{i=1}^{i=m} X_i \ge p+\epsilon\right] \le r(p,\epsilon,m)$$
The above can be re-written as:
$$Pr\left[ \sum_{i=1}^{i=m} X_i \ge m\ (p+\epsilon)\right] \le r(p,\epsilon,m)$$
If we let: $Y = \sum_{i=1}^{i=m} X_i$ then we know that:
$$Y \sim \textrm{Binomial}(m,p)$$
where
$p = Prob(X_i=1)$
Given the above it follows that,
$$Pr\left[ \sum_{i=1}^{i=m} X_i \ge m\ (p+\epsilon)\right] = Pr\left[ Y_i \ge m\ (p+\epsilon)\right]$$
But,
$$Pr[ Y_i \ge m\ (p+\epsilon)] = \sum_{k=\lceil m\ (p+\epsilon) \rceil}^{k=m} {m \choose k} p^k (1-p)^{m-k}$$
Thus, it follows that:
$$\sum_{k=\lceil p+\epsilon \rceil}^{k=m} {m \choose k} p^k (1-p)^{m-k} \le r(p,\epsilon,m)$$
I am not sure if we can simplify the above to express $\epsilon$ as a function of $m$ but it may be of some help. Alternatively, you may want to explore the use of the normal approximation to the binomial.
