Questions tagged [chernoff-bound]
The chernoff-bound tag has no usage guidance.
26
questions
0
votes
0
answers
51
views
Approximation ratio of randomized rounding for integral multi-commodity flow
In [1], Raghavan and Thompson showed that we can use randomized rounding to approximate integral multi-commodity flow and routing with congestion. The result is that suppose the optimal solution is $W$...
- 33
2
votes
1
answer
228
views
Additive chernoff bound
From wikipedia,
Additive form (absolute error)
The following theorem is due to Wassily Hoeffding and hence is called the Chernoff-Hoeffding theorem.
Chernoff-Hoeffding theorem.
Suppose $X_1, \ldots, ...
- 109
0
votes
0
answers
53
views
Amplifying success probability for PTMs with $poly(n) / \exp(n)$ gap?
The following is a well-known result of BPP in complexity theory, e.g., Theorem 1 and its proof from here:
Consider a probabilistic Turing Machine (PTM) $M$, and a language $L \in BPP$:
If $x \in L$ (...
2
votes
1
answer
358
views
Chernoff bound for weighted sums of Bernoulli random variables
I tried to prove the following Chernoff-type bound when doing research, and found that it is of indepent interest.
Let $X_1, \dots, X_n$ be independent random varibles such that each $X_i$ is a ...
- 23
1
vote
0
answers
247
views
Converse form of Chernoff bound
Suppose $X_1,\ldots,X_n$ are i.i.d. random variables, all with mean $p$, and we have the statement that $\Pr\left[\sum_i X_i\geq 0.8n\right]\geq 0.9$, can we use this to conclude anything about $p$ (...
- 251
5
votes
1
answer
261
views
$\rho OPT + k$ approximation for bin packing (Unpublished result of David P. Williamson)
I am currently stuck on Exercise 5.12 in this book, which is apparently an unpublished result of David P. Williamson according to the book notes.
The problem asks to use randomized rounding and first ...
- 1,153
2
votes
1
answer
502
views
How to use a 𝑝-coin so a TM can decide an undecidable language in polynomial time? [closed]
In "Computational complexity- A modern approach" book (page 117) for the lemma 7.12 (following) the author mentioned that if the ρ is efficiently computable ρ-coin cannot give probabilistic algorithm ...
- 29
2
votes
1
answer
135
views
Sample Complexity for Order Statistics
I have a sample complexity question which seems fairly basic, but for which I'm having trouble finding a reference.
Let $F$ be an unknown distribution over $[0,1]$. Denote by $X_{k:n}$ the $k$th of $...
- 21
4
votes
1
answer
295
views
Janson-type inequality, limited dependence
So I am trying to figure out an upper bound on the probability of the following...
This is a question related to a problem I am working on (not for a class, just for fun)
Let $\Omega=\{X_{1},\dots,...
- 203
1
vote
0
answers
101
views
Concentration Bounds for functions of matrices
This is a question about properties of large directed graphs which are preserved when we randomly sample edges.
Imagine I have an infinite sequence of positively weighted directed graphs. The ...
- 617
1
vote
1
answer
810
views
Differential Privacy and Randomized Responses for Counting Queries
I'm trying to understand a basic randomized response mechanism for differential privacy (concrete definition not relevant for the question), but I have some trouble understanding the last step in the ...
- 217
5
votes
1
answer
1k
views
Orlicz norm of random variable and variance
In probability and statistics Orlicz norms are frequently used in concentration inequalities. For example, for Bernstein's inequality, we have versions for sub-exponential random variables using $\...
- 852
2
votes
1
answer
262
views
Evaluating the expected value of negatively correlated random variables
A polynomial random process satisfying the following properties converts a fractional point $(x_1, x_2, \ldots, x_n) \in \mathcal{P}$, $(x_i \in [0,1])$ to a random integer point $(X_1, X_2, \ldots, ...
- 93
5
votes
0
answers
133
views
Tools to bound the singular values of a finite sum of random matrices from below?
Matrix Chernoff bounds (see also this arXiv paper) are usually used to give upper bounds on the largest eigenvalue of a finite sum of random matrices. Sometimes it can also be used to give a lower ...
- 179
1
vote
0
answers
346
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 ...
- 11
4
votes
0
answers
250
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 ...
- 666
13
votes
2
answers
3k
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 - e^{-x/\...
- 666
6
votes
0
answers
185
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 ...
- 666
4
votes
0
answers
161
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 ...
- 271
1
vote
2
answers
2k
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. ...
- 666
36
votes
6
answers
7k
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 ...
- 1,584
3
votes
1
answer
398
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 ...
- 131
14
votes
3
answers
3k
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 ...
- 151
9
votes
2
answers
654
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 ...
- 4,701
16
votes
3
answers
3k
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 ...
- 161
15
votes
1
answer
2k
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) ...
- 445