The chernoff-bound tag has no wiki summary.
1
vote
2answers
96 views
Chernoff Bounds for settings with limited dependence
Could someone point me to a way of bounding the tail probability of sums of bernoulli variables each generated by the same distribution but the condition of independence is only partially satisfied. ...
11
votes
4answers
387 views
Reverse Chernoff bound
Is there an reverse Chernoff bound which bounds that the tail probability is at least so much.
i.e if $X_1,X_2,\ldots,X_n$ are independent binomial random variables and $\mu=\mathbb{E}[\sum_{i=1}^n ...
3
votes
1answer
193 views
Estimator for sum of independent and identically distributed (iid) variables
This is a repost of a question at math.stackexchange, but I was told by a reliable source that people around here might be able to help me, so I thought I'd give it a shot.
Consider the Chernoff ...
12
votes
2answers
580 views
An extension of Chernoff bound
I am looking for a reference (not a proof, that I can do) to the following extension of Chernoff.
Let $X_1,..,X_n$ be Boolean random variables, not necessarily independent.
Instead, it is guaranteed ...
9
votes
2answers
296 views
Chernoff-type inequality for random variable with 3 outcomes
Suppose we have a random variable which takes non-numeric values a,b,c and want to quantify how empirical distribution of $n$ samples of this variable deviates from true distribution. The following ...
11
votes
3answers
767 views
Chernoff-type Inequality for pair-wise independent random variables
Chernoff-type inequalities are used to show that the probability that a sum of independent random variables deviates significantly from its expected value is exponentially small in the expected value ...
9
votes
1answer
355 views
Chernoff bound for weighted sums
Consider $X = \sum_i \lambda_i Y_i^2$, where lambda_i > 0 and Y_i is distributed as a standard normal. What kind of concentration bounds can one prove on X, as a function of the (fixed) coefficients ...
