26
$\begingroup$

Fix an integer $n\geq 2$. Suppose we start at the origin in the complex plane, and on each step we choose an $n^{th}$ root of unity at random, and go $1$ unit distance in that direction. Let $X_N$ be distance from the origin after the $N^{th}$ step. How well can we bound $E(X_N)$ from above?

In my attempt to calculate this, I found the bound $\sqrt{N}$, but I have a feeling this could be wrong because the problem I am applying this to has instead $\sqrt{N\log N}$. (This reasoning is based on the belief that the problem is likely optimal) What I did was apply Cauchy Schwarz to get a sum with the norm squared, and then try to do some manipulations from there, relying on the fact that the sum of the vectors (not the distance) is zero by symmetry.

  • 0
    @Srivatsan: Yes, thanks for pointing this out, I edited accordingly.2012-01-15
  • 6
    For $n=2$ this is an ordinary one-dimensional random walk, in which case $E(X_N)$ is well known to go towards $\sqrt{\frac{2}{\pi}N}$. So $\sqrt{N\log N}$ certainly grows too fast.2012-01-15

2 Answers 2

23

Srivatsan has given a very fine answer, with a simple, elegant analysis. With a little more work, we can sharpen the result.

Claim: For $n \geq 3$, $\mathbb E X_N \sim \sqrt{\frac{\pi}{4} N}$ .

We can analyze this by means of the central limit theorem and the continuous mapping theorem. Below is just a sketch. We have restricted ourselves to the case $n \geq 3$ since the case $n = 2$ corresponds to the standard simple random walk, which has slightly different behavior (cf. Henning's comment). Intuitively, since for $n \geq 3$, the random walk can wiggle in an extra dimension, we should anticipate that its expected norm might grow slightly faster.

Proof (sketch):

Let $Z_i = (R_i,I_i)$, $i=1,2,\ldots$, be an iid (uniform) sample of the roots of unity where $R_i$ indicates the "real" component and $I_i$ the "imaginary" component of the $i$th element of the sample. Then, it is a simple exercise to verify that $\mathbb E R_i = \mathbb E I_i = 0$, and, also, $\mathbb E R_i I_i = 0$. Furthermore, $$ \mathrm{Var}(R_i) = \mathrm{Var}(I_i) = 1/2 \>, $$ independently of $n$, using simple properties of the roots of unity.

Hence, by the multivariate central limit theorem, we have that $$ \sqrt{2N} (\bar{R}_N, \bar{I}_N) \xrightarrow{d} \,\mathcal \,N(0,\mathbf I_2 ) \> , $$ where $\bar{R}_N = N^{-1} \sum_{i=1}^N R_i$ and likewise for $\bar{I}_N$. Here $\mathbf I_2$ denotes the $2 \times 2$ identity matrix.

An application of the continuous mapping theorem using $g(x,y) = x^2 + y^2$ yields $$ 2 N (\bar{R}_N^2 + \bar{I}_N^2) = \frac{2}{N} X_N^2 = g( \sqrt{2N} \bar{R}_N, \sqrt{2N} \bar{I}_N ) \,\xrightarrow{d}\, \chi_2^2 \> . $$

That is, the rescaled squared norm has a limit distribution which is chi-squared with two degrees of freedom.

The square-root of a $\chi_2^2$ distribution is known as a Rayleigh distribution and has mean $\sqrt{\pi/2}$.

Hence, by a second application of the continuous mapping theorem, $\sqrt{\frac{2}{N}} X_N$ converges to a Rayleigh distribution.

This strongly suggests (but does not prove) that $\mathbb E X_N \sim \sqrt{\frac{\pi}{4} N}$.

To finish the proof, note that $\mathbb E \frac{2}{N} X_N^2 = 2$ for all $N$. By a standard theorem in probability theory, there exists a sequence of random variables $\{Y_N\}$ such that $Y_N \stackrel{d}= \sqrt{\frac{2}{N}} X_N$ and $Y_N$ converges to $Y_\infty$ almost surely, where $Y_\infty$ is a standard Rayleigh. By the uniformity of the second moment above, we know that the set $\{Y_N\}$ is uniformly integrable and so $L_1$ convergent. So, $$ \mathbb |\mathbb E Y_N - \mathbb E Y_\infty| \leq \mathbb E |Y_N - Y_\infty| \to 0 \> . $$

Hence $\mathbb E Y_N = \mathbb E X_N \sim \sqrt{\frac{\pi}{4} N}$ as desired.

  • 0
    Ha, once again 2 sticks out from the rest of the numbers! :-) (+1)2012-01-16
  • 0
    +1, This is excellent, I didn't know we could actually derive the asymptotic.2012-01-16
  • 1
    +1. (But this is more than a *sketch* of the proof...)2012-01-16
  • 0
    @EricNaslund: Let me know if anything is unclear and I can attempt to clarify it. I'd be interested to know a little about the application. Cheers. :)2012-01-16
  • 0
    @Cardinal: Can you also calculate higher moments with this approach, or do you need to do something very different?2012-01-16
  • 0
    @EricNaslund: As long as you can show, e.g., uniform integrability (u.i.) of the right collection of random variables, then an essentially identical proof will work. For example, suppose you are interested in $\mathbb E X_N^p$ for some $p > 0$. If there is a sequence of constants $c_{p,N}$ such that $\{c_{p,N} X_N^p\}$ is u.i. and $c_{p,N} X_N^p \to Y_{p,\infty}$ in distribution for some random variable $Y_{p,\infty}$ then, you are set. A natural conjecture for the choice of $c_{p,N}$ is $(2/N)^{p/2}$. In this case, the continuous mapping theorem will give a limiting random variable.../...2012-01-16
  • 0
    .../...that is equal in distribution to the $p/2$ power of a $\chi_2^2$ random variable. I have not checked, but I believe a closed-form expression for the mean of such a random variable is likely to exist for integral $p$. You can either check the u.i. property by the definition or by showing that $\sup_N\; \mathbb E c_{p,N}^{1+\delta} X_N^{p+\delta} < \infty$ for some $\delta > 0$. The latter approach is often easier. (I showed it above by taking $\delta = 1$.)2012-01-16
  • 0
    @EricNaslund: You should look at the Marcinkiewicz-Zymund inequalities which should help you easily establish uniform integrability, particularly since your random-variables are bounded. I think this plus maybe another couple bound manipulations will finish it off for arbitrary finite powers of $X_N$.2012-01-19
