Questions tagged [chernoff-bounds]
questions about concentration inequalities for sum of independent random variables, martingales, and their applications
21
questions
0
votes
0
answers
30
views
Chernoff bounds using importance sampling identity
How to use importance sampling identity to obtain the Chernoff bounds as given below?
Let X have moment generating function $\phi(t)= E[e^{tX}]$. Then, for any c > 0 ,
$P[X\geq c ]\leq e^{-tc} \phi(...
2
votes
0
answers
75
views
Distribution of $k$-matchings in a random graph
Take the Erdos-Renyi random graph $G(n,p)$, i.e. the random graph with $n$ vertices and where each possible edge has an independent probability of $p$ of being present. Recall that a $k$-matching is a ...
0
votes
0
answers
23
views
Probability Estimation with Chernoff Bound
Let's say there is an unfair coin with $P[head]=p$. We do not now $p$ but we know that $p \geq a$ for a known $a$. After $n$ trials we get $bn$ heads. Now, we want to estimate $p$ so that
$P[|p-b|\...
2
votes
0
answers
121
views
Concentration inequality of sum of geometric random variables taken to a power
Let $X_1, \cdots, X_n$ be $n$ independent geometric random variables with success probability parameter $p = 1/2$, where $X_i = j$ means it took $j$ trials to get the first success. Let $S_d = \sum_{i=...
- 453
1
vote
1
answer
68
views
Computational indistinguishability for any distribution using a Chernoff bound
I had a question about a general statement regarding finding a computationally indistinguishable distribution given any distribution, observed (in the third paragraph of Section 11, page 31) here. ...
- 229
0
votes
0
answers
33
views
Chernoff Bounds (upper tail)
For the proof of Chernoff Bounds (upper tail) we suppose δ<2e−1 .
Like in this paper ([see this link ]) 1. Can you tell me why ?
- 17
0
votes
0
answers
22
views
Find expectation and calculate Chernoff bound [duplicate]
We have a group of employees and their company will assign a prize to as many employees as possible by finding the ones probably better than the rest. The company assigned the same 2 tasks to every ...
- 17
3
votes
1
answer
383
views
Find expectation with Chernoff bound
We have a group of employees and their company will assign a prize to as many employees as possible by finding the ones probably better than the rest. The company assigned the same $2$ tasks to every ...
- 31
1
vote
1
answer
432
views
Can BPP be bounded around any constant other than 1/2?
A language $L$ is in BPP if there exists a randomised TM such that it outputs a correct answer with probability at least $1/2+1/p(n)$ for some polynomial $p(n)$, where $n$ is the length of the input. ...
- 1,269
6
votes
1
answer
173
views
Chernoff-Hoeffding bounds for the number of nonzeros in a submatrix
Consider a $n \times n$ matrix $A$ with $k$ nonzero entries. Assume every row and every column of $A$ has at most $\sqrt{k}$ nonzeros. Permute uniformly at random the rows and the columns of $A$. ...
- 63
5
votes
2
answers
247
views
Chernoff-like Concentration Bounds on Permutations
Suppose I have $n$ balls. Among them, there are $m \leq n$ black balls and the other $n - m$ balls are white. Fix a random permutation $\pi$ over these balls and denote by $Y_i$ the number of black ...
- 73
-1
votes
1
answer
742
views
Applying a Chernoff bound with Only an Upper Bound of the Expectation
First, I am aware at least one or two similar questions have already been asked on stack exchange, but I've gone through the answers they got and didn't find one that was satisfactory for my case.
The ...
1
vote
0
answers
88
views
Proving a randomized algorithm that sums array elements
I am trying to prove the following algorithm to be correct:
...
- 11
4
votes
1
answer
219
views
Chernoff bound when we only have a lower bound of expecation
This question: Chernoff bound when we only have upper bound of expectation is similar, but for an upper bound of expectation.
The standard Chernoff bound says that is $X$ is a sum of 0/1 random ...
- 143
3
votes
1
answer
224
views
Reducing randomness needed by turing machine
I am reading an article related to streaming algorithms named "Turnstile streaming algorithms might as well be linear sketched" by Yi Li, Huy Nguyen and David Woodruff,
At some point they have a ...
- 143
3
votes
1
answer
113
views
Sampling from a set of numbers with a fixed sum
Let $s = \{x_1, x_2, \ldots, x_n\}$ be a set of $n$ random non-negative integers where $\sum_i x_i = n$. And let $\{y_1, y_2, \ldots, y_{\sqrt{n}}\}$ denote a subset of size $\sqrt{n}$ of $s$, chosen ...
- 33
2
votes
0
answers
121
views
Prove $\forall a>0.BPP[{a,a+\frac{1}{n}}]=BPP$
I need to prove that
$\forall a>0.BPP[{a,a+\frac{1}{n}}]=BPP$
$BPP[a,b]$ definition:
A language L is in BPP(a,b) if and ...
- 121
7
votes
1
answer
1k
views
Chernoff bound when we only have upper bound of expectation
If $X$ is a sum of i.i.d. random variables taking values in $\{0,1\}$ and $E[X]=\mu$, the Chernoff bound tells us that
$$\Pr(X\geq (1+\delta)\mu)\leq e^{-\frac{\delta^2\mu}{3}}$$
for all $0<\...
- 375
3
votes
1
answer
276
views
"Practical forms" of Chernoff bound for inequality in expectation
From Wikipedia:
The above formula is often unwieldy in practice, so the following looser but more convenient bounds are often used:
(i) $Pr(X\geq (1+\delta)\mu)\leq e^{-\frac{\delta^2\mu}{3}}, 0<\...
- 375
3
votes
1
answer
2k
views
Expected maximum bin load, for balls in bins with equal number of balls and bins [closed]
Suppose we have $n$ balls and $n$ bins. We put the balls into the bins randomly. If we count the maximum number of balls in any bin, the expected value of this is $\Theta(\ln n/\ln\ln n)$. How can we ...
- 31
2
votes
1
answer
1k
views
Chernoff bounds and Monte Carlo algorithms
One of Wikipedia examples of use of Chernoff bounds is the one where an algorithm $A$ computes the correct value of function $f$ with probability $p > 1/2$. Basically, Chernoff bounds are used to ...
- 1,644