Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a re-combining binomial tree with probability of up = $p$ and probability of down = $(1-p)$. Let $n$ be the number of time steps in the binomial tree (the $x$-axis is time, and each column of nodes corresponds to "a time step". Also, each column of nodes is evenly spaced along to $x$-axis).

A re-combining binomial tree is in this picture. "Re-combining" just means that we end up in the same place given (i) Up movement --> Down movement, (ii) Down movement --> Up movement.

The set $\{0,1,...,n\}$ corresponds to the location of each node(s) on the $x$-axis. So, in the above picture, "1" would correspond to the nodes $S_{\Delta t}$, and "2" would correspond to the nodes $S_{2\Delta t}$. Consider the sets of nodes that correspond to to the following locations on the $x$-axis:

(i) $m \in \{1,...,n-2\}$,

(ii) $m+1$ and

(iii) $n$.

Let the $j$-th node at $m$ be the node that has had $j$ up-movements in all the sample paths leading to it. Let the $i$-th node at $n$ be similarly defined.

I want to find the probability that the sample path goes through node $j$ at $m$, node $j$ at $m+1$, then through node $i$ at $n$. Denote this $P\{(j,m)\cap(j,m+1)\cap(i,n)\}$.

We already know that $P\{(i,n)\cap(j,m)\} = P\{(j,m)\}P\{(i,n)|(j,m)\} = \frac{m!}{j!(m-j)!}p^j(1-p)^{m-j}*\frac{(n-m)!}{(i-j)!(n-m-i+j)!}p^{i-j}(1-p)^{n-m-i+j} = \frac{m!(n-m)!}{j!(m-j)!(i-j)!(n-m-i+j)!}p^i (1-p)^{n-i}.$

I'm looking for a way to arrive at $P\{(j,m)\cap(j,m+1)\cap(i,n)\}$.

I already know the answer is obviously $P\{(j,m)\cap(j,m+1)\cap(i,n)\} = P\{(i,n)|(j,m+1)\}P\{(j,m)\}*(1-p)$ from observation ... But I would like a "proper" way to derive it.

share|improve this question
I hope a lot of other people know what a "recombining binomial tree" is --- I sure don't. –  Gerry Myerson Sep 11 '12 at 12:59
I guess that explains the "recombining", but I still don't know what a binomial tree is. I don't know what a time step in a tree is. You write about moving on the $y$-axis, but your nodes are located on the $x$-axis --- how does that work? You are using a lot of words that you understand. As I say, I hope some other people understand the words you are using, too. –  Gerry Myerson Sep 11 '12 at 13:16
@Harokitty, Let me know if this is an accurate re-phrasing of your question. Rather than up and down movements, let's put $_0S_0$ at the origin and move up or right with probability $p$ or $1−p$ at every time step, respectively. Your question is the following: What is the probability that your length $n>m$ random walk of up-right movements passes through the points $(m−j,j)$, $(m−j+1,j)$, and $(n-i,i)$? By necessity, $i\geq j$. –  Max Sep 12 '12 at 1:10
@Harokitty, And just to be clear, the point $(a,b)$ in this new setup is the same as the point $_aS_{(a+b)\Delta t}$ from your original setup. –  Max Sep 12 '12 at 6:57
@Harokitty, You are on the right track. You just need to condition again: $P(A,B,C)=P(A|B,C)P(B|C)P(C)$. –  Max Sep 12 '12 at 7:01
show 4 more comments

1 Answer

up vote 1 down vote accepted

Your model seems to assume that the steps are iid.

In the same way as

$P\{(i,n)\cap(j,m)\} = P\{(j,m)\}P\{(i,n)|(j,m)\} = P\{(j,m)\}P\{(i-j,n-m)\} $

with $j \le i$ and $m \le n$, you can derive

$P\{(j,m)\cap(j,m+1)\cap(i,n)\} = P\{(j,m)\}P\{(j-j,m+1-m)\}P\{(i-j,n-(m+1))\} $

$= P\{(j,m)\}P\{(0,1)\}P\{(i-j,n-m-1)\} $

$= {m \choose j} p^j (1-p)^{m-j} {1 \choose 0} p^0 (1-p)^1 {n-m-1 \choose i-j} p^{i-j} (1-p)^{n-m-1-i+j} $

$= {m \choose j} {n-m-1 \choose i-j} p^{i} (1-p)^{n} $

with $j \le i$ and $m \le n-1$.

share|improve this answer
add comment

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.