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

CC BY-SA 4.0
2021-10-25T06:11:18.917Z
Berry-Esseen theorem could be one way to go. Compares the CDF of the sum to a normal distribution. https://en.wikipedia.org/wiki/Berry%E2%80%93Esseen_theorem
usul
CC BY-SA 4.0
2021-10-25T16:27:39.580Z
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 .
Neal Young
CC BY-SA 4.0
2022-05-29T17:32:50.773Z
see this question https://cstheory.stackexchange.com/questions/14471/reverse-chernoff-bound/
Aryeh
<pr.probability><randomness><chernoff-bound>
Converse form of Chernoff bound
Annonymous
# Converse form of Chernoff bound

(Asked by: username_0 on 2021-10-24)

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?

**Tags:** pr.probability, randomness, chernoff-bound
> **Comments:**
> **username_1**: Berry-Esseen theorem could be one way to go. Compares the CDF of the sum to a normal distribution. https://en.wikipedia.org/wiki/Berry%E2%80%93Esseen_theorem  
> **username_2**: 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 .  
> **username_3**: see this question https://cstheory.stackexchange.com/questions/14471/reverse-chernoff-bound/  

---

## 0 answers

