Полiт.ua Государственная сеть Государственные люди Войти
6 декабря 2016, вторник, 08:52
Facebook Twitter LiveJournal VK.com RSS

НОВОСТИ

СТАТЬИ

АВТОРЫ

ЛЕКЦИИ

PRO SCIENCE

ТЕАТР

РЕГИОНЫ

Розенкранц, Гильденстерн и случайные последовательности

 
 

6 марта в рамках проекта «Публичные лекции "Полит.ру"» выступил Александр Ханиевич Шень – кандидат физико-математических наук, старший научный сотрудник Лаборатории теории передачи информации и управления ИППИ РАН, научный сотрудник LIRMM CNRS (Франция, Монпелье). Тема его лекции «Основания теории вероятностей и колмогоровская сложность». 

В «Демографическом энциклопедическом словаре» 1985 года издания в качестве примера возрастно-половой пирамиды приводится пирамида населения Мексики на январь 1970 года. На первый взгляд в ней не было ничего необычного. По вертикальной оси отмечается возраст, по горизонтальной – количество людей, слева – мужчины, справа – женщины. Длина полосок соответствует числу лиц этого возраста.

Но, присмотревшись, можно заметить странное явление. Начиная с возраста 30 лет и далее для возрастов 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85 лет мы видим, что количество людей значительно превышает число тех, чей возраст не кратен пяти. Что это? В Мексике раз в пять лет старались больше рожать? Или люди, рожденные в эти годы, обладают повышенной выживаемостью? Специалистам по демографии ответ на этот вопрос известен. Просто люди, многие из которых не были очень грамотны, на вопрос переписчика о возрасте называли округленное число. Поскольку перепись населения регистрирует все данные не по документам, а со слов опрашиваемых, итоговые данные приняли такой вид.

Здесь неожиданно обнаруженная закономерность заставила нас усомниться в верности исходных данных. А что бывает, когда мы смотрим на последовательности, полученные в результате случайных процессов? Мы бросаем монету и получаем такую последовательность (0 – орел, 1 – решка):

11011100111011111010011001101011100000111101.

Или мы бросаем шестигранную кость и получаем последовательность, например, такую:

44215665323414612456423363165524112145645692.

Вроде, ничего подозрений не вызывает. А теперь представим, что результаты бросания монеты или кости оказались иными и последовательности выглядят так:

11111111111111111111111111111111111111111111.

Или так:

100100100100100100100100100100100100100100100.

Или так:

123456123456123456123456123456123456123456123456.

Мы сразу начинаем подозревать, здесь что-то неладное. Мы удивлены, также, как удивлены были главные герои пьесы Стоппарда «Розенкранц и Гильденстерн мертвы», когда монета более восьмидесяти раз упала орлом вверх. Мы предполагаем обман, неправильную монету или какое-то еще вмешательство. Полученные результаты кажутся нам маловероятными.

Между тем, они ничуть не менее вероятны, чем любые другие. Последовательное выпадение одних орлов имеет такую же вероятность, как и любой другой набор орлов и решек. Ведь итог каждого испытания не зависит от итогов предыдущих. И выпадение пяти решек подряд ничуть не увеличивает вероятность выпадения орла в шестой попытке.

Кстати, этот принцип независимости результата от предыдущих испытаний часто противоречит интуиции человека, а порой с гневом им отвергается. Александр Шень привел цитату из рассказа Эдгара Аллана По «Тайна Мари Роже», в котором автор с видом знатока теории вероятностей утверждает прямо противоположное:

«Это одна из тех аномалий, которые, хотя и чаруют умы, далекие от математики, тем не менее полностью постижимы только для математиков. Например, обычного читателя почти невозможно убедить, что при игре в кости двукратное выпадение шестерки делает почти невероятным выпадение ее в третий раз и дает все основания поставить против этого любую сумму. Заурядный интеллект не может этого воспринять, он не может усмотреть, каким образом два броска, принадлежащие уже прошлому, могут повлиять на бросок, существующий еще пока только в будущем. Возможность выпадения шестерки кажется точно такой же, как и в любом случае – то есть зависящей только от того, как именно будет брошена кость. И это представляется настолько очевидным, что всякое возражение обычно встречается насмешливой улыбкой, а отнюдь не выслушивается с почтительным вниманием. Суть скрытой тут ошибки – грубейшей ошибки – я не могу объяснить в пределах места, предоставленного мне здесь, а людям, искушенным в философии, никакого объяснения и не потребуется. Тут достаточно будет сказать, что она принадлежит к бесконечному ряду ошибок, которые возникают на пути Разума из-за его склонности искать истины в частностях».

И все же, чем отличаются последовательности, вызвавшие у нас сомнение, от других? В этих последовательностях распределение результатов подчиняется некоторой закономерности, которая позволяет описать эту последовательность, причем описание будет короче самой последовательности.

Последовательность:

11111111111111111111111111111111111111111111.

Описание:

44 единицы

Последовательность:

100100100100100100100100100100100100100100100.

Описание:

100, повторить 15 раз

Последовательность:

123456123456123456123456123456123456123456123456.

Описание:

Натуральные числа от 1 до 6, повторить 8 раз.

