Random sequences are essential in statistics. The statistical analysis of any experiment usually begins with the words "let X1,...,Xn 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 {Xi} 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.
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.
Encyclopedia
top
