1
$\begingroup$

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

$\endgroup$

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.