4
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Like a depth-first search? $\endgroup$
    – chrisaycock
    Apr 9, 2013 at 2:43
  • 3
    $\begingroup$ Can you describe the data structure of your tree? Is the tree recombining? $\endgroup$
    – Bob Jansen ♦
    Apr 9, 2013 at 12:40
  • $\begingroup$ So you want to condition on a specific path end? $\endgroup$
    – Quartz
    Apr 9, 2013 at 16:20

2 Answers 2

Reset to default
5
$\begingroup$

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]
Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user2183336
    Apr 9, 2013 at 18:16
  • $\begingroup$ @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. $\endgroup$
    – chrisaycock
    Apr 9, 2013 at 18:21
1
$\begingroup$

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?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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