# Random sequence

A **random sequence** is a kind of stochastic process. In short, a random sequence is a sequence of random variables.

Random sequences are essential in statistics. The statistical analysis of any experiment usually begins with the words "let *X*_{1},...,*X _{n}* be independent random variables...". The easiest way to talk about a situation when you can choose to make new measurements is to assume that an infinite sequence {

*X*} is given, and that successive stages of the experiment you look at the first

_{i}*N*terms of the sequence. Also, the statement of the law of large numbers (essentially that the average of a number of observations converges to the mean value) involves an infinite sequence of independent identically-distributed random variables.

## Use of the term in algorithmic information theory

The term "random sequence" can also describe a finite sequence, or string, of random characters. (Though not universal, computer scientists generally refer to an infinite sequence of characters or digits as a *sequence*, and a finite sequence of characters or digits as a *string*.) Algorithmic information theory defines a random string as one that cannot be produced from any computer program that is shorter than the string (Chaitin-Kolmogorov randomness); i.e. a string whose Kolmogorov complexity is at least the length of the string. This is a different meaning from the usage of the term in statistics. Whereas statistical randomness refers to the *process* that produces the string (e.g. flipping a coin to produce each bit will randomly produce a string), algorithmic randomness refers to the *string itself*. Algorithmic information theory separates random from nonrandom strings in a way that is relatively invariant to the model of computation being used.

An algorithmically random sequence is an *infinite* sequence of characters, all of whose prefixes (except possibly a finite number of exceptions) are strings that are "close to" algorithmically random (their length is within a constant of their Kolmogorov complexity).

# References

- Per Martin-Löf. The Definition of Random Sequences. Information and Control, 9(6): 602-619, 1966.

## See also

- Halton sequence
- Randomness
- Random number generator
- Statistical randomness
- Algorithmically random sequence
- Kolmogorov complexity