Hoeffding's inequality
@complexity
Hoeffding's inequality indicates how much samples we need to take from some distribution (TODO what type of distribution? What assumptions?) so that we are enough sure of that distribution, meaning: within a given error bound.
I think Chernoff's bound is a one-sided variant, whereas Hoeffding's inequality is two-sided.
For example, this is useful when using a stochastic approach to determine the MajSat problem:
- If the running frequency is very close to 0 or 1, we can be sure relatively quickly on a majority decision
- If instead the running frequency is close to 0.5, we are really not sure and need more samples to come to a decision with reasonable confidence.
The Hoeffding's inequality encodes this behavior using
- q: fraction of satisfying truth assignments
- delta: upper bound on the desired degree of error
$$\frac{1}{(q-1/2)^2} ln \frac{1}{\sqrt{\delta}}$$
If q is close to 1/2, you need much more random samples than when you would just iterate over all truth assignments deterministically. If q is close to 1 or 0, this stochastic approach is incredibly more efficient.