Page 321 - Applied Probability

14. Poisson Approximation
310
The Chen-Stein approximation does provide considerable insight into the
distribution of M mn. For instance, the approximate median of M mn satisfies
t
−λ
t
≈ 1/2. This gives mn(1 − q)q ≈ ln 2, or mn(1 − q)/ ln 2 ≈ (1/q) .
e
Solving for t yields t ≈ log 1 [mn(1 − q)/ ln 2]. This suggests that M mn is of
q
order log 1 [mn(1 − q)]. In fact, it is known [3, 19] that M mn has mean and
q
variance
1
E(M mn ) ≈ log 1 [mn(1 − q)] + γ log 1 e − (14.7)
q q 2
2

π log 1 e 1
Var(M mn ) ≈ q + , (14.8)
6 12
where γ ≈ .577 is Euler’s constant. Note that E(M nn ) grows like 2 log 1/q n
as n grows; Var(M nn ) stays virtually constant.
To gain some insight into formulas (14.7) and (14.8), it is instructive to
consider the simpler problem of characterizing the limiting behavior of the
maximum number of failures observed in n independent realizations of a
geometric waiting time with failure probability q per trial. The sequence
matching problem is more complicated because it involves the maximum of
mn dependent waiting times, with failure equated to matching and success
to nonmatching.
In the simplified problem, we construct a waiting time that counts the
number of failures before an ultimate success by taking the integer part
X of an appropriate exponential waiting time X.Now X can be viewed
as the time until the first random point of a Poisson process on [0, ∞). In
this setting the random variable X = k if and only if there are no random
points on the disjoint intervals [0, 1), [1, 2), ... , [k − 1,k) and at least one
random point on the interval [k, k+1). If the intensity of the Poisson process
is λ, then this event occurs with probability (e −λ k −λ ). It follows that
) (1−e
X is geometrically distributed with failure probability q = e −λ .
Now let X 1 ,... ,X n be n independent, exponentially distributed waiting
times with common intensity λ. Clearly, the integer part of the maximum
M n = max 1≤i≤n X i satisfies M n = max 1≤i≤n X i . In view of the in-
equalities 0 ≤ M n −x M n < 1, the moments of M n are approximately
the same as the moments of M n.
At first glance, calculating the moments of M n appears hard. However,
progress can be made by invoking a standard representation of the order
statistics X (1) < ··· <X (n) = M n [8]. Imagine the X i as random points
scattered on the interval [0, ∞). From the calculation
n
−nλx
Pr(X (1) ≥ x)= Pr(X i ≥ x)= e ,
i=1
we find that X (1) is exponentially distributed with intensity nλ. Because
of the lack of memory property of the exponential, the n − 1 points to