Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 101 / 2

This is the simple symmetric random walk on the integers, starting at zero. It is recurrent: it returns to zero infinitely often almost surely, and in fact visits every integer infinitely often. To see the two-sided unboundedness explicitly, gambler's ruin gives, for positive integers $a,b$,Letting $a\to \infty$ shows that $b$ is hit with probability one; the analogous argument hits every negative integer. From any state the same argument gives return to zero with probability one. Repeated use of the Strong Markov property then gives infinitely many returns and visits. ThereforeIn particular $X_n$ has no limit almost surely, and $|X_n|$ does not tend to infinity because of the returns to zero. In contrast, the strong law of large numbers gives $X_n/n\to 0$ almost surely, while the central limit theorem gives $X_n/\sqrt{n}\stackrel{d}{\to }N(0,1)$. These distinguish oscillation of the path from scaling limits of its probability distribution.

Every $X_n$ is integrable: induction gives $|X_n|\le a^n|x|+{\sum }_{j=0}^{n-1}{a}^j$. Since the innovation has expectation zero, the recursion impliesStarting from $\mathbb{E}{X}_0=x$, induction therefore givesThis holds for every $a>0$, including $a=1$. The independence of the signs also identifies this as an autoregressive process of order one, although zero mean of each sign already suffices for the displayed expectation recursion.

Write $c=1/(a-1)$. If $X_0=x>c$, then for either possible sign,as long as $X_n>c$. Thus the process stays above $c$, is strictly increasing, and induction gives $X_n\ge c+a^n(x-c)\to \infty$. If $x<-c$, the symmetric argument makes the process strictly decreasing to $-\infty$. This proves the first assertion pathwise, with the strict sufficient threshold $|x|>c$.

For an arbitrary starting point, a proof is needed that the process actually reaches such a region. Fix $L>c$ and choose an integer $m$ soAt a block starting at time $km$, if $X_{km}\ge 0$, the next $m$ signs all equal to $+1$ give $X_{(k+1)m}>L$. If $X_{km}<0$, all $-1$ signs instead give $X_{(k+1)m}<-L$. Conditional on the current natural filtration, the selected block has probability $\epsilon =2^{-m}$, by independence of future signs. If $\tau =\inf \{n:|X_n|>L\}$, iterated conditional expectation givesThis is a geometric tail bound from a uniform escape probability, so $\tau <\infty$ almost surely. Once outside, the sign is preserved and, for every future noise sequence,Consequently the explosive affine recursion with symmetric bounded noise hasThe block argument closes the gap between escape from a large initial value and escape from an arbitrary one; no assertion about the absence of atoms in an infinite random series is necessary.