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$.


1 Answer 1


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
    Commented Jun 15, 2016 at 9:14
  • $\begingroup$ I suggest checking textbooks on the area. $\endgroup$ Commented Jun 15, 2016 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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