5
votes
Reverse Chernoff bound
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 ...
- 11.9k
4
votes
How to use a 𝑝-coin so a TM can decide an undecidable language in polynomial time?
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 ...
- 10.2k
4
votes
Reverse Chernoff bound
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 ...
- 742
4
votes
Accepted
Differential Privacy and Randomized Responses for Counting Queries
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} ...
- 2,803
3
votes
Sum of Independent Exponential Random Variables
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}$....
- 958
2
votes
Accepted
Orlicz norm of random variable and variance
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}...
- 10.2k
2
votes
Accepted
Chernoff bound for weighted sums of Bernoulli random variables
Your bound (at least when $t\le E[S]$) seems to follow from the standard multiplicative Chernoff bound, as follows.
Lemma 1. (a standard multiplicative Chernoff bound) Let $S$ be the sum of ...
- 9,595
2
votes
$\rho OPT + k$ approximation for bin packing (Unpublished result of David P. Williamson)
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 ...
- 1,058
1
vote
Sample Complexity for Order Statistics
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$ ...
1
vote
Janson-type inequality, limited dependence
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 ...
- 203
Only top scored, non community-wiki answers of a minimum length are eligible