Jul 14, 2015

Solution to Student Puzzle Corner 9

Bulletin Editor Anirban DasGupta writes:

Well done to Yixin Wang of Columbia University, who sent correct answers to all three parts (although fuller answers are encouraged).
SPC Yixin Wang

The problem asked was to characterize the set of recurrence points of three $d$-dimensional random walks with step distributions $F$:
(a) $d = 1, F$ = the two point step distribution with $P(X_i = \pm 1) = \frac{1}{2}$;
(b) $d = 2, F$ = the uniform step distribution inside the unit two dimensional ball;
(c) $d = 3, F$ = the trivariate standard normal distribution.

Recall that a specific point $\bf{x}$ is called a recurrence point of the random walk $S_n$ if for any $\epsilon > 0$, $P(||S_n – \bf{x}$$|| < \epsilon \, \mbox{for infinitely many}\, n) = 1$. In contrast, a specific point $\bf{x}$ is called a possible point of the random walk $S_n$ if for any $\epsilon > 0$, $\exists N \ni P(||S_N – \bf{x}|| < \epsilon ) > 0$.

Here are three facts that are useful in studying recurrence points of a general $d$-dimensional random walk:
1. The set of recurrence points of a $d$-dimensional random walk is either the empty set or equals the set of all possible points of the random walk.
2. Fix $0 < r < 1$. The set of recurrence points of a $d$-dimensional random walk $S_n$ is nonempty (and hence, equals the set of its possible points) if and only if $\sum_{n = 1}^\infty P(||S_n|| < r) = \infty $. 3. Let $\phi (t)$ denote the cf (characteristic function) of the step distribution $F$ of a $d$-dimensional random walk. Suppose $F$ is symmetric around the origin, i.e., $P(A) = P(-A)$ for all (measurable) sets $A$ under $F$. Then, the set of recurrence points of $S_n$ is nonempty if and only if [ \int_{(-1,1)^d}\, \frac{1}{1 - \phi (t)}dt = \infty . \] Fact 3 is sometimes easier to verify than Fact 2, although they both characterize when a random walk is recurrent. Returning now to the problem that was asked, for problem (a), the set of possible points is the set of integers $\{0, \pm 1, \pm 2, \cdots \}$. The random walk $S_n$ can return to zero only for even $n$, and \[ P(S_{2n} = 0) = \frac{{2n \choose n}}{4^n} \sim \frac{1}{\sqrt{n\pi }}, \] by straightforward use of Stirling’s approximation. Hence, for $0 < r < 1$, \[ \sum_{n = 1}^\infty P(|S_n| < r) = \sum_{n = 1}^\infty P(S_{2n} = 0) = \sum_{n = 1}^\infty \frac{1}{\sqrt{n\pi }}(1+o(1)) = \infty , \] since $\sum_{n = 1}^\infty \frac{1}{\sqrt{n}} = \infty .$ Therefore, by Fact 1, in the case of problem (a), the set of recurrence points of $S_n$ is equal to the set of all integers. For problem (b), the set of possible points is $\mathcal{R}^2$. Heuristically, for large $n$, $S_n$ is approximately a two dimensional normal with mean zero and covariance matrix $cnI$, where $I$ is the $2\times 2$ identity matrix and $c$ is a positive constant. Hence, \[ P(||S_n|| < r) = P(||\frac{S_n}{\sqrt{n}}|| < \frac{r}{\sqrt{n}}) \approx \frac{ar^2}{n}, \] where $a$ is a constant. Since $\sum_{n = 1}^\infty \frac{1}{n} = \infty $, this suggests that $\sum_{n = 1}^\infty P(||S_n|| < r) = \infty $. Indeed, this is the case and the heuristic argument can be made rigorous. It follows from Fact 2 that for problem (b), the set of recurrence points of $S_n$ is $\mathcal{R}^2$. One may also conclude this by using Fact 3. For the case of problem (c), consider the $d$-dimensional random walk with the $d$-dimensional standard normal step distribution. The cf of $F$ equals $\phi (t) = e^{-t’t/2}$. Therefore, locally near ${\bf t} = {\bf 0}$, $1-\phi (t) \sim t’t/2$. Now, with $S_d$ denoting the surface area of the unit $d$-dimensional ball, \[ \int_{t:t’t \leq 1}\frac{1}{t’t}dt = S_d\int_{0}^1r^{d-3}dr \] (by transforming to the $d$-dimensional polar coordinates) which is $< \infty $ if and only if $d \geq 3$. Now note that $\int_{(-1,1)^d}\frac{1}{1-\phi (t)}dt < \infty $ if and only if $\int_{t:t’t \leq 1}\frac{1}{1-\phi (t)}dt < \infty $. Therefore, by Fact 3, the $d$-dimensional Gaussian random walk is recurrent in one and two dimensions, and transient in all dimensions higher than two; in particular, for problem (c), the set of recurrence points is the empty set.


1 Comment

Leave a comment to Student Puzzle Corner 10: deadline August 10, 2015 « IMS Bulletin




Welcome to the IMS Bulletin website! We are developing the way we communicate news and information more effectively with members. The print Bulletin is still with us (free with IMS membership), and still available as a PDF to download, but in addition, we are placing some of the news, columns and articles on this blog site, which will allow you the opportunity to interact more. We are always keen to hear from IMS members, and encourage you to write articles and reports that other IMS members would find interesting. Contact the IMS Bulletin at bulletin@imstat.org

What is “Open Forum”?

In the Open Forum, any IMS member can propose a topic for discussion. Email your subject and an opening paragraph (to bulletin@imstat.org) and we'll post it to start off the discussion. Other readers can join in the debate by commenting on the post. Search other Open Forum posts by using the Open Forum category link below. Start a discussion today!

About IMS

The Institute of Mathematical Statistics is an international scholarly society devoted to the development and dissemination of the theory and applications of statistics and probability. We have about 4,500 members around the world. Visit IMS at http://imstat.org
Latest Issue