Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

I have a random walk process where each step the probability of $+1$ is $p$ and $-1$ is $q$, with $p+q=1$. $p$ may not equal $q$. The walker starts at zero. I want to know the probability that the first return to zero occurs at $t$. Obviously, the number of increases will equal the number of decreases and both will equal $t/2$. So obviously $t$ must be even.

So far, all I have seen is the unbiased random walk PDF for first return time and that when $p>q$ there is a probability that the walker may ever reach zero. It seems like that for any finite $t$, it should simply be a question of getting the right number of permutations. Or perhaps it is as easy as a rewrite of the unbiased PDF?

Additionally, if possible, I'd like to condition on the first step being to $1$.

Thank you!

share|cite|improve this question
Although this may or may not be obvious, I should add that I am referring to a discrete random walk in one dimension. – Dave Bapst Sep 15 '11 at 22:36
up vote 3 down vote accepted

You are correct. It boils down to calculating the correct number of "permutations" or walks. I will leave you to figure out how to get the exact probability; here I only do the combinatorial problem.

We want to count the number of walks of length $t$ that start and end at $0$, such that the walk never visits $0$ in between. For convenience, we will restrict the first step to be $+1$; you will need to double the answer we get. We can naturally represent any walk as a word over the alphabet $\{ +, - \}$, where the sign tells us whether the step is in the positive or negative direction.

In this notation, we are counting the number of words such that

  1. the length of the word is $t$,
  2. the starting symbol is $+$ (why?),
  3. the number of '$+$' and '$-$' are equal (why?),
  4. for any proper prefix of the word, the number of $+$ strictly exceeds the number of '$-$' (why?).

Clearly, the last symbol must be a '$-$'. Let us delete the starting '$+$' and ending '$-$' symbol of the word, to get a subword of length $t-2$. Obviously, the original word is in one-to-one correspondence with the subword.

The final idea here is to recognize that the subwords themselves form the so-called Dyck words of length $t-2$. (A Dyck word is one with equal number of $+$ and $-$ such that every prefix of the word has at least as many '$+$' as '$-$'.) It is a standard result that the number of Dyck words of length $t-2$ is equal to the Catalan number $$ C := \frac{1}{(t/2)}\binom{t-2}{\frac{t}{2}-1}. $$

Can you take it from here?

Added. Let $E$ be the event that the first return time is $t$. If you want to calculate the probability of $E$ conditioned on the first step being $+1$, you can use the usual definition: $$ \frac{\Pr[ E \wedge \text{ first step is $+$} ]}{\text{first step is $+$}} = \frac{C \cdot (pq)^{t/2}}{p}. $$

share|cite|improve this answer
@Dave You are mixing up the biased and unbiased random walk ideas. There is no need to divide by $2^t$. Each walk that we are counting has a probability $(pq)^{t/2}$. And I am looking for the event walk1 OR walk2 OR walk3 OR ..., and all these are disjoint. So you simply add the probabilities of the walks; in this case, you can just multiply the number of allowed walks with the probability of a single one. (Note that if $p=q=1/2$, then $(pq)^{t/2} = 1/2^{t}$, so multiplying $(pq)^{t/2}$ is the same as dividing $C$ by $2^t$. I think this is the source of your confusion.) – Srivatsan Sep 16 '11 at 1:52
@Dave Well, I don't follow you now. Do you understand this proof or do you have some doubts? Are you worried that this proof may not carry over to the birth-death process scenario directly? – Srivatsan Sep 16 '11 at 1:56
@Dave Oops! Sorry, I didn't think you were wondering about that. It is fairly common to use the notation := when a quantity is being defined to be equal to something else. So here it means $C$ is defined to be the quantity on the right. (There is no variable like C: here.) – Srivatsan Sep 16 '11 at 2:43
Srivatsan, I compared your C to a few example values of t/2 and they appear to give valid estimates of the total number of combinations. For example, C=2 for t=6, which agrees with my manual estimate. So, I decided to try some simulations across a number of values of p and t, and the probability function you offered works really well. Thank you very much! – Dave Bapst Sep 16 '11 at 20:17
@Dave You're welcome. Hopefully it's correct :-) – Srivatsan Sep 16 '11 at 20:19

A standard approach for a probabilist here is to rely on generating functions. That is, fix $|s|<1$ and consider $u_x=\mathrm E_x(s^T)$, where the subscript $x$ means that the random walk starts from $x$ and where $T$ denotes the first return to $0$ of the random walk, that is, $T=\inf\{n\ge1\mid X_n=0\}$ and $(X_n)_n$ denotes the random walk starting from $X_0=x$ and making steps $+1$ with probability $p$ and $-1$ with probability $q=1-p$.

