Enumerating Paths Through a Trinomial Tree
Summary
The document describes how to enumerate every sequence of up, middle, and down moves in a trinomial tree. Its example uses recursive depth-first search: extend a partial path with each of the three moves until the desired number of steps is reached, then keep paths whose move values sum to the target terminal node. This produces all distinct sequences ending at that node, including paths that arrive there in different orders.
A second answer suggests an alternative representation: count in base three and convert each digit into one of the three moves. The example demonstrates the recursive filter for a five-step path ending at the central node, but it does not discuss stock price assumptions, trade P&L calculations, probabilities, or efficiency. Enumerating every path grows exponentially with the number of steps, so the recursive approach may become costly for large trees; counting paths by endpoint can be more efficient when the individual sequences are not needed.
Key ideas
- A trinomial path is a sequence of up, middle, and down moves.
- Recursion can generate each possible sequence by extending partial paths one move at a time.
- Summing move values filters paths that end at a chosen node.
- Base-three digits can also encode move sequences.
- The method enumerates paths and does not calculate their probabilities or trade P&L.
Tags
Full text
# Iterating through every path of a Trinomial Tree
# Iterating through every path of a Trinomial Tree
I am attempting to come up with an algorithm to iterate through every possible path of a trinomial tree and am having difficulties coming up with one. Is there any literature on this or has anyone else written something similar?
To be specific I am trying to calculate the P&L of stock trades from node 0 to every possible path end.
EDIT: Let me clarify - for a 1 step trinomial tree there are three paths: 1 (up) 0 (middle) or -1 (down). Adding another step makes the tree have 5 ending points and 9 paths: 11 (up,up) 10 (up,mid) 01 (mid, up) 1-1 (up,down) 00 (mid,mid) -11 (down,up) 0-1 (m,d) -10 (d,m) -1-1 (d,d)
I am aware the total number of paths that end at a given point is given by Pascal's tetrahedron but I do not know how to come up with all the paths for an arbitrary (n-step) tree. So I need the 1,-1,1,-1,0 sequence which in this case would end on the middle node of a 5 step tree.
## Answer by chrisaycock (score 5)
https://quant.stackexchange.com/a/7707
If I understand you correctly, here's an example in Python. Any other programming language should be able to do something similar:
```
def search(path):
if len(path) == 5:
if sum(path) == 0:
print path
else:
search(path+[1])
search(path+[0])
search(path+[-1])
```
Just invoke it with an empty array:
```
>> search([])
[1, 1, 0, -1, -1]
[1, 1, -1, 0, -1]
[1, 1, -1, -1, 0]
[1, 0, 1, -1, -1]
[1, 0, 0, 0, -1]
[1, 0, 0, -1, 0]
[1, 0, -1, 1, -1]
[1, 0, -1, 0, 0]
[1, 0, -1, -1, 1]
[1, -1, 1, 0, -1]
[1, -1, 1, -1, 0]
[1, -1, 0, 1, -1]
[1, -1, 0, 0, 0]
[1, -1, 0, -1, 1]
[1, -1, -1, 1, 0]
[1, -1, -1, 0, 1]
[0, 1, 1, -1, -1]
[0, 1, 0, 0, -1]
[0, 1, 0, -1, 0]
[0, 1, -1, 1, -1]
[0, 1, -1, 0, 0]
[0, 1, -1, -1, 1]
[0, 0, 1, 0, -1]
[0, 0, 1, -1, 0]
[0, 0, 0, 1, -1]
[0, 0, 0, 0, 0]
[0, 0, 0, -1, 1]
[0, 0, -1, 1, 0]
[0, 0, -1, 0, 1]
[0, -1, 1, 1, -1]
[0, -1, 1, 0, 0]
[0, -1, 1, -1, 1]
[0, -1, 0, 1, 0]
[0, -1, 0, 0, 1]
[0, -1, -1, 1, 1]
[-1, 1, 1, 0, -1]
[-1, 1, 1, -1, 0]
[-1, 1, 0, 1, -1]
[-1, 1, 0, 0, 0]
[-1, 1, 0, -1, 1]
[-1, 1, -1, 1, 0]
[-1, 1, -1, 0, 1]
[-1, 0, 1, 1, -1]
[-1, 0, 1, 0, 0]
[-1, 0, 1, -1, 1]
[-1, 0, 0, 1, 0]
[-1, 0, 0, 0, 1]
[-1, 0, -1, 1, 1]
[-1, -1, 1, 1, 0]
[-1, -1, 1, 0, 1]
[-1, -1, 0, 1, 1]
```
## Answer by Quartz (score 1)
https://quant.stackexchange.com/a/7703
To convert an index to base 3 (actually to an array with the base 3 digits, each one selecting a move up/mid/down) you only need to alternate a modulo-3 (remainder) operator and integer division by 3. Or were you asking for something else?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.