Page 322 - Applied Probability

311
14. Poisson Approximation
the right of X (1) provide an exponentially distributed sample of size n − 1
starting at X (1) . Duplicating our argument for X (1) , we find that the differ-
ence X (2) − X (1) is independent of X (1) and exponentially distributed with
intensity (n−1)λ. Arguing inductively we now see that Z 1 = X (1) and that
the differences Z i+1 = X (i+1) − X (i) are independent and that Z i is expo-
nentially distributed with intensity (n − i +1)λ. From the representation
n

M n = X (n) = Z i , we can read off the first two moments
i=1
n
1 ln n γ
E(M n )= ≈ +
iλ λ λ
i=1
n 2
1 π
Var(M n )= ≈ .
2 2
i λ 6λ 2
i=1
The normalized random variable Y n = λM n / ln n has mean 1 and vari-
ance tending to 0. Hence, the sequence Y n converges in probability to 1.
With more effort, one can prove that it converges almost surely to 1. The
Erd¨os-R´enyi law [7] generalizes this almost sure convergence result to global
sequence matches without gaps. Arratia et al. [3, 4] prove analogs of the
Erd¨os-R´enyi law for local sequence alignments.
k
k
One can improve on the moment approximation E( M n ) ≈ E(M ).
n
For instance roughly M n è M n − U, where U is uniform on [0, 1] and
independent of M n. Because λ =1/ log 1 e, it follows that
q
1
E( M n ) ≈ E(M n ) −
2
1
=log 1 n + γ log 1 e −
q q 2
1
Var( M n ) ≈ Var(M n )+
12
2
π log 1 e 1
= q + .
6 12
14.8 Problems
1. Prove that the Chen-Stein bound (14.1) implies the bound (14.2)
when the inequality U α ≥ V α holds for all α.

2. Show that in the neighborhood method λ − Var(S)= b 1 − b 2 .

3. For a random permutation σ 1 ,... ,σ n of {1,... ,n},let X α =1 {σ α =α}
be the indicator of a match at position α. Show that the total number