What Are Random Sequences?

Random sequences are ordered collections of values, typically drawn from a finite alphabet such as binary digits, in which no element can be predicted from the preceding elements with probability better than chance. They occupy a central place in information theory, cryptography, and coding theory, where the unpredictability and statistical uniformity of a sequence determine its usefulness for tasks ranging from key generation to channel simulation. The concept connects mathematical probability theory, which defines randomness in terms of distributional properties, with computational complexity theory, which defines it in terms of the difficulty of prediction by efficient algorithms.

Defining randomness for a finite sequence is more subtle than it appears. A sequence of one million coin flips that alternates perfectly between 0 and 1 passes a frequency test but fails a runs test. For this reason, rigorous treatments of randomness require a sequence to satisfy multiple statistical criteria simultaneously, and the field distinguishes between sequences that are statistically random and sequences that are cryptographically random, a strictly stronger condition.

Formal Definitions of Randomness

Several competing formalizations of random sequences have been developed since the mid-twentieth century. Martin-Löf randomness, introduced in 1966, defines a random infinite binary sequence as one that passes all effective statistical tests, formalized as computably enumerable measure-zero sets. A sequence is Martin-Löf random if and only if its Kolmogorov complexity, the length of the shortest program that generates it, grows linearly with length. Schnorr randomness and Kurtz randomness provide weaker and more constructively accessible alternatives to Martin-Löf's criterion, each corresponding to a different class of statistical tests. These theoretical definitions inform the design of practical testing frameworks, including the NIST SP 800-22 statistical test suite, which applies fifteen distinct tests to assess whether finite binary sequences meet empirical randomness criteria.

Pseudorandom Sequences

Because truly random sequences cannot be generated deterministically, most practical systems rely on pseudorandom sequences: outputs of deterministic algorithms that are statistically indistinguishable from random sequences by tests of bounded computational complexity. The Blum-Blum-Shub generator and the NIST-approved deterministic random bit generators in SP 800-90A produce pseudorandom binary sequences satisfying the cryptographic next-bit test, which requires that no polynomial-time algorithm predicts the next bit with advantage greater than a negligible function. In spread-spectrum communications, maximal-length sequences (m-sequences) generated by linear feedback shift registers have period 2^n - 1 for an n-stage register and possess balanced, run, and correlation properties that closely mimic truly random sequences while remaining fully reproducible from a known seed. A detailed treatment of pseudorandom sequences and their algebraic structure shows how the theory of finite fields underlies the construction of sequences with guaranteed correlation properties.

Cryptographic and Coding Properties

Cryptographic applications demand that a sequence be statistically uniform and computationally unpredictable: knowledge of any prefix of the sequence must not enable efficient prediction of subsequent bits. This requirement, formalized as semantic security, goes well beyond passing statistical tests. In coding theory, pseudorandom sequences serve a different purpose: Gold codes and Kasami sequences are families of binary sequences with controlled cross-correlation properties that allow multiple users to share a spread-spectrum channel with minimal mutual interference, the principle underlying CDMA cellular networks. A guide to pseudo-random number generators and security models surveys both the security-theoretic and practical design considerations.

Applications

Random sequences have applications across a range of communications, security, and computational domains, including:

• Cryptographic key streams and one-time pad generation in symmetric encryption
• Spread-spectrum and CDMA channel access, where sequences define individual user codes
• Monte Carlo methods in scientific computing, finance, and probabilistic algorithm analysis
• Error-correcting code design, where pseudorandom interleaving improves burst-error performance
• Hardware testing and design verification using pseudorandom test pattern generation