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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.