What you are asking amounts to computing $u_0$ and $u_1$, we shall explain how to compute $u_x$ for every integer $x$.

Taking into account the first step of the walk, one sees that $u_0=s(pu_1+qu_{-1})$, $u_1=s(pu_2+q)$ and $u_{-1}=s(p+qu_{-2})$. Furthermore, starting from $x=2$, to reach $0$ one must first hit $1$ and then starting from $1$ one must hit $0$. The times to hit $1$ starting from $2$ and to hit $0$ starting from $1$ to are i.i.d. hence $u_2=u_1^2$. Likewise, $u_{-2}=u_{-1}^2$ (and in fact $u_x=u_1^x$ and $u_{-x}=u_{-1}^x$ for every positive $x$).

This shows that $u_0=s(pu_1+qu_{-1})$ where $u_1=s(pu_1^2+q)$ and $u_{-1}=s(p+qu_{-1}^2)$. Solving this for $u_1$ and $u_{-1}$ yields $u_1=\dfrac{1\pm\sqrt{1-4pqs^2}}{2sp}$ and a similar formula for $u_{-1}$ but since one wants that $u_1$ and $u_{-1}$ stay bounded when $s\to0$, the $\pm$ signs are in fact $-$ signs and $$ u_0=1-\sqrt{1-4pqs^2},\qquad u_1=\frac{u_0}{2sp},\qquad u_{-1}=\frac{u_0}{2sq}. $$ The PDF of $T$ starting from $0$, $1$ and $-1$ is fully encoded in $u_0$, $u_1$ and $u_{-1}$ respectively. For example, the probability to come back at $0$ starting from $0$ and to hit $0$ starting from $1$ and $-1$ respectively, are the limits of $u_0$, $u_1$ and $u_{-1}$ when $s\to1$, that is, $$ \mathrm P_0(T<\infty)=1-\sqrt{1-4pq}=1-|1-2p|, $$ and $$ \mathrm P_1(T<\infty)=\frac1{2p}\mathrm P_0(T<\infty),\quad \mathrm P_{-1}(T<\infty)=\frac1{2q}\mathrm P_0(T<\infty). $$ Let us assume from now on that $p\ge\frac12$ (hence $p\ge q$). Then, $$ \mathrm P_0(T<\infty)=2q,\quad \mathrm P_1(T<\infty)=q/p,\quad\mathrm P_{-1}(T<\infty)=1. $$ Likewise, to get the full PDF only requires to know the expansion along powers of $t$ of the square root involved, namely, $$ \sqrt{1-4t}=1-\sum\limits_{n=1}^{+\infty}c_nt^n,\quad c_n=\frac{(2n)!}{(2n-1)(n!)^2}. $$ One gets for example $$ u_1=\frac1{2ps}\sum\limits_{n=1}^{+\infty}c_n(pq)^ns^{2n}, $$ hence, for every $n\ge1$, $$ \mathrm P_1(T=2n-1)=\frac1{2p}c_n(pq)^n. $$ Likewise, for every $n\ge1$, $$ \mathrm P_{-1}(T=2n-1)=\frac1{2q}c_n(pq)^n,$$ and finally, $$ \mathrm P_0(T=2n)=c_n(pq)^n. $$

share|cite|improve this answer
Hello Diedier! Thank you for your kind proof. Your c(n) appears to overestimate the number of combinations. For example, when n = 3, c(n)=4, although I can only count the sequences of ++-+-- and +++--- as satisfying the conditions. I'm a biologist and I had not heard about generating functions until yesterday when I looked into the literature, so I may be understanding something incorrectly. (I still don't understand what this mystery (s) is supposed to be.) – Dave Bapst Sep 16 '11 at 19:47
The formulas are correct. For example the number of paths of length $6$ with endpoints $0$ and avoiding $0$ except at their endpoints is $c_3=4$ (you seem to have forgotten the two paths below $0$). To count the paths above $0$ only, one should use the probabilities $\mathrm P_1$ (note that $\mathrm P_1(T=5)$ involves $\frac12c_3=2$). – Did Sep 16 '11 at 20:22
Oh, I see. Yes, I think that makes sense. – Dave Bapst Sep 16 '11 at 22:09
I'm trying to walk myself through the steps and having a hard time. When you take $\lim_{s\rightarrow 1}$ of $u_0$, where is the PDF of $T$ popping out from? Why does that result occur when $s$ approaches $1$? EDIT (made in last 30 secs so just del'ed orig): OH WAIT. $E[g(X)] = \int_{-\infty}^\infty g(x)f(x)dx$. Is that it? – user Jan 1 '14 at 8:18

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.