I wonder how to solve this problem. Lets say we have a binomial tree with the following parameters:
$u=1.25,\ d = 1/u,\ T=15$.
How many distinct possible values are there for $X_{7}$?
1
-
$\begingroup$ $d=1/u$ tells you it is a recombining tree. So there is one choice for $S_0$, two choices for $S_1$ (up and down), three choices for $S_2$ (up up, middle and down down), ... looks to me like there are $N+1$ choices for $S_N$. But draw the diagram to be sure... $\endgroup$– nbbo2Commented Sep 14, 2019 at 23:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Noob2 has given the answer, a recombining tree has $N+1$ nodes after $N$ time points. In our case, you have $8$ distinct possible values after $7$ time steps. I will next illustrate the difference between a recombining and non-recombining tree.
For a binomial tree, if $u=\frac{1}{d}$, then an up-move followed by an down-move gives the same result as a down-move followed by an up-move (since $ud=1$): $S_0ud=S_0du=S_0$. This is a huge numerical advantange since the amount of potential nodes grows only linearly with the number of time steps.
If $ud\neq1$, then the order of up- and down-moves occurrring does matter and the amount of nodes grows exponentially. In particular, $S_0ud\neq S_0du\neq S_0$. After $N$ time steps, there are $2^N$ distinct nodes. So the difference between recombining and non-recombining is (for your example of $N=7$) the difference between $7+1=8$ and $2^7=128$. For numerical implementation, the former is of course much easier and less costy: just set $N=100$. Then, a recombining tree has $101$ nodes but a non-recombining tree has roughly $10^{30}$ nodes.
The bottom line ist that a recombining tree ``re-uses'' nodes it has already created and comes back to them. A non-recombining tree however creates for every existing node two new ones which leads to exponential grow. The same issue of (non-)recombining trees equally applies to the trinomial trees where you allow for an up/middle/down-move.
This image illustrates the amount of nodes of a recombining tree (the case you have since $ud=1$)
This image illustrates the amount of nodes for a non-recombining tree
