# Control the variance of some coincidence statistic

Let $X = X_1, \cdots, X_m \sim D_d$ a sample of size $m$ from a $[d]$-supported distribution.

Let $$K_1 = K_1(X_1, \cdots, X_m) = \sum_{i = 1}^{d} \unicode{x1D7D9}\{B_i = 1\}$$ with $$B_i = B_i(X_1, \cdots, X_m) = |\{ j \in [d] : X_j = i \}|$$

i.e. $K_1$ is the number of bins into which exactly one sample has fallen.

Our goal is to upper bound the variance of the $K_1$ statistic over the sample.

In Paninski's work, A coincidence-based test for uniformity given very sparsely-sampled discrete data, at the top of the right column of page 3 (Lemma 2), the author states the following equality:

$$\frac{1}{2} \underset{X_1, \cdots, X_m, X_1', \cdots, X_m'}{\mathbf{E}}{\sum_{j = 1}^{m} (K_1 - K_1^{(j)})^2} = \frac{m}{2} \underset{X_1, \cdots, X_{m-1}}{\mathbf{E}}{\left[\sum_{1 \leq i, j \leq d} p_i p_j \left( \unicode{x1D7D9}\{n_i = 0 \cap n_j > 0\} + \unicode{x1D7D9}\{n_j = 0 \cap n_i > 0\} \right)\right]}$$

I cannot get the same though. Let's go through the steps.

$\forall j \in [m]$ define $K_1^{(j)} = K_1(X_1, \cdots, X_{j-1} , X_{j}' ,X_{j-1}, \cdots, X_m)$ with $X_j'$ an independent copy of $X_j$. By the Efron-Stein inequality from the independence of the $X_j$,

$$\mathbf{Var}[K_1] \leq \frac{1}{2} \underset{X_1, \cdots, X_m, X_1', \cdots, X_m'}{\mathbf{E}}{\sum_{j = 1}^{m} (K_1 - K_1^{(j)})^2}$$

For all $j \in [m]$, $K_1 - K_1^{(j)} = \sum_{i = 1}^{d} (\unicode{x1D7D9}\{B_i = 1\} - \unicode{x1D7D9}\{B_i^{(j)} = 1\} )$ where $$B_i^{(j)} = B_i(X_1, \cdots, X_{j-1} , X_{j}' ,X_{j-1}, \cdots, X_m).$$

Notice that this difference is the same for all $j$ by symmetry of the problem, so that,

$$\frac{1}{2} \underset{X_1, \cdots, X_m, X_1', \cdots, X_m'}{\mathbf{E}}{\sum_{j = 1}^{m} (K_1 - K_1^{(j)})^2} = \frac{m}{2} \underset{X_1, \cdots, X_{m-1}}{\mathbf{E}}{\left[\underset{X_{m}, X_{m}'}{\mathbf{E}}{\left[(K_1 - K_1^{(m)})^2 | X_1=x_1, \cdots X_{m-1} = x_{m-1} \right]}\right]}$$

So it would remain to prove that

$$\underset{X_{m}, X_{m}'}{E}{\left[(K_1 - K_1^{(m)})^2 | X_1=x_1, \cdots X_{m-1} = x_{m-1}\right]} = \sum_{1 \leq i, j \leq d} p_i p_j \left( \unicode{x1D7D9}\{n_i = 0 \cap n_j > 0\} + \unicode{x1D7D9}\{n_j = 0 \cap n_i > 0\} \right)$$

where $n_i$ is a shorthand for $B_i(x_1, \dots, x_{m-1})$. This is the part I am stuck at and asking for your help. It seems that the cases where $|K_1 - K_1^{(m)}| = 2$ have somehow disappeared from the summation.