Questions tagged [chernoff-bounds]
questions about concentration inequalities for sum of independent random variables, martingales, and their applications
9
questions with no upvoted or accepted answers
2
votes
0
answers
187
views
Chernoff bound on the maximum of multinomial distribution
I am reading some heavy hitter (HH) papers
when I run into the following reduction theorem.
The theorem attempts to reduce
an HH problem with a very small tail frequency $\epsilon$
to multiple HH ...
- 71
2
votes
0
answers
76
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 ...
2
votes
0
answers
125
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
2
votes
0
answers
122
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
1
vote
0
answers
91
views
Proving a randomized algorithm that sums array elements
I am trying to prove the following algorithm to be correct:
...
- 11
0
votes
0
answers
34
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(...
0
votes
0
answers
28
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|\...
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
-1
votes
1
answer
768
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 ...
