Page 318 - Applied Probability

X α has the same expectation. Because the event {S m ≤ s} is equivalent to
X α > 0, it suffices to compute the probability S =0.

the event S =
α
−λ
The Chen-Stein approximation suggests that Pr(S =0) ≈ e
with

n
n

m
m+1
λ =
].
[(m +1)s − ms
m +1 E(X α )= m +1 14. Poisson Approximation 307
Karlin and Macken use this approximation with m = 10 to detect clustering
of PstI restriction sites in the E. coli bacterial genome [13].
m
To verify the substitution E(X α )= p α =(m+1)s −ms m+1 , we proceed
by conditioning on the position u of the leftmost of the m+1 points. Because
the remaining m points of α must lie within a distance s to the right of u,
it follows that
1−s 1

m
m
=(m +1) s du +(m +1) (1 − u) du
p α
0 1−s
m
=(m +1)s (1 − s)+ s m+1 (14.5)
m
=(m +1)s − ms m+1 .
Thus, if s is small,
n m m+1

λ = [(m +1)s − ms ]
m +1
n(n − 1) ··· (n − m) m
≈ s .
m(m − 1) ··· 1
s
If λ is to be bounded away from 0 and ∞, written λ 1, then n m+1 m 1.
Here n is taken as very large and s as very small.
To compute the Chen-Stein bound (14.3), it is convenient to define the
neighborhood B α = {β : |β| = m +1,β ∩ α = ∅}. Again X α is indepen-
dent of those X β with β outside B α . The Chen-Stein constant b 1 can be
expressed as
= |I||B α |p 2
b 1 α
n n n − m − 1 m m+1 2

= − [(m +1)s − ms ]
m +1 m +1 m +1
n−m−1

= λ 2 m+1
n
1 −
m+1

2 m +1 m +1
= λ 1 − (1 − ) ··· (1 − ) .
n n − m
Now for any m + 1 numbers a 1 ,...,a m+1 from [0, 1], standard inclusion–
exclusion arguments imply that

a 1 + ··· + a m+1 − a i a j ≤ 1 − (1 − a 1 ) ··· (1 − a m+1 )
1≤i<j≤m+1
≤ a 1 + ··· + a m+1 .