28

Here is an explicit proof that a standard Chernoff bound is tight up to constant factors in the exponent for a particular range of the parameters. (In particular, whenever the variables are 0 or 1, and 1 with probability 1/2 or less, and $\epsilon\in(0,1/2)$, and the Chernoff upper bound is less than a constant.) If you find a mistake, please let me know. ...


22

The Berry-Esseen theorem can give tail probability lower bounds, as long as they are higher than $n^{-1/2}$. Another tool you can use is the Paley-Zygmund inequality. It implies that for any even integer $k$, and any real-valued random variable $X$, $$ \Pr[|X| >= \frac{1}{2}(\mathbb{E}[X^k])^{1/k}] \geq \frac{\mathbb{E}[X^k]^2}{4\mathbb{E}[X^{2k}]} $$ ...


14

If you are indeed okay with bounding sums of Bernoulli trials (and not, say, bounded random variables), the following is pretty tight. Slud's Inequality*. Let $\{X_i\}_{i=1}^n$ be i.i.d. draws from a Bernoulli r.v. with $\mathbb{E}(X_1) = p$, and let integer $k\leq n$ be given. If either (a) $p\leq 1/4$ and $np \leq k$, or (b) $np \leq k \leq n(1-p)$, ...


7

The de Moivre-Laplace Theorem shows that variables like $|T\cap S_1|$, after being suitably normalised and under certain conditions, will converge in distribution to a normal distribution. That's enough if you want constant lower bounds. For lower bounds like $n^{-c}$, you need a slightly finer tool. Here's one reference I know of (but only by accident - I'...


7

For concreteness, say that the pdf of the r.v. $X_i$ is $$p(X_i = x) = \frac{1}{2} \lambda_i e^{-\lambda_i|x|}.$$ This is the Laplace distribution, or the double exponential distribution. Its variance is $\frac{2}{\lambda_i^2}$. The cdf is $$ \Pr[X_i \leq x] = 1 - \frac{1}{2}e^{-\lambda_i x} $$ for $x \geq 0$. The moment generating function of $X_i$ ...


6

If $X_1, \cdots, X_n$ are $k$-wise independent random variables on $[0,1]$, then $$\text{Pr} \left[ \left| \sum_i X_i - \text{Ex}\left[ \sum_i X_i \right] \right| \geq n \cdot \varepsilon \right] \leq \left( \frac{k^2}{4 n \varepsilon^2} \right)^{\lfloor k/2 \rfloor}.$$ Note that this bound does not necessarily improve with greater $k$. So you may want to ...


4

This is the first link on Google for the search "chernoff limited independence": "Chernoff-Hoeffding Bounds for Applications with Limited Independence" by Schmidt et al.


4

I'll take as given the existence of Chaitin's constant $\Omega\in[0,1]$, and that knowing its first $k$ bits is equivalent to be able to decide the halting problem for all Turning machines of size up to $k$: https://en.wikipedia.org/wiki/Chaitin%27s_constant Given access to an $\Omega$-biased coin, one can use Chernoff bounds to compute $\hat\Omega_k$, ...


4

The Generalized Littlewood-Offord Theorem isn't exactly what you want, but it gives what I think of as a "reverse Chernoff" bound by showing that the sum of random variables is unlikely to fall within a small range around any particular value (including the expectation). Perhaps it will be useful. Formally, the theorem is as follows. Generalized ...


3

For the Laplace distribution, if you use the Bernoulli bound you can write $$Ee^{u\sum_i X_i} = \prod_i \frac1{1-u^2/\lambda_i^2} \le \frac1{1-u^2\sigma^2/2},$$ where $\sigma^2=2\sum_i\lambda_i^{-2}$. Then the classical Chernoff method to gives $$\Pr[\sum_i X_i \ge t\sigma]\le \tfrac{1+\sqrt{1+2t^2}}{2} e^{1-\sqrt{1+2t^2}} \le\cases{ (et/\sqrt2+1) e^{-\...


3

An alternative reference could be Lemma 1.19 in B. Doerr, Analyzing randomized search heuristics: Tools from probability theory, Theory of Randomized Search Heuristics (A. Auger and B. Doerr, eds.), World Scientific Publishing, 2011, pp. 1-20. In simple words, it shows that when $X_i=1$ with probability $p_i$ no matter what you condition $X_1, \dots, X_{i-...


3

You have $\mathbb{E}[y_i]=\epsilon q(x_i) + (1-\epsilon)/2$ and $0 \leq y_i \leq 1$, with all they $y_i$s being independent. Thus the Chernoff-Hoeffding bound gives $$\mathbb{P}\left[\left|\frac{1}{n} \sum_{i=1}^n y_i -\epsilon q(x_i) - \frac{1-\epsilon}2\right| \geq \lambda\right] \leq 2 \cdot e^{-2\lambda^2 n}$$ for all $\lambda>0$. Multiply through by $...


3

The exponent in the standard Chernoff bound as it is stated on Wikipedia is tight for 0/1-valued random variables. Let $0<p<1$ and let $X_1,X_2,\ldots $ be a sequence of independent random variables such that for each $i$, $\Pr[X_i=1]=p$ and $\Pr[X_i=0]=1-p$. Then for every $\varepsilon>0$, \begin{equation} \frac{2^{-D(p+\varepsilon\| p)\cdot n}}{n+...


2

You need McDiarmid's inequality, or in particular the Hoeffding inequality, which is a simplification: Given $n$ independent $X_i$ with the property that $X_i \in [a_i, b_i]$, and $X = (1/n)\sum X_i$, then $$ \text{Pr}(|X - EX| \ge t) \le 2 \exp(\frac{2t^2n^2}{\sum (b_i - a_i)^2}) $$


2

The Kearns-Saul inequality states that if $X\sim Ber(p)$ then $$ E[\exp(t(X-p))] = (1-p)e^{-tp}+pe^{t(1-p)} \le \exp\left(\frac{1-2p}{4\log((1-p)/p)}t^2\right).$$ The subgaussian constant $\frac{1-2p}{4\log((1-p)/p)}$ is optimal. See http://ecp.ejpecp.org/article/view/2359 and especially the appendix in http://www.jmlr.org/papers/v16/berend15a.html for ...


1

One way to approach this problem is via the CDF transformation. Consider $Z=F(X)$. We know $Z$ is uniformly distributed in $[0,1]$. Let $Z_{(1)},...,Z_{(m)}$ be the order statistics of these $m$ samples (after transforming to Z). It can be shown that $Z_{(t)}\sim \text{Beta}(t,m+1-t)$. Using this, $Z_{(m\cdot k/n)}=F(X_{(m\cdot k/n)})$ is a consistent ...


1

I'm posting a suitable answer that I found for this problem. The approach linked here does not exploit the fact that no $t$-tuples of elements of $\Omega$ are present in too many subsets $Y$ (for arbitrary $t$), but it does end up giving me a good enough bound anyway.


1

I think that in principle it would take exponential time to compute this probability exactly. Hence sampling would be the only option here, although you would have to settle for additive and multiplicative approximation here. Can I ask you about the problem in which you need this value to be computed?


Only top voted, non community-wiki answers of a minimum length are eligible