Abstract

Intuitively, it seems that S 1 is “more random” or “less regular” than S 2. In other words, it seems more plausible (in some sense) that S 1 (as opposed to S 2) was generated by a random process ( e.g. , by tossing a fair coin eight times, and recording an H for a heads outcome and a T for a tails outcome). We will use the notation x σ 1 ą σ 2y to express the claim that xstring σ 1 is more random than string σ 2y. And, we take it to be intuitively clear that — on any plausible definition of such a relation — we should have S 1 ą S 2