Does the square of a symmetric walk length have a mean?

63 Views Asked by At

Consider a symmetric random walk starting at the origin where the positions are non negative integers. Each move goes right/left with probability 1/2 except if you are at the origin you always go right.

Let $X$ be the number of steps to get to 10. Does $X^2$ have a mean?

1

There are 1 best solutions below

2
On BEST ANSWER

Divide time into blocks of length 10 steps. In each block, there is a chance of at least $p=2^{-10}$ that the walk will reach 10, so the hitting time $X=\tau$ can be bounded above by $10Y$ where $Y$ is a Geometric variable with parameter $p$. Thus by here, $$E (X^2) \le 100 E(Y^2)=100(2-p)/p^2.$$ This bound is far off. To calculate $E (X^2)$, one can set up and solve a recursion. The most powerful method, which requires some preparation, is to use the optional stopping theorem for Martingales. This is a topic you can find in most probability textbooks, e.g. the books by Durrett, by Billingsley and by Williams, or in Chapter 17 of this.

Let $S_n$ be simple random walk on the integers, which steps left or right with equal probability, where $S_0=0$. Then the process you consider is exactly $|S_n|$, so your $X$, which I will now call $\tau$, is the time for $|S_n|$ to reach $L=10$. Let's find the moments of $\tau=X$ for any target integer $L>0$. If $|k|<L$, then (with the subscript indicating the starting point of the simple random walk) $$E_k(\tau)=1+\frac{E_{k-1}(\tau)+E_{k+1}(\tau)}{2}\,,$$ and $E_L(\tau)=E_{-L}(\tau)=0$ The unique solution of this recursion is $$E_k(\tau)=L^2-k^2\,.$$ Alternatively, the standard quadratic Martingale $Q_t=S_t^2-t$ yields $$0=E(Q_0)=E(Q_{\tau \wedge n})=E(S_{\tau \wedge n}^2)-E(({\tau \wedge n})^2)\,. $$ Thus $$E(S_{\tau \wedge n}^2)=E(({\tau \wedge n})^2)\,.$$ Taking a limits as $n \to \infty$, using the lebesgue bounded convergence theorem on the left and monotone convergence on the right, we get $$L^2=E(S_{\tau }^2)=E( \tau ^2)\,.$$

To calculate the second moment, first consider $L=2$. then $\tau=2G$ where $G$, the number of visits to zero, is Geometric$(1/2)$. Thus $E(\tau^2)=4E(G^2)=24$ for $L=2$.

For the general case, we use the process $$M_{t}=S_t^4 - 6t S_t^2 + 3t^2 + 2t \,. $$ It is straightforward to check that $E(M_{t+1})|S_t)=M_t$ for every $t$, i.e., $M_t$ is a martingale. One can discover $M_t$ in a principled way, see section 17.3.3 in 2.

Optional Stopping (the version recalled below) yields $$ 0=L^4-6E_0(\tau)L^2+3E_0(\tau^2)+2E_0(\tau)=-5L^4+3E_0(\tau^2)+2L^2 \,. $$ Solving for $E_0(\tau^2)$ gives $$ E_0(\tau^2)=(5L^4-2L^2)/3 \,, $$ In particular, for $L=10$ this gives $$E(X^2)=E(\tau^2)=16,600 \,.$$

Optional Stopping Theorem, Version 3 (Cor 17.8 p. 246 in 2).
Let $(M_t)$ be a martingale for some filtration, that has bounded increments, that is $|M_{t+1} - M_t| \leq B$ for all $t$ where $B$ is a non-random constant. Suppose that $\tau$ is a stopping time for the same filtration, with $ E(\tau) < \infty$. Then $ E(M_{\tau}) = E(M_0)$.

https://pages.uoregon.edu/dlevin/MARKOV/mcmt2e.pdf