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?

  • 2
    $\begingroup$ 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 $\endgroup$
    – usul
    Oct 25, 2021 at 6:11
  • 3
    $\begingroup$ 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 . $\endgroup$
    – Neal Young
    Oct 25, 2021 at 16:27
  • 2
    $\begingroup$ see this question cstheory.stackexchange.com/questions/14471/… $\endgroup$
    – Aryeh
    May 29 at 17:32


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy