Let gn be the k-NN classification rule for M classes:                     gn(x) = arg max 1≤j≤M k i=1 I{Y(i,n)(x)=j} Show that, for kn → ∞ and kn/n → 0,                     lim n→∞ P{gn(X) = Y } =...

Let gn be the k-NN classification rule for M classes:

                    gn(x) = arg max 1≤j≤M k i=1 I{Y(i,n)(x)=j}

Show that, for kn → ∞ and kn/n → 0,

                    lim n→∞ P{gn(X) = Y } = P{g∗(X) = Y }

for all distributions of (X, Y ), where g∗ is the Bayes decision rule (Devroye, Gy¨orfi, and Lugosi (1996)). Hint: Apply Problem 1.5 and Theorem 6.1.