Анализируя подобные последовательности, известный математик Андрей Николаевич Колмогоров сформулировал понятие, которое впоследствии получило название колмогоровская сложность. Сложность последовательности – это минимальная длина программы, которая порождает данную последовательность. У последовательности из 44 единиц подряд колмогоровская сложность невелика, а вот у самой первой из приведенных нами последовательностей – напротив, сложность большая. Гораздо меньше места займет запись последовательности, чем описание алгоритма ее порождения.

В лекции Александр Шень сообщил малоизвестные подробности из истории понятия сложности. Независимо от Колмогорова примерно в то же время к формулировке такого понятия пришли еще два математика. Это Грегори Чайтин (Gregory Chaitin), который написал свою первую статью на эту тему, еще будучи школьником. И еще один американский математик Рэй Соломонофф (Ray Solomonoff).

Где понятие сложности может встретиться в жизни простого человека? При работе компьютера порой используют программы-архиваторы, которые сжимают размер файла, чтобы тот занимал меньше места на диске. Сжатие файлов основано, грубо говоря, на том, что программа находит закономерности в размещении кулей и единиц в его двоичной записи. Файл, колмогоровская сложность которого мала, сжимается хорошо, в несколько раз. Размер файла, колмогоровская сложность которого велика, при архивировании сильно не уменьшится. Фактически размер сжатого файла – это верхняя оценка его колмогоровской сложности (остается некоторый шанс, что закономерность есть, но программа-архиватор ее не нашла).

Приложениями колмогоровской сложности для классификаций занимается современный нидерландский математик Пол Витаньи (Paul Vitanyi). В одной из работ он сделал попытку построение классификации некоторого набора музыкальных произведений на основе сжатия midi-файлов с ними. При этом файлы х и у считались близкими, если сложность файла ху была меньше суммы сложностей  файлов х и у. В результате, как оказалось, близкими по этой классификации оказались музыкальные произведения, действительно принадлежащие одному автору.

Также Полу Витаньи принадлежать попытки классификаций по сжатию текстов произведений русской литературы классиков и их переводов.

В других случаях им и его соавторами этот метод использовался для определения места вируса тяжелого острого респираторного синдрома (SARS) среди других вирусов по последовательности нуклеотидов в его РНК, классификации видов млекопитающих по ДНК, грибов по митохондриальным ДНК и даже построения классификации языков по текстам декларации прав человека, переведенным на эти языки. Подробнее об этом можно прочитать в работах The similarity metric (pdf) и Clustering by compression (pdf).

Обсудите в соцсетях

Система Orphus
Подпишитесь
чтобы вовремя узнавать о новых спектаклях и других мероприятиях ProScience театра!
3D Apple Facebook Google GPS IBM iPhone PRO SCIENCE видео ProScience Театр Wi-Fi альтернативная энергетика «Ангара» античность археология архитектура астероиды астрофизика Байконур бактерии библиотека онлайн библиотеки биология биомедицина биомеханика бионика биоразнообразие биотехнологии блогосфера бозон Хиггса визуальная антропология вирусы Вольное историческое общество Вселенная вулканология Выбор редакции гаджеты генетика география геология глобальное потепление грибы грипп демография дети динозавры ДНК Древний Египет естественные и точные науки животные жизнь вне Земли Западная Африка защита диссертаций землетрясение зоопарк Иерусалим изобретения иммунология инновации интернет инфекции информационные технологии искусственный интеллект ислам историческая политика история история искусства история России история цивилизаций История человека. История институтов исчезающие языки карикатура католицизм квантовая физика квантовые технологии КГИ киты климатология комета кометы компаративистика компьютерная безопасность компьютерные технологии коронавирус космос криминалистика культура культурная антропология лазер Латинская Америка лженаука лингвистика Луна мамонты Марс математика материаловедение МГУ медицина междисциплинарные исследования местное самоуправление метеориты микробиология Минобрнауки мифология млекопитающие мобильные приложения мозг Монголия музеи НАСА насекомые неандертальцы нейробиология неолит Нобелевская премия НПО им.Лавочкина обезьяны обучение общество О.Г.И. открытия палеолит палеонтология память педагогика планетология погода подготовка космонавтов популяризация науки право преподавание истории происхождение человека Протон-М психология психофизиология птицы ракета растения РБК РВК регионоведение религиоведение рептилии РКК «Энергия» робототехника Роскосмос Роспатент русский язык рыбы Сингапур смертность Солнце сон социология спутники старообрядцы стартапы статистика технологии тигры торнадо транспорт ураган урбанистика фармакология Фестиваль публичных лекций физика физиология физическая антропология фольклор химия христианство Центр им.Хруничева школа эволюция эволюция человека экология эпидемии этнические конфликты этология ядерная физика язык

Редакция

Электронная почта: politru.edit1@gmail.com
Адрес: 129343, Москва, проезд Серебрякова, д.2, корп.1, 9 этаж.
Телефоны: +7 495 980 1893, +7 495 980 1894.
Стоимость услуг Полит.ру
Свидетельство о регистрации средства массовой информации
Эл. № 77-8425 от 1 декабря 2003г. Выдано министерством
Российской Федерации по делам печати, телерадиовещания и
средств массовой информации. Выходит с 21 февраля 1998 года.
При любом использовании материалов веб-сайта ссылка на Полит.ру обязательна.
При перепечатке в Интернете обязательна гиперссылка polit.ru.
Все права защищены и охраняются законом.
© Полит.ру, 1998–2014.