5 thoughts on “An exercise in walking randomly

  1. 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”.

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s