0

Sorry if this has been asked elsewhere. I'd like to count number of paths that doesn't revisit zero multiple times; that is, given a starting point $a > 0$ at time $0$, what is a number of paths that will hit $b = 0$ only once at a specific time $t$?

At first I thought that I could find it by first finding a number of paths that hit zero multiple times then subtracting it with a total number of possible paths.

To find the number of paths that hit zero multiple times, I've tried applying the idea of reflection principle from Grimmett and Stirzaker's textbook on "Probability and Random Processes." It states that "If $a,b > 0$ then $N^0_{n} (a,b) = N_{n} (-a,b)$," where $N_{n} (a,b)$ is a number of all possible paths from $a$ to $b$ within time $n$, and $N^{0}_{n} (a,b)$ is a number of paths from $a$ to $b$ within time $n$ that pass $0$ during any time in $1,2,...,n-1$.

Apparently, this doesn't work for my problem since $b = 0$ in my case and all paths that were reflected by $y = 0$ seems to include all paths including those hits zero only once.

Any idea?

  • 1
    Hint: this is equivalent to counting the paths from $a$ to $1$ within time $t - 1$ that never hit $0$. – cip999 Oct 02 '17 at 15:10
  • Ahh! How silly I am. Just by backtracking 1 step before hitting zero, then I can use the above reflection principle and add 1 more step to get the answer now. Many thanks, @cip999 – Tin Leelavimolsilp Oct 02 '17 at 15:22
  • Sorry. I've just realised that it's exactly equivalent to counting paths from $a$ to $1$ as you said. – Tin Leelavimolsilp Oct 02 '17 at 16:03

0 Answers0