3
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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, 2016 at 9:14
  • $\begingroup$ I suggest checking textbooks on the area. $\endgroup$
    – Yuval Filmus
    Jun 15, 2016 at 9:16

Your Answer

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

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