Prove Theorem 25.17. Hint: Put m
¯ R(x) = ‑ Sx,R m(z)µ(dz) µ(Sx,R) ,
then, by Lemma 24.6,
im R→0 m¯ R(x) = m(x) mod µ.
Given x − X(kn,n)(x)= R, the distribution of
(X(1,n)(x), Y(1,n)(x)),..., (X(kn,n)(x), Y(kn,n)(x))
is the same as the distribution of the nearest neighbor permutation of the i.i.d.
(X∗ 1 (x), Y ∗ 1 (x)),..., (X∗ kn (x), Y ∗ kn (x)),
where
P{X∗ i (x) ∈ A, Y ∗ i (x) ∈ B} = P{Xi ∈ A, Yi ∈ B|Xi ∈ Sx,R},
therefore,
E{Y ∗ i (x)} = E{Yi|Xi ∈ Sx,R} = ¯mR(x).
Thus, by Hoeffding’s inequality,
P 1 kn kn i=1 Y(i,n)(x) − m¯ R(x) > x − X(kn,n)(x)
= R = P 1 kn kn i=1 (Y ∗ i (x) − EY ∗ i (x)) >
≤ 2e − kn2 2L2 ,
which is summable because of kn/ log n → ∞.