Appendix C
Pathway Sums for Chain Graphs, 𝒮α,βCN

To obtain the total probability of leaving the chain CN via node α if started from node β, i.eαCN𝒮α,βCN, we must calculate the pathway sum 𝒮α,βCN. We start with the case α = β and obtain 𝒮β,βCN. Consider any path that has reached node N 1. The probability factor due to all possible N 1 to N recrossings is simply RN1 = 1(1 PN1,NPN,N1). 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

RN2 = m=0(P N2,N1PN1,N2RN1)m = 1 1 PN2,N1PN1,N2RN1. (C.1)

Similarly, we can continue summing contributions in this way until we have recrossings of β to β + 1, for which the result of the nested summations is Rβ = 1(1 Pβ,β+1Pβ+1,βRβ+1). Hence, Rβ is the total transition probability for pathways that return to node β and are confined to nodes with index greater than β without escape from CN.

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 L2 = 1(1 P1,2P2,1). Hence, the required probability for recrossings between nodes 2 and 3 including arbitrary recrossings between 1 and 2 is L3 = 1(1 P2,3P3,2L2). Continuing up to recrossings between nodes β 1 and β we obtain the total return probability for pathways restricted to this side of β as Lβ = 1(1 Pβ1,βPβ,β1Lβ1). The general recursive definitions of Lj and Rj are:

Lj = 1, j = 1, 1(1 Pj1,jPj,j1Lj1),j > 1, andRj = 1, j = N, 1(1 Pj,j+1Pj+1,jRj+1),j < N. (C.2)

We can now calculate 𝒮β,βCN as

𝒮β,βCN = m=0 n=0m n! m!(n m)! Pβ1,βPβ,β1Lβ1 n P β,β+1Pβ+1,βRβ+1 mn = m=0(P β1,βPβ,β1Lβ1 + Pβ,β+1Pβ+1,βRβ+1)m =(1 Pβ1,βPβ,β1Lβ1 Pβ,β+1Pβ+1,βRβ+1)1 = 1 Lβ 1 Lβ Rβ 1 Rβ 1 = LβRβ Lβ LβRβ + Rβ, (C.3)

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

We can now derive 𝒮α,βCN as follows. If α > β we can write

𝒮α,βCN = 𝒮α1,βCN Pα,α1Rα. (C.4)

𝒮α1,βCN gives the total transition probability from β to α 1, so the corresponding probability for node α is 𝒮α1,βCN times the branching probability from α 1 to α, i.ePα,α1, times Rα, 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 𝒮α1,βCN by 𝒮α2,βCNPα1,α2Rα1 and so on, until 𝒮α,βCN is expressed in terms of 𝒮β,βCN. Similarly, if α < β we have

𝒮α,βCN = 𝒮α+1,βCN Pα,α+1Lα, (C.5)

and hence

𝒮α,βCN = 𝒮β,βCN i=αβ1P i,i+1Li,α < β, 𝒮β,βCN i=β+1αP i,i1Ri,α > β. (C.6)