My Math Forum Total Possibilities of a Probability Tree (with node reuse)

 Probability and Statistics Basic Probability and Statistics Math Forum

 June 10th, 2013, 02:49 PM #1 Newbie   Joined: Jun 2013 Posts: 1 Thanks: 0 Total Possibilities of a Probability Tree (with node reuse) Hello Everyone! It's been a while since I've done any hard core probability, and I'm working on a program to help my friend randomly generate phrases from snippets of text. The program is fine, I just want to be able to calculate the total possible outcomes from a web of phrases. Here's a link to an example tree that I drew to try and figure this out: http://arolkay.com/Tree.gif. At first I tried to work from the top down, and multiply every time I reached a branching node, but I either am not keeping track properly, or something else is happening and I'm always ending up with way too much. Then I started from the bottom up, and I got closer, but was one off (the actual number of possibilities is 12, and I got 11). I'm using Java to write this program, so I'm guessing I'll be using a recursive function to plow through the whole tree. Any ideas on how to calculate this would be greatly appreciated!
 June 13th, 2013, 01:01 AM #2 Senior Member   Joined: Jan 2013 Posts: 113 Thanks: 0 Re: Total Possibilities of a Probability Tree (with node reu Starting with the root node, traverse the tree downwards by selecting the first available succeeding node. When you reach a node with no successors, you have found a path. When you have found a path, traverse the tree upwards along the same path by which you arrived. Stop at each node to see if there are any successors which have not yet been accessed. If you find an available successor, traverse it downwards by selecting the first available succeeding node. When you reach a node with no successors, another path has been found. Continue this procedure until you end at the start node with no available successors. CASE EXAMPLE: For brevity, a node is defined by X(S), where X is the node name and S is the set of successors. Let the node set be: $N=\{S(\{A,B\}),A(\{C\}),B(\{C,D\}),C(\emptyset),D( \{E\}),E(\emptyset)\}$ Where S is the start node. Here's a trace. - Current: S. Travel: A. Reason: first available. - Current: A. Travel: C. Reason: first available. - Current: C. Travel: A. Reason: end of branch; retracing path. (1) - Current: A. Travel: S. Reason: no unused successors; retracing path. - Current: S. Travel: B. Reason: unused successor. - Current: B. Travel: C. Reason: first available. - Current: C. Travel: B. Reason: end of branch; retracing path. (2) - Current: B. Travel: D. Reason: unused successor. - Current: D. Travel: E. Reason: first available. - Current: E. Travel: D. Reason: end of branch; retracing path. (3) - Current: D. Travel: B. Reason: no unused successors; retracing path. - Current: B. Travel: S. Reason: no unused successors; retracing path. - Current: S. Travel: halt. Reason: no unused successors at root node.

 Tags node, possibilities, probability, reuse, total, tree

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post alfred_oh Advanced Statistics 0 May 3rd, 2013 07:43 AM shaon Applied Math 0 December 18th, 2012 05:10 PM eulerrules1 Computer Science 0 April 10th, 2012 01:00 PM rnck Probability and Statistics 7 November 5th, 2011 09:33 PM Fibo Applied Math 1 March 26th, 2010 06:32 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top