Consider the n-dimensional unit cube [0, 1]n. Suppose that each of its n2n−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).

(Hint: Let I be the set of all 2n 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, b2 = 0 because pαβ = 0 for β − α = 1.)