Likelihood of the 'closest' vector having the same feature? Suppose I have vectors $\mathbf{x_1},\mathbf{x_2},\ldots,\mathbf{x_n}$, each sampled uniformly and independently from the set of vertices of the unit hypercube of dimension $d$, and that I'm then given a new vertex vector $\mathbf{v}$. If $\mathbf{x_c}$ denotes the closest of my $\mathbf{x}$ vertices to $\mathbf{v}$, does an expression exist for the probability $p$ that $\mathbf{x_c}_1 \neq \mathbf{v}_1$ (i.e. they differ in some given dimension)?
 A: Let $\mathbf D$ be the random variable representing the number of different coordinates (or the squared distance) between $\boldsymbol v$ and $\boldsymbol{x}_c$. Then by the law of total probability
$$
    \Pr[\boldsymbol v_1 \ne (\boldsymbol x_c)_1] = \sum_{k=0}^d \Pr[\boldsymbol v_1 \ne (\boldsymbol x_c)_1 \mid \mathbf D=k] \cdot \Pr[\mathbf D=k].
$$
By symmetry, $\Pr[\boldsymbol v_1 \ne (\boldsymbol x_c)_1 \mid \mathbf D=k] = \frac kd$: given that $\boldsymbol v$ and $\boldsymbol x_c$ differ in exactly $k$ coordinates, the probability is $\frac kd$ that the first coordinate is one of those $k$. So we get
$$
   \Pr[\boldsymbol v_1 \ne (\boldsymbol x_c)_1] = \sum_{k=0}^d \frac kd \cdot \Pr[\mathbf D = k] = \frac1d \sum_{k=0}^d k \cdot \Pr[\mathbf D =k] = \frac1d \mathbb E[\mathbf D].
$$

Now, we are going to compute $\mathbb E[\mathbf D]$ in a different way. For any nonnegative integer-valued random variable $\mathbf X$, the identity
$$
   \mathbb E[\mathbf X] = \sum_{k=1}^\infty \Pr[\mathbf X \ge k]
$$
holds, because $\Pr[\mathbf X=k]$ is included in the $k$ probabilities $\Pr[\mathbf X \ge 1], \Pr[\mathbf X\ge 2], \dots, \Pr[\mathbf X \ge k]$.
In the case of $\mathbf D$, $\Pr[\mathbf D \ge k] = \left(1 - \frac1{2^d} \sum_{i=0}^{k-1} \binom di\right)^n$, which is just the probability that none of $\boldsymbol x_1, \dots, \boldsymbol x_n$ are closer than that to $\mathbf v$. So we get
$$
   \Pr[\boldsymbol v_1 \ne (\boldsymbol x_c)_1] = \frac1d \sum_{k=1}^d \left(1 - \frac1{2^d} \sum_{i=0}^{k-1} \binom di\right)^n.
$$
Unfortunately, that's maybe as simple as it gets. We've gotten a pretty nice expression for the probability as a function of $n$, when $d$ is fixed and not too large; when $d$ can also vary, this sum probably has no nice closed form, because the partial sum of binomial coefficients inside it doesn't.
