Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [chernoff-bounds]

questions about concentration inequalities for sum of independent random variables, martingales, and their applications

Filter by
Sorted by
Tagged with
2 votes
0 answers
191 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 ...
Symbol 1's user avatar
1 vote
0 answers
41 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(...
Win_odd Dhamnekar's user avatar
2 votes
0 answers
77 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 ...
Harry Vinall-Smeeth's user avatar
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|\...
Aris Konstantinidis's user avatar
2 votes
0 answers
126 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=...
spektr's user avatar
  • 453
1 vote
1 answer
72 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. ...
Sid Meier's user avatar
  • 249
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 ?
Aex's user avatar
  • 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 ...
Aex's user avatar
  • 17
3 votes
1 answer
395 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 ...
Alex's user avatar
  • 31
2 votes
1 answer
482 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. ...
e_noether's user avatar
  • 1,319
6 votes
1 answer
175 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$. ...
Matteo's user avatar
  • 63
5 votes
2 answers
261 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 ...
Jeff Cooper's user avatar
-1 votes
1 answer
780 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 ...
Yaniv Tzur's user avatar
1 vote
0 answers
93 views

Proving a randomized algorithm that sums array elements

I am trying to prove the following algorithm to be correct: ...
user2566415's user avatar
4 votes
1 answer
252 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 ...
user341502's user avatar
3 votes
1 answer
228 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 ...
Matan L's user avatar
  • 143
3 votes
1 answer
119 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 ...
Soheil's user avatar
  • 33
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 ...
Mugen's user avatar
  • 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<\...
mba's user avatar
  • 375
3 votes
1 answer
284 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<\...
mba's user avatar
  • 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 ...
user3367692's user avatar
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 ...
zpavlinovic's user avatar
  • 1,654