# Golomb's Randomness postulates

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?

• I fixed your autocorrelation definition that seemed to have dropped off. – kodlu Feb 12 '19 at 4:48

R1. This is a strict balancedness condition, the difference is 1, in case $$N$$ is odd and zero is impossible.
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.