Page 323 - Applied Probability

14. Poisson Approximation
312
n
X α satisfies the coupling bound

of matches S =
α=1
−1
)
2(1 − e
,
L(S) −L(Z) Ø
n
where Z follows a Poisson distribution with mean 1. (Hint: Use in-
equality (14.1) rather than inequality (14.2).)
4. In certain situations the hypergeometric distribution can be approx-
imated by a Poisson distribution. Suppose that w white balls and b
black balls occupy a box. If you extract n< w + b balls at random,
then the number of white balls S extracted follows a hypergeometric
distribution. Note that if we label the white balls 1,...,w, and let
X α be the random variable indicating whether white ball α is cho-
w
sen, then S = X α . Show that you can construct a coupling by
α=1
performing the sampling experiment in the usual way. If white ball α
does not show up, then randomly take one of the balls extracted and
exchange it for white ball α. Calculate an explicit Chen-Stein bound,
and give conditions under which the Poisson approximation to S will
be good.
n
5. Consider the n-dimensional unit cube [0, 1] . Suppose that each of
its n2 n−1 edges is independently assigned one of two equally likely
orientations. Let S be the number of vertices at which all neighboring
edges point toward the vertex. The Chen-Stein method implies that
S has an approximate Poisson distribution Z with mean 1. Verify the
estimate
L(S) −L(Z) Ø (n + 1)2 −n (1 − e −1 ).
n
(Hint: Let I be the set of all 2 vertices, X α the indicator that vertex
α has all of its edges directed toward α, and B α = {β : β −α Ø 1}.
Note that X α is independent of those X β with β − α > 1. Also,
b 2 = 0 because p αβ = 0 for β − α =1.)
6. A graph with n nodes is created by randomly connecting some pairs
of nodes by edges. If the connection probability per pair is p, then all
3
pairs from a triple of nodes are connected with probability p .For p
n
3
small and λ = p moderate in size, the number of such triangles
3
in the random graph is approximately Poisson with mean λ. Use the
neighborhood method to estimate the total variation error in this
approximation.
7. Suppose n balls (people) are uniformly and independently distributed
into m boxes (days of the year). The birthday problem involves find-
ing the approximate distribution of the number of boxes that receive
d or more balls for some fixed positive integer d. This is a special case