# An exercise in walking randomly

## 5 thoughts on “An exercise in walking randomly”

1. Lianxin says:

I took a course on Stochastic Calculus with J. Michael Steele at UPenn. (I remember you said you were gonna teach stat in fall 2010, but never learnt it before)
First of all, $S_n^2-n$ is a martingale,
$E(S_{n+1}^2-(n+1))=\frac12 ((S_n+1)^2-(n+1))+\frac12 ((S_n-1)^2-(n+1))=S_n^2-n$
From Doob stopping time theorem,
$E(S_T^2-T)=E(S_0^2-0)=0$
So
$E(T)=E(S_T^2)=\frac12 N^2+\frac12 N^2=N^2$
I like your series term matching method for solving for $P(T=M)$. I came up with a combinatorial approach that I want to discuss with you.
Let $(\frac{M+N}{2},\frac{M-N}{2})$ denote the event that for a random walk without stopping rules (hallway is infinitely long), there are $\frac{M+N}{2}$ left steps and $\frac{M-N}{2}$ right steps during the first $M$ steps.
$P(T=M, S_T=N) P((\frac{M+N}{2},\frac{M-N}{2})| T=M, S_T=N)=P(T=M, S_T=N| (\frac{M+N}{2},\frac{M-N}{2}) ) P( (\frac{M+N}{2},\frac{M-N}{2}) )$
$P(T=M, S_T=N) = P(T=M, S_T=N| (\frac{M+N}{2},\frac{M-N}{2}) ) C_M^{\frac{M+N}{2}} /2^M$
where $C_X^Y$ is the number of ways to choose $Y$ items from $X$ items.
$P(T=M, S_T=N | (\frac{M+N}{2},\frac{M-N}{2}) )=[C_M^{(M+N)/2}-N(\text{hit }N\text{ before }T)-N(\text{hit }-N\text{ before }T)]/C_M^{(M+N)/2}$
By principle of reflection, $N(\text{hit }-N\text{ before }T)=N(S_T= -3N)=C_M^{M+3N/2}$ for $M\ge3N$. Otherwise it is 0.
$N(\text{hit }N\text{ before }T)$ can be decomposed as $N(S_{T-1}=N+1,\text{ hit }N\text{ before }T)+N(S_{T-1}=N-1,\text{ hit }N\text{ before }T)=C_M^{M+3N/2}/2+N(S_{T-1}=N+1)=C_M^{M+3N/2}/2+C_{M-1}^{(M+N)/2}$
Finally $P(T=M)=2 P(T=M, S_T=N)$

1. I converted formulas to latex (WordPress uses “dollar”latex … “dollar” syntax). Your count of paths is interesting but there are two questionable points. First, the events “hit N before T” and “hit -N before T” are not mutually exclusive. Second, I did not understand your way of counting the number of “hit N before T”.

1. Lianxin says:

Yes thanks for pointing these out! It should be $P(T=M, S_T=N|(\frac{M+N}{2},\frac{M-N}{2}))=[C_M^{\frac{M+N}{2}}-N(\text{hit N before T})-N(\text{hit -N before T})+N(\text{hit both N and -N before T})]/C_M^{\frac{M+N}{2}}$.
$N(\text{hit N before T})=N(S_{T-1}=N+1)+N(S_{T-1}=N-1,\text{ hit N})=2N(S_{T-1}=N+1)=2C_{M-1}^{\frac{M+N}{2}}$
$N(\text{hit -N before T})=N(S_{T}=3N)=C_M^{\frac{M+3N}{2}}$ if $M \ge 3N$.
$N(\text{hit both N and -N before T})=N(S_{T}=5N)=C_M^{\frac{M+5N}{2}}$ if $M \ge 5N$.

2. This is meant as a reply to your Nov. 4 7:59pm comment, but WordPress does not seem to allow 4th level replies. The term $C_M^{\frac{M+5N}{2}}$ actually counts only (hits N and then -N before T). Using reflection again, the term (hits -N and then N before T) should be $2*C_{M-1}^{\frac{M+3N}{2}}$. So the total number of walks exiting [-N,N] through N in M steps should be

binomial(M,(M+N)/2)-2*binomial(M-1,(M+N)/2)-binomial(M,(M+3*N)/2)+2*binomial(M-1,(M+3*N)/2)+binomial(M,(M+5*N)/2)
(using Maple notation, since I calculated with Maple).

The convenient test case is N=2, because (for M even) the correct answer is $2^{(M-2)/2}$. The above formula gives correct answer for M=2,4,6,8,10, but for M=12 it returns 34 instead of 32. Why? Apparently, because the events (hits -N and then N before T) and (hits N and then -N before T) are not mutually exclusive. We could try to fix this too, but I’m afraid this is never going to stop.