2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Случайность по Колмогорову и Кнуту
Сообщение26.08.2016, 19:45 
Прошу прощения за дилетантский стиль, но надеюсь, вопрос получится осмысленным.

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

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

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

 
 
 
 Re: Случайность по Колмогорову и Кнуту
Сообщение26.08.2016, 20:27 
Аватара пользователя
Вы хотите брать бесконечные последовательности, и сравнивать "случайность по Кнуту" и случайность по Мартин-Лёфу относительно равномерной меры (которая эквивалентна тому, что априорная сложность префиксов отличается от их длин не больше чем на константу), правильно?

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

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

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group