In this question, we study the limiting properties of the k-nearest neighbour algorithm. Suppose tha ...

---

In this question, we study the limiting properties of the k-nearest neighbour algorithm. Suppose that we are given n data points X_1, ..., X_n, sampled uniformly and independently from the interval [0, 2], and one test point y = 1. Let Z_i = |X_i - y| denote the distance of y to the data point X_i, and let Z_(i) denote the distance of y to its i-th nearest neighbour, so that Z_(1) < ... < Z_(n). (a) Show that the random variable Z_i is uniformly distributed on the unit interval [0, 1]. (b) Show that E[Z_(1)] = 1/(n + 1); that is, the expected distance to the first nearest neighbour is 1/(n + 1). (Hint: it may help to first compute P{Z_(1) > t}. Note that Z_(1) = min over i of Z_i, so P{Z_(1) > t} = P{min over i of Z_i > t}.)