1
$\begingroup$

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.

$\endgroup$
16
  • $\begingroup$ Think carefully about what you want to conclude. "On average, one-third of the bits are 1, rest are 0" is not the same as "Every third bit is a 1, rest are 0". The latter is true if and only if the sequence is $001001001001\cdots$ which is easy to test for; the former is true not only for $001001001001\cdots$ but also for $0010000000111\cdots$ as well as for numerous other sequences. What do you wish to test for? $\endgroup$ – Dilip Sarwate Mar 26 at 20:09
  • $\begingroup$ Thanks for asking about the clarification. I definitely want to reject the sequence $0010000000111$. Recall that after errors, the sequence "re-starts" doing $001001001$, but the placement of $1$s might not be the same. I.e. before, you might have $1$ at $1, 4, 7$. Then $8$ is an errant $0$. After this, you would expect $1$ at $9, 12, 15...$. $\endgroup$ – genauguy Mar 26 at 20:29
  • $\begingroup$ Hi: you can use the test of proportions where, in this $p = 1$. under the null. But be careful here because $\hat{p}$ will be the number of 001 sequences out of the total number of three digit sequences. So, if you had say, 000001001000, then this is four three digit sequences and two of the four are 001 so your $\hat{p} = 2/4 = 0.5$. From there, you can carry out the proportions test at whatever significance level you choose. If you are not familiar with the test, any intro stat book will explain the steps. The only catch for your is what $\hat{p}$ is which I explained above. $\endgroup$ – mark leeds Mar 26 at 21:29
  • $\begingroup$ Are you assuming that you know the alignment of where the $1$s should be? $\endgroup$ – IanJ Mar 26 at 21:57
  • $\begingroup$ Also would you ever allow a slip? I.E. An extra or missing bit. $\endgroup$ – IanJ Mar 26 at 22:23
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you so much! One question. Our sequence is not IID. Given that you observe 001, the probability that the next sequence is 010 is quite high. If I assume that this sequence is ergodic (which I think just requires something mild about our the "noise" periods, then maybe I can just take a random sample of spaced out trios, right? Those are as good as independent. $\endgroup$ – genauguy Mar 27 at 4:31
  • $\begingroup$ Hi: If the three digit sequences are not independent, then the proportions test can't be used. But I think what you're referring to as a fix to this is to randomly sample the sequences in order to sort of make them indepedent ? This sounds reasonable but you'll need a lot of sample data. I'm not sure why you refer to simulations ? Do you not have actual data ? $\endgroup$ – mark leeds Mar 27 at 18:40
  • $\begingroup$ No, we do have actual data. Sorry by "random sample" I mean randomly selected subsets of the series. $\endgroup$ – genauguy Mar 27 at 18:42
  • $\begingroup$ yes, you can sample with replacement to hopefully deal with the correlation. Note that this is called bootstrapping so you may want to google for an intro to that if you're not familar with the approach. You will sample to get what is a referred to ad a "boostrapped statistic" and then use that to test your hypothesis, construct a CI etc. The underlying distribution is no longer binomial ( because of the correlation ) but the boostrapped distribution can be used to test the hypothesis. There are some good intros out there. If you can't find one, let me know and I can try to find one. $\endgroup$ – mark leeds Mar 27 at 19:20
  • $\begingroup$ Yes I am familiar with bootstrapping. I should have connected the dots there.I will attempt this! $\endgroup$ – genauguy Mar 27 at 19:26
1
$\begingroup$

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
```
$\endgroup$
0
$\begingroup$

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.

Cross correlation of noisy data with superimposed shuffles.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.