This article or section is in need of attention from an expert on the subject. WikiProject Mathematics may be able to help recruit one. If a more appropriate WikiProject or portal exists, please adjust this template accordingly.

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₁,...,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_i} is given, and that successive stages of the experiment you look at the first 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

External links

• Randomness tests by Terry Ritter

Donate to Wikimedia