First passage time of a 1D simple random walk in a discrete time infinite markov chain [closed]

Question

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!

Answer 1

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}.$$