Page 324 - Applied Probability

14. Poisson Approximation
of the W d Poisson approximation treated in the text by the coupling
method. In this exercise we attack the birthday problem by the neigh-
borhood method. To get started, let the index set I be the collection
of all sets of trials α ⊂{1,... ,n} having |α| = d elements. Let X α be
the indicator of the event that the balls indexed by α all fall into the
same box. Argue that the approximation Pr(W d =0) ≈ e −λ with 313
n 1

λ =
d m d−1
is plausible. Now define the neighborhoods B α so that X α is inde-
pendent of those X β with β outside B α . Prove that the Chen-Stein
constants b 1 and b 2 are
2d−2

n n n − d 1
=
b 1 −
d d d m
2d−i−1
d−1
n d n − d 1
b 2 = .
d i d − i m
i=1
When d = 2, compute the total variation bound
n
1 − e −λ 1 − e −λ (4n − 7)
2
(b 1 + b 2 ) = .
λ λ m 2
8. In the somatic cell hybrid model, suppose that the retention probabil-
1 n n n n
2
1
1
3
2
ity p = . Define w n,d 12 ,d 13 =Pr[ρ(C ,C )= d 12 ,ρ(C ,C )= d 13 ]
for a random panel with n clones. Show that
d−1 d−1

= ,
p αβ w n,d 12 ,d 13
d 12 =0 d 13 =0
regardless of which β ∈ B α \{α} is chosen [10]. Setting r = p(1 − p),
verify the recurrence relation
+ w n,d 12 ,d 13 −1 + w n,d 12 −1,d 13 −1 )
w n+1,d 12 ,d 13 = r(w n,d 12 −1,d 13
.
+(1 − 3r)w n,d 12 ,d 13
is 1 when d 12 = d 13 =0
Under the natural initial conditions, w 0,d 12 ,d 13
and 0 otherwise.
9. In the somatic cell hybrid model, suppose that one knows a priori that
the number of assay errors does not exceed some positive integer d.
Prove that assay error can be detected if the minimum Hamming
distance of the panel is strictly greater than d. Prove that the locus
can still be correctly assigned to a single chromosome if the minimum
Hamming distance is strictly greater than 2d.