3
$\begingroup$

In Handbook of applied cryptography, Golomb's randomness postulates are given: Let $s$ be a periodic sequence of period $N$. Golomb’s randomness postulates are the following.

R1: In the cycle $s_N$ of $s$, the number of $1$s differs from the number of $0$s by at most $1$.

R2: In the cycle $s_N$, at least half the runs have length $1$, at least one-fourth have length $2$, at least one-eighth have length $3$, etc., as long as the number of runs so indicated exceeds $1$. Moreover, for each of these lengths, there are (almost) equally many gaps and blocks.6

R3: The autocorrelation function $C(t)$ is two-valued. That is for some integer $K$, $C(t)=K$ for $t\neq 0 \pmod N$ while $C(0)=N.$

But why do those postulates make sense?

$\endgroup$
  • 1
    $\begingroup$ I fixed your autocorrelation definition that seemed to have dropped off. $\endgroup$ – kodlu Feb 12 at 4:48
3
$\begingroup$

They make sense as a starting point, for pseudorandomness.

R1. This is a strict balancedness condition, the difference is 1, in case $N$ is odd and zero is impossible.

R2. If you have an i.i.d. and unbiased binary source, the run length distribution is geometric, which in a finite length segment should follow the profile given in R2, due to the law of large numbers.

R3. Having an autocorrelation $C(t)$ of the form $$ C(t)=N I\{t=0\}+ f(t) I\{t \neq 0\} $$ where $I$ is the indicator function, with $f(t)$ small in absolute value is a feature of an i.i.d. independent sequence. By parseval $|f(t)|\leq 1$ is possible for odd lengths. Golomb chooses this off peak correlation function $f(t)$ as constant so phase information is not leaked.

Of course he also knew that algbraic structures, in particular cyclic difference sets, allowed one to mechanise this two level correlation.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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