MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hello everybody. I'm working about asymptotic estimates of

$M_n = \left|\sum_{k=1}^n Z_k\right|$

where $Z_1, Z_2, \ldots$ are independent uniformly distributed random variables on the complex unit circle. I found that the expectation $\textbf{E}[M_n^2] = n$ and the variance $\textbf{Var}[M_n^2] = n^2 - n$, so with Chebyshev's inequality I concluded that $M_n = o(n)$ almost surely as $n \to \infty$.

It is possible to improve this estimate? I need something like $M_n = O(\sqrt{n})$ or $M_n = O(n^{1/2 + \varepsilon})$. Thanks.

share|cite|improve this question
The central limit theorem ( ) applied to the real and imaginary parts of \sum _k Z_k shows these are normally distributed and independent. From this it should be easy to show $M_n = O(\sqrt n )$ with high probability. – Erik Aas Feb 25 '12 at 13:12
Here is a similar (recent) question at math.SE, though they were interested in the asymptotics of the expected value $\mathbf E M_n$: – cardinal Feb 25 '12 at 23:28
To be precise, so as not to mislead, the above-referenced link uses a different (but related) distribution for the $Z_i$. – cardinal Feb 25 '12 at 23:45

This is a classical random walk in the plane, extensively studied wrt Brownian motion etc.. Other people here are more expert in the subject than I am, so I'll leave it for them to provide you with references.

Also, because the summands are bounded, you can apply Hoeffding's inequality or similar to find strong tail bounds.

share|cite|improve this answer
But how I can apply Hoeffding's inequality? It is true only for real random variables, not complex. – Richard Bonne Feb 25 '12 at 13:39
If $M_n$ is large, then either the real or imaginary part of the sum is large (up to a factor of $\sqrt 2$). If $M_n$ is large infinitely often, then either the real or imaginary part is large infinitely often. – Douglas Zare Feb 25 '12 at 14:22
Apply Hoeffding's inequality to the real and imaginary parts separately. – Brendan McKay Feb 26 '12 at 0:34

$O(\sqrt n)$ is too much to ask, and it fails almost surely. The law of the iterated logarithm says the real and imaginary parts are a. s. $O(\sqrt{n \log \log n})$ so with probability $1$, $M_n$ is $O(\sqrt{n \log \log n})$.

share|cite|improve this answer
OK, then I give up to prove $M_n = O(\sqrt{n})$, however I would be happy if there was I simpler proof that $M_n = o(n)$, which avoids the central limit theorem and the law of the iterated logarithm. – Richard Bonne Feb 25 '12 at 14:07
If you are allergic to the CLT and law of the iterated logarithm, then (as Brendan McKay points out) you can use Hoeffding's inequality on the real and imaginary parts. This gives you exponentially decaying tail bounds which will let you prove a. s. $M_n=O(n^{(1/2+ϵ)})$. – Douglas Zare Feb 25 '12 at 15:58
Maybe I am misunderstanding the question, but I don't see why the CLT or the LIL should be necessary to establish $M_n = o(n)$. This is an immediate consequence of the SLLN (and an application of the continuous mapping theorem). – cardinal Feb 25 '12 at 23:25
Yes, the strong law of large numbers also establishes that with probability $1$, $M_n = o(n).$ You need something more to get a better bound. – Douglas Zare Feb 26 '12 at 22:37
@Douglas, sorry. Yes, I know that, of course. My remark was directed at the OP's comment in search of a "simpler" proof that $M_n = o(n)$ almost surely. – cardinal Feb 27 '12 at 15:27

Your Answer


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.