STAT333 Lecture Notes - Lecture 13: Equivalence Class, Random Variable, Part Of Speech
Document Summary
For n z+, de ne: i,j = p (xn = j, xn 1 (cid:54)= j, . , x2 (cid:54)= j, x1 (cid:54)= j|x0 = i) i, j. f (n) This is the probability that starting from state i, the rst visit to state j occurs at time n. Note that f (1) for n z+, we consider the quantity p (n) i,j and condition on the time the rst visit to state j is made. More generally, to obtain a recursive expression to compute f (n) i,j. P (n) i,j = n(cid:88) k=1 j,j i,j p (n k) f (k) n 1(cid:88) = f (n) i,j p (0) j,j + i,j p (n k) f (k) j,j n 1(cid:88) k=1 i,j p (n k) f (k) j,j k=1 i,j p (n k) f (k) j,j. = f (n) i,j + i,j n 1(cid:88) k=1 i,j = p (n) f (n) which can be rearranged to give.