In his 1973 paper On the notion of a random sequence, Levin states (without proving) a characterization of Martin-Löf randomness by writing

Theorem 3. A sequence $\alpha$ is random w.r.t. the distribution $P$ in the Martin-Löf sense if and only if the probability ratio $P(\alpha_n)/ R(\alpha_n)$ is bounded below

where $R$ is the universal semicomputable (semi)measure.

I feel a bit confused how this ratio could not be bounded below, being the ratio of two positive quantities it should always be bounded below by $0$.


The ratio should be bounded below by a positive constant. Equivalently, its infimum should be positive.

  • $\begingroup$ I wonder whether I should have been able to understand this by reading the text...can you point me to some proof of this statement? $\endgroup$ – Manlio Jun 15 '16 at 9:14
  • $\begingroup$ I suggest checking textbooks on the area. $\endgroup$ – Yuval Filmus Jun 15 '16 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.