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.

Improve this question
$\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
    Commented Feb 25, 2012 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
    Commented Feb 25, 2012 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
    Commented Feb 25, 2012 at 23:45

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ But how I can apply Hoeffding's inequality? It is true only for real random variables, not complex. $\endgroup$
    – Richard Bonne
    Commented Feb 25, 2012 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$
    – Douglas Zare
    Commented Feb 25, 2012 at 14:22
  • $\begingroup$ Apply Hoeffding's inequality to the real and imaginary parts separately. $\endgroup$
    – Brendan McKay
    Commented Feb 26, 2012 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})$.

Improve this answer
$\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$
    – Richard Bonne
    Commented Feb 25, 2012 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$
    – Douglas Zare
    Commented Feb 25, 2012 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
    Commented Feb 25, 2012 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$
    – Douglas Zare
    Commented Feb 26, 2012 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
    Commented Feb 27, 2012 at 15:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .