Tag Info

4

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+...

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 ...

4

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 $... 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$, ... 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^{-\... 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 ... 2 Using Chandra's hint, I think I got the idea. We bounded the probability:$$Pr(G_i \leq b_i) \leq e^{-\frac{\rho(1-\frac{1}{\rho})^2 b_i}{3}}$$Now consider an item of size s_i that was left. It was left out because we didn't sample a configuration that contains it. This happens with probability$$(1-\sum_{j:{\bf T_j} \text{ contains item }i}\frac{x_j}{z^\... 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