Hypothesis testing with binary pattern

Question

Let's say you have a sequence $\{x_i\}_{i = 1}^N$ of ones and zeros. You know that $P(x_i = 1) = \frac{1}{3}$.

You want to test two hypotheses

$H_0$: The sequence is $iid$ with $P(x_i = 1) \ \forall \ i$

$H_1$: The sequence is full of $001$ sub-sequences, but has noise. For example, the sequence might start off as $001001$, then have a period of random noise (where $P(x_i = 1) = \frac{1}{3}$).

After the period of noise, the sequence matches the $001001$ pattern again. Importantly, the $1$ values might land on different values than when it started.

That is, we are not testing whether $mod(i, 3) = 0 \implies x_i = 1$. We are merely testing whether the "normal" state of this sequence is batches of $001001001$ but those batches could start at any value.

Another way of putting this is that we allow for "extra" bits to be inserted.

Ideally, I would like to find a test statistic that enables me to reject the null in this scenario. One possible solution, suggested in the comments below, is to count the number of $001$ sequences, and compare to the number of $001$ sequences you would find under the null.

This is an interesting solution. I will have to think more about how one might construct a confidence interval or assymptotics for this statistic.

I appreciate your comments.

Update: After thinking about the scenario that we are working with more, I think I can safely assume that only $0$ values are inserted. This is a much simpler problem.

$H_0$: The sequence is $iid$ with $P(x_i = 1) = \sum_{i = 1}^N x_i$. We guess it's Bernoulli distributed according to the number of $1$s we observe in the data.

$H_1$: The sequence has lots of $001001001$ segments, but extra $0$ values get inserted at random into the sequence (which creates offsets as above).

I don't think this materially changes the approach too much, but means we no longer need to worry about the distribution of the "Noise" sequences.

Answer 1

Given what you explained, you can count the number of times the sequence is 001, 100 or 010. Then, $\hat{p}$ is defined as that count divided by the number of sequences, $N$.

If we define the null as the hypothesis that the proportion of good sequences is 1.0, then the test is

$H_0: p = 1.0$ versus $H_1: p \neq 1.0$

As far as testing the null, ( I'm assuming N is large here so that the normal approximation to the binomial holds ) you can calculate the test statistic

as $Z = \frac{ \hat{p} - p_{0}}{\sqrt{\frac{\bar{p}(1-\bar{p})}{N}}}$

and use $p_{0} = 1 $ and $\bar{p} = 0.5$. Then, reject the null if $|Z| > Z_{\frac{\alpha}{2}}$ where $\alpha$ is the critical value of the test.

The CI would be $\hat{p} ~ \pm Z_{\frac{\alpha}{2}} \times {\sqrt{\frac{\bar{p}(1-\bar{p})}{N}}}$.

If a digit in one of the three digit sequences is is missing or there's an extra, and you know this, then you can just count that sequence as a bad sequence.

Answer 2

You seem to describe a discrete hidden Markov chain X with hidden states (let's name them 1,2,3) and transition matrix

λ*[0 1 0; 0 0 1; 1 0 0] + (1 - λ)*ones(3,3)/3 

and observation operator

H(x) = x == 3

If λ == 1, you have a deterministic 1 2 3 1 2 3 1 2 3 latent sequence and will observe 0 0 1 0 0 1 0 0 1.... If λ == 1, the latent states are i.i.d 1 2 1 2 3 3 2 1 3 and you'll observe an i.d.d sequence of 0 0 0 0 1 1 0 0 1...

If you put a prior on λ, you can use Bayesian inference to estimate it, or otherwise maximum likelihood if you want. Related: Baum-Welch algorithm.

You can play with

using Random, LinearAlgebra, Distributions, StatsBase

P =  λ*[0 1 0; 0 0 1; 1 0 0] + (1 - λ)*ones(3,3)/3 
"""
      samplefrom(p)

Produces a sample from the probability distribution
with prob .mass vector p.

Helpful: to sample from the conditional distribution given state i

    j = samplefrom(P[i, :]) # : for all j

"""
samplefrom(p) = sample(1:3, weights(p))

"""
      samplefromchain(p, P, n)

Samples an n-step Markov chain with starting distribution p
with transition matrix P.
"""
function samplefromchain(p, P, n) # n is number of trans
      s = samplefrom(p)
      statevector = [s]
      for i in 1:n
            s = samplefrom(P[s, :])
            push!(statevector, s)
      end
      return statevector
end
```

Answer 3

I would take a different approach (less formal?) than @mschuaer.

1. Generate the autocorrelation of your sequence.
2. Shuffle your sequence by sampling from it without replacement (x1000)
3. Compare the actual autocorrelation with the shuffle.