Page 306 - Applied Probability

13. Sequence Analysis
294
(b) Show that the likelihood ratio test rejects the null hypothesis
λ = λ 0 whenever the statistic
n

T
=2λ 0
i=1 X i
is too large or too small.
(c) Prove that T has a χ 2 distribution.
4n
2. Use the Borel-Cantelli lemma [4] to prove that the pattern SFS of a
success, failure, and success occurs infinitely many times in a sequence
of Bernoulli trials. This result obviously generalizes to more complex
patterns.
3. Renewal theory deals with repeated visits to a special state in a sto-
chastic process [3, 4]. Once the state is entered, the process leaves it
and eventually returns for the first time after n> 0 steps with proba-
bility f n . The return times following different visits are independent.
Define u n to be the probability that the process is in the special state
at epoch n given that it starts in the state at epoch 0. Show that
u n = f 1u n−1 + f 2 u n−2 + ··· + f n u 0
for n ≥ 1. If we define the generating functions U(s)= ∞ u n s n
n=0
n
and F(s)= ∞ f n s with f 0 = 0 and u 0 = 1, then prove that
n=0
U(s)= [1 − F(s)] −1 .
4. Repeated visits to a pattern such as GCGC in a DNA sequence consti-
tute a renewal process as noted in the text. Given the assumptions of
Section 13.2, one can calculate the generating functions U(s) and F(s)
defined in Problem 3 for renewals of the pattern R =(r 1 ,... ,r m ). If
and
we let p R = p r 1 ··· p r m
1 k =0
&
= 1 1 ≤ k ≤ m − 1 ,
q k (m−k)
p r m−k+1 ··· p r m {R
=R (m−k) }
0 k ≥ m
then show that
n−1

= (13.11)
p R u n−k q k
k=0
for n ≥ m. Use this to prove that
p R s m
=[U(s) − 1]Q(s) (13.12)
1 − s
m
p R s +(1 − s)Q(s)
U(s) =
(1 − s)Q(s)