Next: TOTAL ESCAPE PROBABILITY FOR Up: thesis Previous: ALGORITHMS Contents
To obtain the total probability of leaving the chain via node if started from node , i.e. , we must calculate the pathway sum . We start with the case and obtain . Consider any path that has reached node . The probability factor due to all possible to recrossings is simply . We need to include this factor every time we reach node during recrossings of to . The corresponding sum becomes
PATHWAY SUMS FOR CHAIN GRAPHS, #MATH944#
| || (C.1)|
Similarly, we can continue summing contributions in this way until we have recrossings of to , for which the result of the nested summations is . Hence, is the total transition probability for pathways that return to node and are confined to nodes with index greater than without escape from .
We can similarly calculate the total probability for pathways returning to and confined to nodes with indices smaller than . The total probability factor for recrossings between nodes 1 and 2 is . Hence, the required probability for recrossings between nodes 2 and 3 including arbitrary recrossings between 1 and 2 is . Continuing up to recrossings between nodes and we obtain the total return probability for pathways restricted to this side of as . The general recursive definitions of and are:
| || (C.2)|
We can now calculate as
| || (C.3)|
where we have used Equation C.2 and the multinomial theorem .
We can now derive as follows. If we can write
| || (C.4)|
gives the total transition probability from to , so the corresponding probability for node is times the branching probability from to , i.e. , times , which accounts for the weight accumulated from all possible paths that leave and return to node and are restricted to nodes with indexes greater than . We can now replace by and so on, until is expressed in terms of . Similarly, if we have
| || (C.5)|
| || (C.6)|
Next: TOTAL ESCAPE PROBABILITY FOR Up: thesis Previous: ALGORITHMS Contents Semen A Trygubenko 2006-04-10