26

I get the same $\sqrt{N}$ bound.

Let the $k$-th step be $z_k$ (an $n$-th root of unity), so that the position at time $N$ is $z_1 + \cdots + z_N$. The square of the distance from the origin at time $N$ is $$ X_N^2 = \left( \sum_{k=1}^{N} \overline{z_k} \right) \cdot \left( \sum_{j=1}^{N} z_j \right) = \sum_{k=1}^{N} | z_{k} |^2 + \sum_{k \ne j} \overline{z_k} \cdot z_j = N + \sum_{k \ne j} \overline{z_k} \cdot z_j. $$ Since each summand $\overline {z_k} \cdot z_j$ (for $k \ne j$) vanishes in expectation, we get $\mathbf E[X_N^2] = N$. Finally $$\mathbf EX_N \leqslant \sqrt{ \mathbf E[X_N^2] } = \sqrt{N} .$$

This settles that $\mathbf EX_N$ is asymptotically $O(\sqrt{N})$, but the resulting constant is most likely not tight since the approximation in the final step is rather crude (for any finite $n$).

  • 0
    It seems the last $(\cdot)^{1/2}$ is on the outside of the expectation (as a consequence of Jensen's inequality). However, from the current typesetting, that's not entirely clear.2012-01-15
  • 1
    @cardinal, Thanks, I have now made the final inequality clearer. (Your interpretation is absolutely right.)2012-01-15
  • 0
    @Sritvatsan: +1, Very good, this is close to I did, but the way you wrote it is much cleaner and nicer. One question, you say the approximation is crude at some point, at which point is that? You seem to have inequalities and equalities throughout, so doesn't the upper bound $\sqrt{N}$ follow?2012-01-16
  • 0
    @Eric: The upper bound is *correct*. What I meant is that I do not expect it to be *tight* (in the sense that $\mathbf E X_N \leqslant c \sqrt{N}$ for some $c < 1$).2012-01-16
  • 0
    @Srivatsan: Ahhh of course, thanks!2012-01-16
  • 0
    @Srivatsan: Do you have a nice way to see why each summand $\overline{z_k}\cdot z_j$ vanishes in the expectation?2012-01-16
  • 0
    @Eric: I thought the claim was clear, which is why I skipped justifying it. First, by independence, $\mathbf E [\overline{z_k} \cdot z_j] = \mathbf E [\overline{z_k}] \cdot \mathbf E[z_j]$ for $k \ne j$. The claim then follows from noting that $\mathbf E [\overline{z_k}] =\mathbf E[z_j] = 0$. (I hope I am not missing something here; do let me know if this looks ok :))2012-01-16
  • 0
    @Srivatsan: That was what I was thinking, but the problem I had was it also seemed to give $0$ when we set $k=j$, and if $k=j$..... but then we can't factor the expectation as we did for $k\neq j$. Ok I see now, all good, thanks!2012-01-16
  • 0
    @Eric: Precisely. In case this clarification helps: This situation is entirely analogous to (e.g.) the proof that the variance of a sum of $N$ independent random variables is equal to the sum of their variances.2012-01-16
  • 0
    @Eric: [I thought you had written a comment about computing the higher moments of $X_N$, but maybe my memory is tricking me.] As far as I can see, the even moments can be computed (exactly) by an extension of this method, although you may not find a simple closed-form expression. [Some "combinatorics" will be involved because we are interested in how many terms of the resulting summation survive.] Also I presume we should be able to find the asymptotics of $X_N^{2k}$ for large $k$ as well. The odd moments are a different story though.2012-01-16