An average-case sublinear forward algorithm for the haploid Li and Stephens model

We will write μ i ( j ) as shorthand for p ( o i | x j , i ) . We will also define the values of the initial probabilities p ( x j , 1 , o 1 | H ) = μ 1 ( j ) k , which can be derived by noting that if all haplotypes have equal probabilities 1 k of randomly being selected, and that this probability is then modified by the appropriate emission probability