The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
104 views

How to derandomize the Chernoff bound?

Avi Wigderson have a paper on how to derandomize the matrix-valued Chernoff bound. I would like to know whether there exists a simple version of paper on how to derandomize the real-valued Chernoff ...
4
votes
0answers
123 views

Sums of products of bernoulli random variables

Let $x_1 \ldots x_a,y_1 \ldots y_b$ be independent random variables taking values +1 or -1. Consider the sum $$S = \sum_{i,j} x_iy_j.$$ I wish to upper bound the probability $P(|S| > t)$. The ...
7
votes
1answer
529 views

Sum of Independent Exponential Random Variables

Can we prove a sharp concentration result on the sum of independent exponential random variables, i.e. Let $X_1, \ldots X_r$ be independent random variables such that $Pr(X_i < x) = 1 - ...
5
votes
0answers
121 views

Squares of random binary matrices

Are there results/techniques pertaining to the analysis of squares of random matrices ? More specifically, let $A$ be an $n\times n$ matrix such that each entry is $1$ or $-1$ independently and with ...
3
votes
0answers
85 views

Concentration Bounds for Dependent Rounding

Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$: At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its ...
1
vote
2answers
198 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. ...
12
votes
4answers
745 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
260 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
3answers
1k 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
340 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 ...
12
votes
3answers
937 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
463 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 ...