This is from Stirzaker's book Random Processes.

Suppose we have a simple random walk with probability going "up" p, "down" q. At time 0 it stats at 0, so

$$S_0 = 0$$

Now let $u_b $ be the mean number of visits to "state" b before returning to the origin. The following is given without proof:

$$u_b = \sum^n_{i=1}P(S_1S_2..S_n \neq 0, S_n = b)$$

where the the probability in brackets is the probability of random walk reaching b on the nth step AND not touching 0 during the trip. By the balot theorem, $P(S_1S_2..S_n \neq 0|S_n = b) = b/n $. But I still dont understand how the equality is found. Any help much appreciated.

  • $\begingroup$ Which equation is the one you don't understand? What does $P(S_1S_2...S_n|S_n=b)$ mean? $\endgroup$ – pajonk Jun 20 '16 at 17:38
  • $\begingroup$ The main equality ub = .... And thank you for pointing out the type, it should be S1S2..Sn not equal to 0 | Sn = b $\endgroup$ – Malin Jun 20 '16 at 17:57
  • $\begingroup$ There must be a typo in your question. The sum is over an index $i$ that does not appear anywhere. $\endgroup$ – Michael Jun 20 '16 at 17:59
  • 1
    $\begingroup$ Yes, sorry for all the typos, and thank you for answering the question! $\endgroup$ – Malin Jun 20 '16 at 18:09

There was likely a typo in your question, as the sum is over an index $i$ that does not appear anywhere. I think the true equation is intended to be: $$ u_b = \sum_{i=1}^{\infty} P[S_1S_2\cdots S_i \neq 0, S_i=b]$$ You can prove that by defining $N_b$ as the random number of times we hit $b$ before returning to $0$ and then taking expectations of the identity: $$ N_b = \sum_{i=1}^{\infty} 1\{S_i=b\}1\{S_1S_2\cdots S_i \neq 0\}$$ with $1\{A\}$ being an indicator function of the event $A$ (being 1 if $A$ occurs and $0$ else).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.