2
$\begingroup$

I have seen this short, wonderful video about the frequency stability property (also there is another video from this guy under his Kickstarter project ArtOfTheProblem; they are both great, and I highly recommend them).

It basically said that when you have two sequences of 0s and 1s you can determine which of those two sequences was truly generated randomly (using a coin flip procedure) and which one was generated by a human trying to act randomly. The trick to discern the two sequences from one another starts with counting non-overlapping segments of length 3. For any sequence you pick, the proportion of times it occurs should be the same as all the other sequences.

Consider following example

1010001101

Three questions:

1st: Which 3 numbers should we observe? Or in another words, should the window of size 3 overlap? Is this the correct histogram?

2 x 101
1 x 010
1 x 100
1 x 000
1 x 001
1 x 011
1 x 110

Or if the window should not overlap then what to do with last 1:

1x 101
1x 000
1x 110
1??

2nd: Why should be observer 3 subsequent numbers? Does it have something to do that the string consist of two numbers (0 and 1)? What would happen if we observe 4,5,6 ... subsequent numbers?

3rd: Do you know some other channel on youtube like this one?

EDIT: I've done experiments using (non)overlapping window, results are here

Improve this question
$\endgroup$
1
$\begingroup$

I take it that he means the sequences don't overlap. If you look at a sequence of length $n=3$, and the sequences are equally likely, then the probability of any sequence is $\frac{1}{2^3}=\frac{1}{2^n}$, since there are $2^3=2^n$ possible sequences.

Now say you observe length $n$ sequences $m=10$ times. Then that's a total of $n\cdot m = 30$ numbers. But instead of thinking about $30$ numbers, think about $10=m$ indicator functions that are based on the $10$ sequences of three you saw. Define $1_1, \ldots 1_m$ as indicator functions that are just $1$ if your sequence that you pick is observed, and $0$ otherwise. The sum of these indicators follows a binomial distribution with parameters $m$ and $p = 2^{-n}$. Let's call it $Y$.

So $Y = \sum_{i=1}^m 1_i$. By the law of large numbers $\bar{1} = \frac{Y}{m} \to \frac{m 2^{-3}}{m} = 2^{-3}$. This is true for any arbitrary sequence.

$\bar{1}$ is the proportion of occurences of any sequence you pick. If you looked at sequences of a difference length, replace $n$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Given this analysis, could you now answer the questions? Specifically, (1) should the algorithm look at overlapping windows or not (and why?) and (2) what will happen when $3$ is increased (and, implicitly, why exactly might $3$ have been chosen for this test)? $\endgroup$ – whuber♦ May 28 '15 at 21:51
  • $\begingroup$ Answering (1) objectively would (should?) involve knowing whether or not there exists a solution in the overlapping case. I don't know about that. I don't think the video is specific about this. As far as (2) goes, that's what my last paragraph answers. And I don't know why 3 was chosen for this test...perhaps because it was small, greater than 1, and not 2. $\endgroup$ – Taylor May 28 '15 at 23:52
  • $\begingroup$ Taylor, thank you for reply bud i still did not get the point. My math background is not as strong as yours. I went lost when you start talking about summing indicators (just fancy name for saying if I've already saw the sequence?) and binomial distribution. $\endgroup$ – Wakan Tanka May 29 '15 at 0:35
  • $\begingroup$ So to be more direct: don't look at overlapping sequences, and also make sure the total length is divisible by 3 so you don't have any leftovers/incomplete seqs of length 3. Question 2: there is no strong reason not to look at sequences of length 4,5,... etc. Questuon 3: no not really $\endgroup$ – Taylor May 29 '15 at 16:46
  • $\begingroup$ 1. when there is very long sequence then the remainder wont have any significant impact on result or will it? The question might also stand: how long the input sequence must be so the possible remainder wont affect the result? Or what is the tolerable deviaton among histogram members? I thing there is not a clear answer for this and it is some deal in statistics or am I wrong? $\endgroup$ – Wakan Tanka Jun 3 '15 at 21:22

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.