# Probability of passing through 3 specific nodes along a binomial tree

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.

• 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

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