If we consider a simple Random Walk on the positive integers (discrete Markov chain), with symmetric transition probabilities. We start at time $0$ at the integer $i_0 = m$ and at each time step $P(i_{t+1}=i_{t}+1) = P(i_{t+1}=i_{t}-1) = .5$. The First Passage Time Density (FPTD) is the probability that we first reach the integer $1$ at time t. I am looking for a close form formula for any $t$ of the First passage time density of $i_t$ in the integer $1$ (the density of the hitting time of integer $1$). Note that there are no boundary or reflection possible for big integers. I am specifically interested in the case when $m\neq 1$ (not the first return problem). Does a close from formula exists for First passage time density in this case or maybe even an upper bound on it in order to get the rate of it?

In Wikipedia I see a result for continuous time that makes the Levy distribution intervene. I am looking for a similar result in discrete time and discrete Markov chain with no boundary. https://en.wikipedia.org/wiki/First-hitting-time_model

Thanks for any help!


closed as off-topic by Douglas Zare, Stefan Kohl, Wolfgang, Boris Bukh, Franz Lemmermeyer Nov 18 '16 at 8:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Douglas Zare, Stefan Kohl, Wolfgang, Boris Bukh, Franz Lemmermeyer
If this question can be reworded to fit the rules in the help center, please edit the question.


There's a standard result that says, in your notation, that the probability $P(\tau = n)$ of hitting 1 for the first time at time $n$ is $\frac{|m-1|}{n} P(i_n = 1)$. See

MR2456097 van der Hofstad, Remco; Keane, Michael. An elementary proof of the hitting time theorem. Amer. Math. Monthly 115 (2008), no. 8, 753–756. PDF

And by the binomial distribution, it's easy to see that $$P(i_n = 1) = \binom{n}{\frac{|m-1|+n}{2}} 2^{-n}$$ where the probability is $0$ if $m-1,n$ have different parity. (To get from $m$ to $1$ in $n$ steps, where let's say $m>1$, you have to make $\frac{(m-1)+n}{2}$ steps to the left and the remaining $\frac{n-(m-1)}{2}$ steps to the right.) So we get $$P(\tau = n) = \frac{|m-1|}{n} \binom{n}{\frac{|m-1|+n}{2}} 2^{-n}.$$


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