Skip to content
All library documents

Counting Paths and Nodes in a Recombining Binomial Tree

Article Quant Q&A · Author: Wolfy
Read the original

Summary

The document asks how many distinct paths and states occur in a binomial model over a specified number of time steps. Since each step offers two possible moves, the number of complete paths from the initial state to the final time is two raised to the number of steps. For a recombining tree, multiple paths can lead to the same state, so counting nodes is different from counting paths.

The answer gives a triangular-number expression for the node count and says it includes the initial node, but its stated summation from one through n does not actually include the root when levels run from time zero through n. With n steps and n+1 time levels, the standard recombining tree has one more node at each level than that level's step index, for a total of (n+1)(n+2)/2 nodes. The path count remains 2^n. A non-recombining tree has a different node count, so the tree structure must be specified.

Key ideas

  • A sequence of n binary moves has 2^n complete paths.
  • In a recombining tree, different paths can arrive at the same node.
  • Node counts must include the states at every time level, including the initial state.
  • For levels from time zero through n, the recombining tree has (n+1)(n+2)/2 nodes.
  • A non-recombining tree has a different number of distinct nodes.

Tags

StatisticsDerivatives pricing
Full text
# Binomial Model, Number of nodes from $t = 0$ to $t = n$


# Binomial Model, Number of nodes from $t = 0$ to $t = n$












How many paths are there in a binomial model from time $t = 0$ to time $t = n$? How many nodes (states) are there?

Intutively it seems that there are $2^n$ paths and $2n - 1$ nodes. But I am not sure exactly, any suggestions or hints is greatly appreciated.

## Answer by Gordon (score 2, accepted)

https://quant.stackexchange.com/a/23127

This will depend on the nature of your tree. For a re-combining binomial tree, the number of nodes, including the initial one, will be \begin{align*} \sum_{i=1}^n i = \frac{n(n+1)}{2}. \end{align*} For the paths, as at each time $j$, there are two possibilities from each node, the total path number is $2^n$.

Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)

This summary was written by Stratmill's research agent from the original; it is not a copy of the source.