3
$\begingroup$

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$. Then $$\Pr\left\{\left| \frac{1}{K} \sum_{i=1}^K X_i - \mu \right| > \epsilon \right\} \le 2 e^{-K \epsilon^2 / 2 b^2}.$$

I am interested in a generalization where the $X_i$ are instead complex valued. What modifications need to be made to the right hand side of the above inequality? I can get $4e^{-K \epsilon^2 / 4 b^2}$ by applying the real-valued version to each of the real and imaginary parts, but can I do better? I found an article on vector valued martingales that can be applied to give $2e^2 e^{-K \epsilon^2 / 2 b^2}$ if $\mu=0$ but I don't want to make that assumption (I can shift the $X_i$ by the mean to make $\mu=0$, but this would incur the penalty of increasing $b$).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Here's a quick idea, haven't checked if I am oversimplifying.

Represent each of your complex numbers as $2\times 2$ matrices, e.g., for $z = a+ib$ we have the representation $$Z := \begin{pmatrix} a & b\\\\ -b & a \end{pmatrix}.$$

Notice that $\|Z\| = |z| = \sqrt{a^2 + b^2}$.

Now, apply the Matrix Chernoff Bound or whatever other matrix style concentration inequality you prefer to get a quick generalization. But I am not sure if this gives the "tightest" possible generalization, but seems to work.

Improve this answer
$\endgroup$
4
  • $\begingroup$ PS: It seems to me that even from this generalization, you'll get a factor of $4$ on the rhs, but maybe it is possible to reduce that factor to $2$.... $\endgroup$
    – Suvrit
    Commented Mar 13, 2013 at 17:51
  • $\begingroup$ An interesting proposition. I can make that matrix Hermitian by putting it in the upper right corner of a $4 \times 4$ matrix and its adjoint in the lower left corner. The problem then is that the bounds all seem to require either positive matrices or a zero expectation value. These can be fixed by adding a multiple of identity to the matrix, but at the expense of increasing the norm. I didn't go through all the inequalities, but it seems most of them still have a 4 or worse in the exponent. $\endgroup$
    – Dan Stahlke
    Commented Mar 14, 2013 at 21:25
  • $\begingroup$ The rectangular case (right before the Matrix Azuma) does not require the matrices to be positive def. or self-adjoint, but then takes a product $BB^\ast$, and thereafter ends up having a factor $4$ on the rhs. So I am confused as to why you are thinking of making it $4\times 4$? $\endgroup$
    – Suvrit
    Commented Mar 14, 2013 at 22:15
  • $\begingroup$ You are right, that one doesn't require positive matrices. I was making the $4 \times 4$ matrix in order to consider the other inequalities on that page. It is also possible to put the real and imaginary parts on the diagonal of a $2 \times 2$ matrix, but again it doesn't seem to improve the bound. $\endgroup$
    – Dan Stahlke
    Commented Mar 15, 2013 at 3:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .