Prove Theorem 8.2. Hint: Step (1). With h = k, follow the line of the proof of Theorem 8.1 until (8.4):
n j=1 (m(h) n,j (Xj ) − Yj ) 2 − n j=1 (m(h) n,j (X j ) − Y j ) 2
≤ 4L2 + 4L n j=2 |m(h) n,j (Xj ) − m(h) n,j (Xj )|.
Step (2). Apply Corollary 6.1 to show that
n j=2 |m(k) n,j (Xj ) − m(k) n,j (Xj )| ≤ 4Lγd.
According to Corollary 6.1,
n j=2 |m(k) n,j (Xj ) − m(k) n,j (Xj )|
= n j=2 1 k Y1I{X1 among X1,...,Xj−1,Xj+1,...,Xn is one of the k NNs of Xj}
1 k l∈{2,...,n}−{j} YlI{Xl among X1,...,Xj−1,Xj+1,...,Xn is one of the k NNs of Xj}
−1 k Y 1 I{X 1 among X 1,...,Xj−1,Xj+1,...,Xn is one of the k NNs of Xj} −1 k l∈{2,...,n}−{j}
YlI{Xl among X 1,...,Xj−1,Xj+1,...,Xn is one of the k NNs of Xj}
≤ 1 kL n j=2 I{X1 among X1,...,Xj−1,Xj+1,...,Xn is one of the k NNs of Xj}
+ 1 kL n j=2 I{X 1 among X 1,...,Xj−1,Xj+1,...,Xn is one of the k NNs of Xj}
+ 1 kL n j=2 l∈{2,...,n}−{j}
I{Xl among X1,...,Xj−1,Xj+1,...,Xn is one of the k NNs of Xj}
−I{Xl among X 1,...,Xj−1,Xj+1,...,Xn is one of the k NNs of Xj}
≤ Lγd + Lγd + 2Lγd.