Let gn be the 1-NN classification rule. Prove that                         lim n→∞ P{gn(X) = Y } = 1 − M j=1 E{m(j) (X) 2 } for all distributions of (X, Y ), where m(j) (X) = P{Y = j|X} (Cover and...

Let gn be the 1-NN classification rule. Prove that

                        lim n→∞ P{gn(X) = Y } = 1 − M j=1 E{m(j) (X) 2 }

for all distributions of (X, Y ), where m(j) (X) = P{Y = j|X} (Cover and Hart (1967), Stone (1977)).

Hint:

Step (a). Show that

                                P{gn(X) = Y } = 1 − M j=1 P{Y = j, gn(X) = j}

                               = 1 − M j=1 E{m(j) (X)m(j) (X(1,n)(X))}.

Step (b). Problem 6.3 implies that

                               lim n→∞ E{(m(j) (X) − m(j) (X(1,n)(X)))2 } = 0.