1

Can anyone provide the first hitting time distribution for a discrete random walk?

Edit: Specifically, a 1D random walk, starting at $k=0$. Each step moves either $-1$ or $+1$ without any boundaries. I require the distribution for the first hitting time at some arbitrary point $m>0$.

I cannot find it anywhere. I can only find it for continuous Brownian motion.

lemon
  • 3,548
  • Can you verbose on what do you understand by discrete random walk? 1D, 2D or 3D discrete RW or on which lattice are you moving on? Also where are the boundaries for the hit phenomena? – Jesús Ros Dec 12 '16 at 10:50
  • @gunbl4d3 Updated. – lemon Dec 12 '16 at 10:52
  • It seems to be solved in here: http://galton.uchicago.edu/~lalley/Courses/312/RW.pdf – Jesús Ros Dec 12 '16 at 11:21
  • @gunbl4d3 Those notes only provide the solution for $\tau(1)$, not $\tau(m)$ which is instead given as an exercise. – lemon Dec 12 '16 at 11:24
  • Still it gives sufficient advice as to how to do it. $\tau(m)$ is the sum of $m$ independent copies of $\tau$, and so it's PGF is the n-th power of $F(z)$. – Jesús Ros Dec 12 '16 at 11:30
  • @gunbl4d3 But I have no experience with PGF's, I don't even know what the $z$ should be/represents. All I need is the solution. – lemon Dec 12 '16 at 11:33

1 Answers1

6

For $n,m\geq 1$, $$P(\tau(m)=n)=\begin{cases} \displaystyle{{m\over n}\binom{n}{(n+m)/2}{1\over 2^n}} &\mbox{if } m+n \mbox{ is even}\\[5pt] 0 &\mbox{if }m+n \mbox{ is odd}.\end{cases} $$