Converse form of Chernoff bound

Suppose $$X_1,\ldots,X_n$$ are i.i.d. random variables, all with mean $$p$$, and we have the statement that $$\Pr\left[\sum_i X_i\geq 0.8n\right]\geq 0.9$$, can we use this to conclude anything about $$p$$ (in particular a lower bound)? I know that we can use $$p$$ to prove bounds on $$\Pr\left[\sum_iX_i\geq (1\pm\varepsilon)n\right]$$, but I want use the latter to prove a bound on the former?

• Berry-Esseen theorem could be one way to go. Compares the CDF of the sum to a normal distribution. en.wikipedia.org/wiki/Berry%E2%80%93Esseen_theorem
– usul
Oct 25, 2021 at 6:11
• By a standard Chernoff bound you have, say, $\Pr[\sum_i X_i \ge (1+\epsilon) pn] \le \exp(-\epsilon^2 pn/3)$. So taking $\epsilon$ such that $(1+\epsilon)p = 0.8$, you have $\exp(-\epsilon^2 pn/3) \ge 0.9$. This implies a lower bound on $p$. In particular something like $p \ge 0.8(1-1/\sqrt{2n})$ or so. This probably doesn't qualify as a research-level question so should be migrated to cs.stackexchange.com . Oct 25, 2021 at 16:27
• see this question cstheory.stackexchange.com/questions/14471/… May 29 at 17:32