Why Memoryless Processes Can Produce Recombining Trees
Summary
The discussion explains the intuitive connection between memorylessness and recombination in a binomial lattice. In a simple up-or-down process, two different sequences of moves can lead to the same value after two steps: one up followed by one down, or one down followed by one up. When future evolution depends only on the current state, those paths meet at a shared node, so the tree can recombine.
The author distinguishes this intuition from a direct relationship to a particular conditional-expectation definition of the Markov property. The explanation is explicitly informal rather than a rigorous proof, and it uses a simple binomial example. More complex models may require additional state variables to capture their history; if relevant path information is omitted from the state, a lattice may fail to recombine or the model may not be properly represented.
Key ideas
- A memoryless process evolves based on its current state rather than its full path.
- In a binomial model, opposite move sequences can arrive at the same state.
- This shared state allows paths to merge into a recombining lattice.
- The explanation is an intuitive example rather than a formal proof.
Tags
Full text
# Non-recombining lattice in non-markovian models
# Non-recombining lattice in non-markovian models
Brigo&Mercurio Interest Rate Models - Theory and Practice, 2nd edition, when treating not markovian HJM models, says the following "the approximating lattice will not be recombining and the number of nodes in the tree will grow exponentially with the number of steps".
I don't see the relation between the Markov property $\mathbb{E}[{f(W(t))}|\mathcal{F(s)}]=g(W(s))$ and the recombination of the approximating lattice. Does anyone know where I could find a proof?
## Answer by Matteo Campagnoli (score 2, accepted)
https://quant.stackexchange.com/a/60185
I think I might have found the solution to my own question. The Markov property as stated above has no direct relation with the recombination of the approximating lattice. However, if we consider the "traditional" meaning of Markovness, that is being memoryless, things become clearer.
Consider a binomial tree, where the random variable $X$ can either go up to $Xu$ with probability $p$, or go down to $Xd$ with probability $1-p$. Needless to say that for free-arbitrage reasons $0<d \le 1$ and $u\ge 1$.
On the second node, the random variable can be in only three configurations: $Xu^2$, $Xud$ or $Xd^2$. This happens only if $X$ is Markov, because the evolution of $X$ does not depend on the previous values of $X$. Hence, the lattice is recombining.
I know this is far from a rigorous proof, but at least the relation between Markovness and recombining lattices is evident and understable.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.