# The mean square distance of a random walk from the origin

I'm wondering whether the following type of problem is a standard one that has been studied by probabilists. The particular case needed (as a lemma that would help with a Polymath project) isn't quite what I'm asking here, but I'll ask a simpler case, since I don't think the case we actually need is significantly different.

Take a standard $n$-step random walk in $\mathbb Z$ (so it starts at the origin and at each step goes right with probability 1/2 and left with probablity 1/2). Let $X_m$ be where the walk has reached after $m$ steps. I am interested in the quantity $\sum_m X_m^2$. The distribution of $X_m$ is roughly normal with standard deviation of order $\sqrt m$, from which it follows easily that the expected value of this quantity has order $n^2$. I would like to prove that the probability that $\sum_mX_m^2\leq c^2n^2$ is, for suitably small $c$, extremely small. For the application I have in mind, it would be enough if "extremely small" meant "with probability at most $n^{-10}$" or something like that, and I'm prepared for $c$ to depend on $n$, as long as it doesn't tend to zero too quickly.

In fact, I think it is necessary for $c$ to tend to zero, because I think that for any fixed $c$ the probability that the $n$-step random walk is always between $-c\sqrt n$ and $c\sqrt n$ is positive. (I wouldn't mind a reference for that actually.) But a heuristic argument that I won't give here suggests that that positive probability depends exponentially on $c$, so I would expect to be OK once $c\ll 1/\log n$.

• Doesn't the law of the iterated logarithm say that the probability that you remain between $-\sqrt n$ and $\sqrt n$ for $n$ steps converge to 0 as $n$ approaches $\infty$? (or did I misunderstand the last paragraph?) – Anthony Quas Jun 19 '17 at 17:47
• Anthony: I presume OP means that the probability that the walk stays between $-c\sqrt{n}$ and $c\sqrt{n}$ throughout its first $n$ steps is bounded away from $0$ as $n\to\infty$. @gowers: for this you can for example use Donsker's theorem en.wikipedia.org/wiki/Donsker%27s_theorem (i.e. convergence of rescaled random walk to Brownian motion) and the continuous mapping theorem en.wikipedia.org/wiki/Continuous_mapping_theorem: the probability converges as $n\to\infty$ to $P(\max_{0\leq t\leq 1} |B_t|<c)$ where $B$ is a standard Brownian motion. – James Martin Jun 19 '17 at 19:11
• I'm confused: why isn't James Martin contradicting Anthony Quas here? When I wrote "I think that" I meant that I wasn't sure, and it looks as though I was right to be cautious. – gowers Jun 19 '17 at 22:49
• @anthony-quas: no, the LIL doesn't imply that. It implies that the trajectory is unlikely to remain in $\{(t,y): t\in[0,n], |y|\leq c\sqrt{t}\}$; here, the question is if it can remain in $\{(t,y): t\in[0,n], |y|\leq c\sqrt{n}\}$ – Serguei Popov Jun 20 '17 at 11:11
• I thought the confusion was between two things. Let $A_n(c)$ be the event that the walk stays in $[-c\sqrt{n}, c\sqrt{n}]$ for its first $n$ steps. Then (1) $P(A_n(c)) \to p(c)$ as $n\to\infty$, where $p(c)$ is the Brownian motion probability I gave above. However, (2) $P(\bigcap_{n=1}^\infty A_n(c))=0$ for any $c$, by the law of the iterated logarithm. – James Martin Jun 20 '17 at 15:38

Let us divide the (time) interval $[0,n]$ into $n/t$ subintervals of length $t$. Let us call the $k$th interval good, if, during that interval, the random walk spends time at least $t/5$ to the left of $x_k-\sqrt{t}$ and at least $t/5$ to the right of $x_k+\sqrt{t}$ (here, $x_k=X_{kn/t}$ is the position of the walk in the beginning of the $k$th time interval). Clearly, the events ($\{k\mbox{th interval is good}\}$, $k=1,\ldots,n/t$) are independent, and there is $\alpha>0$ such that the probability that an interval is good is at least $\alpha$, uniformly in $t$ (you can prove this formally by e.g. comparing the random walk to the Brownian motion).
Next, a good interval contributes an amount at least $\frac{t}{5}\times (\sqrt{t})^2 = \frac{t^2}{5}$ to the sum. Moreover, a Chernoff's bound for the Binomial distribution implies that, with probability at least $1-\exp(-c' \frac{n}{t})$, at least $\frac{\alpha}{2}\times\frac{n}{t}$ intervals will be good. So, at least with the above probability, the sum will be at least $\frac{\alpha}{2}\times\frac{n}{t}\times \frac{t^2}{5} = \frac{\alpha t}{10n}n^2$. Now, take e.g. $t=n/\log^2n$ (or $t=n/(C\log n)$ for large $C$) to get a statement you're aiming at.
I think it maybe possible to use a martingale concentration inequality for this application. Indeed, let $$f(X_1, \cdots, X_n) = \sum_{m} X_m^2$$. Then $$F_i = \mathbb{E}[f|X_1, \cdots, X_i]$$ is a doob martingale. Furthermore, the walk after $$i$$ steps differs from the walk after $$i-1$$ steps only by a distance of $$1$$. Hence, we can say something like $$|F_i-F_{i-1}| \le i^2-(i-1)^2 = O(i)$$.
Then by the bounded difference inequality, we have $$\mathbb{P}(|f - \mathbb{E}f| \ge t) \le \exp(-O(t^2/n^2))$$. Therefore, the value of $$f$$ roughly lives on an interval of length $$O(n)$$.