Случайность по Колмогорову и Кнуту

[denny]

Прошу прощения за дилетантский стиль, но надеюсь, вопрос получится осмысленным.

Случайность по Колмогорову можно связать с длиной "воспроизводящей программы", или со степенью алгоритмической сжимаемости.

В любимой мной книге Кнута случайность определяется как (упрощенно) равнораспределенность всех возможных элементов, их пар, троек и т.д.
Т.е. в случайной двоичной последовательности $100011110...$ с равной вероятностью должны встречаться $0$ и $1$; $00$, $01$, $10$ и $11$ и т.д.

Есть ли связь (эквивалентность, поглощение) между этими определениями?

[mihaild]

Вы хотите брать бесконечные последовательности, и сравнивать "случайность по Кнуту" и случайность по Мартин-Лёфу относительно равномерной меры (которая эквивалентна тому, что априорная сложность префиксов отличается от их длин не больше чем на константу), правильно?

Пусть последовательность неслучайна по Кнуту. Для простоты - пусть доля единиц во всех ее префиксах длины больше $n$ не превосходит $0.49$. Какова обычная мера таких последовательностей? Если нулевая - можно ли такие последовательности покрыть множеством меры меньше $\varepsilon$ эффективно?

Можете ли вы сгенерировать последовательность, случайную по Кнуту? А по Мартин-Лёфу?