2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The central limit theorem (en.wikipedia.org/wiki/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. $\endgroup$
    – Erik Aas
    Feb 25 '12 at 13:12
  • $\begingroup$ Here is a similar (recent) question at math.SE, though they were interested in the asymptotics of the expected value $\mathbf E M_n$: math.stackexchange.com/questions/99389 $\endgroup$
    – cardinal
    Feb 25 '12 at 23:28
  • $\begingroup$ To be precise, so as not to mislead, the above-referenced link uses a different (but related) distribution for the $Z_i$. $\endgroup$
    – cardinal
    Feb 25 '12 at 23:45
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ But how I can apply Hoeffding's inequality? It is true only for real random variables, not complex. $\endgroup$ Feb 25 '12 at 13:39
  • $\begingroup$ 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. $\endgroup$ Feb 25 '12 at 14:22
  • $\begingroup$ Apply Hoeffding's inequality to the real and imaginary parts separately. $\endgroup$ Feb 26 '12 at 0:34
2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Feb 25 '12 at 14:07
  • 1
    $\begingroup$ 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+ϵ)})$. $\endgroup$ Feb 25 '12 at 15:58
  • $\begingroup$ 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). $\endgroup$
    – cardinal
    Feb 25 '12 at 23:25
  • $\begingroup$ 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. $\endgroup$ Feb 26 '12 at 22:37
  • $\begingroup$ @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. $\endgroup$
    – cardinal
    Feb 27 '12 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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