Next: TOTAL ESCAPE PROBABILITY FOR Up: thesis Previous: ALGORITHMS   Contents

# PATHWAY SUMS FOR CHAIN GRAPHS, #MATH944#

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

 (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 [242].

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)

and hence

 (C.6)

Next: TOTAL ESCAPE PROBABILITY FOR Up: thesis Previous: ALGORITHMS   Contents
Semen A Trygubenko 2006-04-10