MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let's consider an asymmetric Random Walk on $Z$, with transition probabilities $p_{i, i+1}=p$, $~~p_{i, i+1}=q$, $\forall i \in \mathcal{Z}$, $p+q=1$ and $p>q$.

I am interested in the probability of the first hitting time of a bareer in $i=n$, assuming that the walk started from $i=0$ at time $t=0$. Is there an explicit formula for it? How does it depend on $n$?

share|cite|improve this question
This is an exercise. The reflection principle lets you count the walks which first arrive at $n$ at time $t$. These all have the same probability, since they all have $n$ more positive steps than negative steps. – Douglas Zare Mar 11 '13 at 17:28
This has been answered fully in… – Jeremy Voltz Mar 11 '13 at 17:56
The answer by Did suggests another solution by generating functions but the reflection method is much simpler. – Douglas Zare Mar 11 '13 at 20:14
up vote 1 down vote accepted

The explicit formula is: $P[N_m=n]=(m/n)P[S_n=m]$, where $P[N_m=n]$ is the probability the position $m$ is hit after exactly $n$ steps, $S_n = X_1+X_2+\dots X_n$ and $P[S_n=m]$ is the probablity after $n$ steps the path to be at the position $m$. This last is well-known and is given by $P[S_n=m]=(n!/([(n+m)/2]![(n-m)/2]!))p^{(n+m)/2}q^{(n-m)/2}$. This is true when $n$ and $m$ have the same parity, else the probability is zero. Additionally $m$ is positive and $n$ is greater than or equal to $m$. A similar expression can be found for negative $m$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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