3
votes
1answer
220 views

Chernoff-Hoeffding bound for complex values

Consider the Chernoff-Hoeffding bound, stated as follows: Let $X_1, \dots, X_K$ be i.i.d. real-valued random variables with expectation value $\mu$ and satisfying $|X_i| \le b$. Let $\epsilon > 0$. ...
2
votes
1answer
240 views

concentration inequality for averages of dependent random variables

Let $X \in R^n$ be a random vector such that $$P(|X_i| > \epsilon) \le e^{-\epsilon^2}$$ What is a tight bound on $$P(\sum_{i=1}^n |X_i| > \epsilon)$$ and on $$P(\max_{1\le i\le n} |X_i| ...
1
vote
0answers
131 views

A Multiplicative version of McDiarmid's Inequality like the one of Chernoff-Hoeffding Bounds

McDiarmid's Inequality basically says the following: Let $X_1, X_2, X_3, \ldots, X_n$ denote independent random variables and $f$ is a function of $n$ real arguments. If changing the value of the ...