Page 204 - Applied Probability

9. Descent Graph Methods
where j r = 0 or 1 according as the rth meiosis in j involves the transmission
of a grandmaternal gene or grandpaternal gene and similarly for k r .Ifwe
let θ i denote the recombination fraction between loci i and i + 1, then
m
t i (k | j) = (1 − θ i ) 1 {k r −j r =0 mod 2} θ 1 {k r −j r =1 mod 2} . 189
i
r=1
The meiosis indicators j and k can be viewed as elements of a commutative
group if we define addition by
j + k =[(j 1 + k 1 )mod 2,... , (j m + k m )mod2]
and the identity element by 0 =(0,..., 0). (See Problem 12 for the proper-
ties of a commutative group.) From the group perspective, Baum’s update
(9.13) becomes the convolution

α i+1 (k)= β i (j)t i (k − j)= β i ∗ t i (k),
j
where β i (j)= α i (j)φ i (y i | j). This suggests the possibility of exploiting
elementary Fourier analysis in the guise of the Walsh transform [16].
The Walsh transform turns a sequence a j indexed by a meiosis indicator
j into a new sequence ˆ a k indexed by a meiosis indicator k via
1 1 m

= (−1) k r j r
ˆ a k ··· a j
j 1 =0 j m =0 r=1

= (−1) k,j a j , (9.14)
j
m

where k, j = k r j r . The inverse Walsh transform
r=1
1
ˇ a k = (−1) k,j a j .
2 m
j
deserves its names because
1 1
(−1) l,k ˆ a k = (−1) l,k (−1) k,j a j
2 m 2 m
k k j
1
= a j (−1) k,j−l
2 m
j k
1 1 m
1 k r (j r −l r )
= a j ··· (−1)
2 m
j k 1 =0 k m =0 r=1
= a l .