Random sequence

From Wikipedia, the free encyclopedia

This article or section is in need of attention from an expert on the subject.
Please help recruit one, or improve this page yourself if you can. See discussion page for details.

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.

1 Usage of the Term in Algorithmic Information Theory
2 References
- 2.1 See also
- 2.2 External link

[edit] Usage 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).