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

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}$.
• 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