Page 279 - Applied Probability

267
12. Models of Recombination
tΦ
left block. More to the point, the entries of q ij (t)of e
evaluated as
(12.11)
k−j
(λt)

j> 0
k>j
for i = 0, and as q 0j (t) = & e −λt s k (k−j)! e −λt j =0 can be explicitly
0 j> i or j =0
,
q ij (t) = (λt) i−j −λt (12.12)
(i−j)! e 0 <j ≤ i
for i> 0.
The solutions (12.11) and (12.12) can be established by path-counting
arguments. For instance, the expression for q 00 (t) is based on the obser-
vation that the Poisson-skip process cannot leave state 0 and return to it
without encountering a χ point. The process stays in state 0 with proba-
bility e −λt . On the other hand, the process can leave state 0 and end up
in state j> 0 if the kth point to its right is the next χ point and if it
encounters k − jo points during the time interval [0,t]. Conditioning on
the value of k gives the expression in (12.11) for q 0j (t) when j> 0. Similar
reasoning leads to the expressions (12.12) for q ij (t) when i> 0.
Although at first glance finding explicit solutions for the entries p ij (t)
of e tΓ seems hopeless, some simplification can be achieved by considering
the discrete renewal process corresponding to how many random points are
skipped. Starting from a χ point, let u n be the probability that the nth
point to the right of the current point is a χ point. By definition, u 0 =1.
Furthermore, the probabilities u n satisfy the classical recurrence relation
u n = s 1 u n−1 + s 2 u n−2 + ··· + s n−1 u 1 + s n u 0,
which enables one to compute all of the u n beginning with u 0 . This re-
currence is derived by conditioning on the number of the next-to-last χ
point.
Armed with these probabilities, we can now express
∞
(λt) i−j −λt (λt) i+n −λt
e e
p ij (t)=1 {0<j≤i} +1 {j=0} u n
(i − j)! (i + n)!
n=0
∞ i+n+k−j
(λt) −λt
u n s k e . (12.13)
+1 {j>0}
(i + n + k − j)!
n=0 k>j
e
Indeed, the first term (λt) i−j −λt /(i − j)! of (12.13) expresses the prob-
ability of encountering i − jo points during [0,t]; this is relevant when
there is a direct path from state i to j that does not pass through state
0. The term u n (λt) i+n −λt /(i + n)! is the probability of passing through
e
the i − 1 current o points to the right, hitting the next χ point, and re-
turning to a χ point after encountering n further points. Finally, the term