# Questions tagged [chernoff-bounds]

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

13 questions
Filter by
Sorted by
Tagged with
56 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. ...
159 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$. ...
100 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 ...
548 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 ...
46 views

### Proving a randomized algorithm that sums array elements

I am trying to prove the following algorithm to be correct: ...
85 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 ...
197 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 ...
67 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 ...
102 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 ...
695 views

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<\... 1answer 194 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}}, ...
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 ...
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 ...