Questions tagged [chernoff-bounds]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
23 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 ?
0
votes
0answers
20 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 ...
3
votes
1answer
280 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 ...
1
vote
1answer
86 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. ...
6
votes
1answer
160 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$. ...
5
votes
2answers
115 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 ...
-1
votes
1answer
607 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
0answers
49 views

Proving a randomized algorithm that sums array elements

I am trying to prove the following algorithm to be correct: ...
4
votes
1answer
101 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 ...
3
votes
1answer
203 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 ...
3
votes
1answer
71 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 ...
2
votes
0answers
104 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 ...
6
votes
1answer
787 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<\...
3
votes
1answer
220 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}}, ...
2
votes
1answer
986 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 ...
2
votes
1answer
839 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 ...