# 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$. 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$).

-

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.

-
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$.... – Suvrit Mar 13 '13 at 17:51
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. – Dan Stahlke Mar 14 '13 at 21:25
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$? – Suvrit Mar 14 '13 at 22:15
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. – Dan Stahlke Mar 15 '13 at 3:03