next up previous contents
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 $ C_N$ via node $ \alpha $ if started from node $ \beta $, i.e.  , we must calculate the pathway sum $ \mathcal{S}_{\alpha,\beta}^{C_N}$. We start with the case $ \alpha=\beta$ and obtain $ \mathcal{S}^{C_N}_{\beta,\beta}$. Consider any path that has reached node $ N-1$. The probability factor due to all possible $ N-1$ to $ N$ recrossings is simply $ R_{N-1}=1/(1-P_{N-1,N}P_{N,N-1})$. We need to include this factor every time we reach node $ N-1$ during recrossings of $ N-2$ to $ N-1$. The corresponding sum becomes

$\displaystyle R_{N-2}=\sum_{m=0}^\infty (P_{N-2,N-1}P_{N-1,N-2}R_{N-1})^m = \dfrac{1}{1-P_{N-2,N-1}P_{N-1,N-2}R_{N-1}}.$ (C.1)

Similarly, we can continue summing contributions in this way until we have recrossings of $ \beta $ to $ \beta+1$, for which the result of the nested summations is $ R_\beta=1/(1-P_{\beta,\beta+1}P_{\beta+1,\beta}R_{\beta+1})$. Hence, $ R_\beta$ is the total transition probability for pathways that return to node $ \beta $ and are confined to nodes with index greater than $ \beta $ without escape from $ C_N$.

We can similarly calculate the total probability for pathways returning to $ \beta $ and confined to nodes with indices smaller than $ \beta $. The total probability factor for recrossings between nodes 1 and 2 is $ L_2=1/(1-P_{1,2}P_{2,1})$. Hence, the required probability for recrossings between nodes 2 and 3 including arbitrary recrossings between 1 and 2 is $ L_3=1/(1-P_{2,3}P_{3,2}L_2)$. Continuing up to recrossings between nodes $ \beta-1$ and $ \beta $ we obtain the total return probability for pathways restricted to this side of $ \beta $ as $ L_\beta=1/(1-P_{\beta-1,\beta}P_{\beta,\beta-1}L_{\beta-1})$. The general recursive definitions of $ L_j$ and $ R_j$ are:

\begin{displaymath}\begin{array}{rll} L_j &=& \left\{ \begin{array}{ll} 1, & j=1... ...j+1}P_{j+1,j}R_{j+1}), & j<N. \\ \end{array}\right. \end{array}\end{displaymath} (C.2)

We can now calculate $ \mathcal{S}^{C_N}_{\beta,\beta}$ as

\begin{displaymath}\begin{array}{lll} \mathcal{S}^{C_N}_{\beta,\beta} &=& \displ... ...R_{\beta}}{L_{\beta}-L_{\beta}R_{\beta}+R_{\beta}}, \end{array}\end{displaymath} (C.3)

where we have used Equation C.2 and the multinomial theorem [242].

We can now derive $ \mathcal{S}_{\alpha,\beta}^{C_N}$ as follows. If $ \alpha>\beta$ we can write

$\displaystyle \mathcal{S}_{\alpha,\beta}^{C_N}=\mathcal{S}_{\alpha-1,\beta}^{C_N} P_{\alpha,\alpha-1} R_\alpha.$ (C.4)

$ \mathcal{S}_{\alpha-1,\beta}^{C_N}$ gives the total transition probability from $ \beta $ to $ \alpha-1$, so the corresponding probability for node $ \alpha $ is $ \mathcal{S}_{\alpha-1,\beta}^{C_N}$ times the branching probability from $ \alpha-1$ to $ \alpha $, i.e.  $ P_{\alpha,\alpha-1}$, times $ R_\alpha$, which accounts for the weight accumulated from all possible paths that leave and return to node $ \alpha $ and are restricted to nodes with indexes greater than $ \alpha $. We can now replace $ \mathcal{S}_{\alpha-1,\beta}^{C_N}$ by $ \mathcal{S}_{\alpha-2,\beta}^{C_N} P_{\alpha-1,\alpha-2} R_{\alpha-1}$ and so on, until $ \mathcal{S}_{\alpha,\beta}^{C_N}$ is expressed in terms of $ \mathcal{S}_{\beta,\beta}^{C_N}$. Similarly, if $ \alpha<\beta$ we have

$\displaystyle \mathcal{S}_{\alpha,\beta}^{C_N}=\mathcal{S}_{\alpha+1,\beta}^{C_N} P_{\alpha,\alpha+1} L_\alpha,$ (C.5)

and hence

$\displaystyle \mathcal{S}_{\alpha,\beta}^{C_N}=\left\{ \begin{array}{ll} \mathc... ...rod_{i=\beta+1}^{\alpha} P_{i,i-1} R_{i}, & \alpha > \beta. \end{array} \right.$ (C.6)

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