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?
$\begingroup$
$\endgroup$
3
-
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$– usulOct 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 YoungOct 25, 2021 at 16:27
-
2$\begingroup$ see this question cstheory.stackexchange.com/questions/14471/… $\endgroup$– AryehMay 29, 2022 at 17:32
Add a comment
|