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

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?

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).

• Sorry, I just updated the question, but I think your answer might still work. (might it even be simplified to a $2\times 2$ table?) However, I am not familiar with the use of the chi-square test for this purpose (I've used it in the past to test for independence...) – M.B.M. Nov 1 '14 at 5:37
• I don't understand what you're saying with your update. – Glen_b Nov 1 '14 at 5:38
• Hmmm.... I may have made things more complicated with the update. Basically, I am interested in finding out whether a substantial number of subsequences is not identical (I can tolerate a few non-identical subsequences, but not too many). I think your pointer to the chi-square test is what I need -- I gotta figure out how it works... – M.B.M. Nov 1 '14 at 5:50
• Oh, that's different -- that sounds more like classification or estimation, or even perhaps a particular form of equivalence testing. I can expand on the chi-square test, but your question now sounds different. – Glen_b Nov 1 '14 at 5:57
• I've given my problem a lot of thought, and I think that what I need is simply testing the null defined in $H_0$ against an alternate that $s_j$'s come from a different distribution. I think that I can use chi-square test for this, but still not completely sure how (though I should be able to figure it out after a night of sleep). One issue is that $p$ is unknown. Since the chi-squared test seems to testing the goodness of fit to a specific binomial, can I estimate $p$ from the data? And should I re-write my original question to reflect my thoughts? Thanks for all your help! – M.B.M. Nov 3 '14 at 7:07