Timeline for How does one change the probability bounds in probabilistic complexity classes without changing the class?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 8, 2015 at 0:30 | comment | added | Yuval Filmus | What you're describing is the weak law of large numbers, but it's not enough for us. We need a polynomial upper bound on $n$. | |
| May 8, 2015 at 0:29 | comment | added | user6818 | One would be done if someone shows that $f(n)$ is monotonically decreasing and doesn't hit an asymptote before passing below $q$. | |
| May 8, 2015 at 0:29 | comment | added | Yuval Filmus | It is the right way to think. Chernoff's bound is just a convenient way of estimating this sum. If you can estimate the sum in some other way, that's also great. | |
| May 8, 2015 at 0:27 | comment | added | user6818 | Why is this not the right way to think? Why do Chernoff-Hoefding? | |
| May 8, 2015 at 0:27 | comment | added | user6818 | I mean - why is the Chernoff-Hoefding bound necessary? Think of it this way : Say success probability in a trial is lower bounded by $p$ then the probability that $k$ of the $n$ trials succeed is lower bounded by $(1-p)^{(n-k) }p^k$. So one can define the function $f(n) = \text{ probability that most of the n trials succeed}$ and one gets that $f(n) \geq \sum_{k= \frac{n}{2}}^{n} (1-p)^{(n-k)}p^k$. Given a need for a success quarantee of $q$ one would be done if one can show that there exists a $n$ such that $q < \sum_{k= \frac{n}{2}}^{n} (1-p)^{(n-k)}p^k $ . | |
| May 7, 2015 at 22:38 | comment | added | Yuval Filmus | $\operatorname{Bin}(n,p)$ is a binomial random variable corresponding to $n$ trials with success probability $p$ each. In order to know that the Chernoff bound gives in this case, you take the formula given by the Chernoff bound, substitute the parameters, and simplify. You don't need me for that. | |
| May 7, 2015 at 22:08 | comment | added | user6818 | What is $Bin$ here? So what exactly does the Chernoff bound give in this case? Is the whole point that to show that given any probability threshold one can iterate the stuff a certain number of times to get the soundness probability below this threshold? | |
| May 4, 2015 at 21:12 | history | answered | Yuval Filmus | CC BY-SA 3.0 |