Page 316 - Applied Probability

305
14. Poisson Approximation
exceed d. If, on the other hand, W 1 <d, then resample W 1 conditional on
the event W 1 ≥ d to get W .For α> 1, replace the gap W α − W α−1 by
∗
1
the gap (W α − W α−1 )(1 − W )/(1 − W 1 ) so that the points to the right
∗
1
of W 1 are uniformly chosen from the interval [W , 1] rather than from
∗
1
[W 1 , 1]. This procedure narrows all remaining gaps but leaves them in the
same proportion. If we now define V 1 as the number of remaining gaps that
exceed d in length, it is clear that V 1 has the same distribution as S − 1
conditional on X 1 = 1. Because U 1 ≥ V 1 , the Chen-Stein inequality (14.2)
applies.
To calculate the mean λ =E(S), we again focus on the first interval. The
n
identity Pr(X 1 = 1) = Pr(W 1 ≥ d)=(1 − d) and symmetry then clearly
n
imply that λ =(n + 1)(1 − d) . In similar fashion, we calculate
Var(S)=(n + 1) Var(X 1 )+(n +1)n Cov(X 1 ,X 2 )
n
=(n + 1)(1 − d) − (n + 1)(1 − d) 2n
2n
+(n +1)n E(X 1 X 2 ) − (n +1)n(1 − d) .
Because
E(X 1 X 2 )=Pr(X 1 =1,X 2 =1)
1 1
n−2
= n(n − 1)[1 − u (2) ] du (2) du (1)
d u (1) +d
1−d
= n[1 − d − u (1) ] n−1 du (1)
d
=(1 − 2d) n
for 2d< 1, it follows that
n
Var(S)=(n + 1)(1 − d) − (n + 1)(1 − d) 2n
2n
n
+(n +1)n(1 − 2d) − (n +1)n(1 − d) .
If d is small and n is large, then one can demonstrate that Var(S) ≈ E(S),
and the Poisson approximation is good [5].
It is of some interest to estimate the average number of markers required
to reduce the largest gap below d. From the Poisson approximation, the
1
median n should satisfy e −(n+1)(1−d) n ≈ . This approximate equality can
2
be rewritten as
− ln(n +1)+ln ln 2
n ≈ (14.4)
ln(1 − d)
and used iteratively to approximate the median. If one chooses evenly
spaced markers, it takes only 1 d markers to saturate the interval [0, 1].
For the crude guess n = 1 , substitution in (14.4) leads to the improved
d