Testing for samples being drawn from identical Bernoulli r.v.'s

Question

Suppose that I have a sequence of size $n$: $x_1,\ldots,x_n$, $x_i\in\{0,1\}$. My null hypothesis is that all $n$ members of the sequence are drawn independently from an identical Bernoulli distribution with $P(x_i=1)=p$. My alternate hypothesis is that the $j$-th subsequence of length $m$ is drawn independently from an identical Bernoulli distribution with $P(x_i=1)=p_j$ for $(j-1)m<i\leq jm$, $1\leq j \leq n/m$ such that there exists $p_{\mathcal{X}}$ which partitions the set of subsequences; that is, letting $\mathcal{X}=\{j: p_j<p_{\mathcal{X}}\}$, $|\mathcal{X}|=\gamma n$ with $\gamma\in(0,1)$ a test parameter. We assume that the draws are independent across subsequences.

The fact that the sums of the subsequences $s_j=\sum_{i=(j-1)m+1}^{jm}x_i$ are drawn from binomial distribution yields the following alternative statement of the hypotheses:

$$H_0: s_j\sim \text{Binomial}(p,m), 1\leq j \leq n/m\\ H_1:s_j\sim \text{Binomial}(p_j,m)~\text{and there exists}~p_{\mathcal{X}}~\text{such that}~\mathcal{X}=\{j: p_j<p_{\mathcal{X}}\}, |\mathcal{X}|=\gamma n$$

Is there a statistical test between these two hypotheses given a parameter $\gamma$? We know $n$ to be very large, order of hundreds of millions, $m$ is also large, order of tens of thousands, $p$ and $p_j$'s are unknown, but small (order of $10^{-4}$ so zeros are prevalent). Any suggestions?

Answer 1

There are a variety of tests used in this circumstance.

The most commonly used test in this situation is a chi-square test.

It's essentially testing for homogeneity of proportions.

You can write the counts as a $2\times\frac{n}{m}$ table of counts (notionally 'successes' and 'failures' vs the $n/m$ groups) on which you carry out the usual chi-square test.

Here's an example. The rows represent the subsequences and the columns '1's and '0's while the interior of the table are the counts for each combination:

       '1'    '0'
subseq  sc    fc
    1   1   12112
    2   1   12329
    3   0   11974
    4   1   12029
    5   4   12151
    6   3   12096
    7   1   12075
    8   0   11908
    9   0   11973
    10  0   12043
    11  1   11985
    12  2   12138
    13  0   12241
    14  2   12036
    15  2   11803

A chi-square test of homogeneity works like a chi-square test of independence.

Software will carry this test out, but it's simple enough to do:

1. We compute expected values for each count as the product of the marginal totals over the overall total: $E_{i,j}=R_i\cdot C_j/N$

For the small table above, the expected counts are:

  1.205200 12111.79
  1.226791 12328.77
  1.191370 11972.81
  1.196942 12028.80
  1.209379 12153.79
  1.203807 12097.80
  1.201519 12074.80
  1.184804 11906.82
  1.191271 11971.81
  1.198236 12041.80
  1.192564 11984.81
  1.207887 12138.79
  1.217936 12239.78
  1.197738 12036.80
  1.174555 11803.83

Then we compute $\sum_{i,j} \frac{(O_{ij}-E_{ij})^2}{E_{ij}}$, where $O_{ij}$ are the observed counts in the first table and $E_{ij}$ are the expected counts in the second table.

That sum is the chi-squared statistic. Under the null hypothesis, this test statistic has a chi-squared distribution (approximately). It has degrees of freedom equal to $(n_r-1)(n_c-1)$ where $n_c$ is the number of rows and $n_r$ is the number of columns. Since $n_c=2$, for your data it's one fewer than the number of subsequences.

Under the conditions you described, the expected count in the first (i.e. '1's) column will typically be close to 1. Some programs will warn against using the chi-square in this situation, but with so many rows, the distribution of the test statistic should be very well approximated by the nominal chi-square distribution.

For the above data, the chi-squared statistic is 16.92, the df = (15-1)(2-1) = 14, and the p-value is 0.2607

You might find it useful to identify the most unusual cells - those with large values of $\frac{O_i-E_i}{\sqrt{E_i}}$ (either large positive or large negative, though with small expected values, large negative values won't occur).