Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.