Consider a process that produces binary strings of varying length $n$. A typical sample would include

$n\ $ I Number of strings

$1\ $ I $\ 3,000,000$

$2\ $ I $\ 800,000$

$3\ $ I $\ 350,000$

$4\ $ I $\ 200,000$

$5\ $ I $\ 130,000$

$6\ $ I $\ 90,000$


Assume that each string is a i.i.d. sequence of Bernoulli random variables with unknown probabilities $p$ of '0' and $q$ of '1'. I am particularly interested in the distribution of strings containing only '0', or 0-strings. More specifically, I would like to find the minimal $n$ such that the observed fraction of 0-strings of length $n$ among all strings of length n can be shown to be significantly different from the expected fraction (assuming the Bernoulli mechanism).

So I guess there are two related questions:

  1. How can one estimate $p$ and $q$ from the sample? I know the total number of strings of length n and the number of 0-strings for each $n$. The total number of '1' appearing among strings of length $n$ is also known.

  2. How do I go about testing whether the observed fraction of 0-strings of length $n$ is significantly different from the expected fraction?

Note. Please forgive me and feel free to correct any mistakes in the methodology, i.e. the assumption of Bernoulli distribution. I am essentially interested to find a statistically significant signal indicating that for a specific value of $n$ the observed fraction of 0-strings of length $n$ can not be explained by randomness (and to find the minimal length when it happens).


Your Answer

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

Browse other questions tagged or ask your own question.