Take the 2-minute tour ×
Quantitative Finance Stack Exchange is a question and answer site for finance professionals and academics. It's 100% free, no registration required.

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.

share|improve this question
1  
Like a depth-first search? –  chrisaycock Apr 9 '13 at 2:43
3  
Can you describe the data structure of your tree? Is the tree recombining? –  Bob Jansen Apr 9 '13 at 12:40
    
So you want to condition on a specific path end? –  Quartz Apr 9 '13 at 16:20
add comment

2 Answers

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]
share|improve this answer
    
Yea that looks like what I want I will extend it to loop through every possible ending point. I am not familiar with Python and can't seem to figure out what the statement path+[1] does. I am trying to implement this in c++ and it I am unsure how your code would do anything else besides add an element to an array with a 1 in it until there are 5 and then stop. Thanks again. –  user2183336 Apr 9 '13 at 18:16
    
@user2183336 That Python notation is the side-effect free way of appending an element. Ie, it returns a new array without modifying the original. Again, the key point to my example is that this is a depth-first search; I recursively descend each possible path. The array notation I used in Python was just for convenience; the DFS is how I actually solved the problem. –  chrisaycock Apr 9 '13 at 18:21
    
Great. Thanks a lot I appreciate it. –  user2183336 Apr 9 '13 at 18:30
add comment

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?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.