20 июля 2019, суббота, 19:19
VK.comFacebookTwitterTelegramInstagramYouTubeЯндекс.Дзен

НОВОСТИ

СТАТЬИ

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
«Ангара» Африка Византия Вселенная Гренландия ДНК Иерусалим КГИ Луна МГУ Марс Металлургия Монголия НАСА РБК РВК РГГУ РадиоАстрон Роскосмос Роспатент Росприроднадзор Русал СМИ Сингапур Солнце Юпитер акустика антибиотики античность археология архитектура астероиды астрофизика бактерии бедность библиотеки биомедицина биомеханика бионика биоразнообразие биотехнологии блогосфера викинги вирусы воспитание вулканология гаджеты генетика география геология геофизика геохимия гравитация грибы дельфины демография демократия дети динозавры животные здоровье землетрясение змеи зоопарк зрение изобретения иммунология импорт инновации интернет инфекции ислам исламизм исследования история карикатура картография католицизм кельты кибернетика киты климатология комета кометы компаративистика космос культура лазер лексика лженаука лингвистика льготы мамонты математика материаловедение медицина метеориты микробиология микроорганизмы мифология млекопитающие мозг моллюски музеи насекомые наука нацпроекты неандертальцы нейробиология неолит обезьяны общество онкология открытия палеолит палеонтология память папирусы паразиты перевод питание планетология погода политика право приматы психиатрия психоанализ психология психофизиология птицы ракета растения религиоведение рептилии робототехника рыбы сердце смертность сон социология спутники старение старообрядцы стартапы статистика такси технологии тигры топливо торнадо транспорт ураган урбанистика фармакология физика физиология фольклор химия христианство школа экология эпидемии эпидемиология этология язык Александр Беглов Древний Египет Западная Африка Латинская Америка НПО «Энергомаш» Нобелевская премия РКК «Энергия» Российская империя Сергиев Посад альтернативная энергетика аутизм биология бозон Хиггса глобальное потепление грипп информационные технологии искусственный интеллект история искусства история цивилизаций исчезающие языки квантовая физика квантовые технологии компьютерная безопасность компьютерные технологии космический мусор криминалистика культурная антропология междисциплинарные исследования местное самоуправление мобильные приложения научный юмор облачные технологии обучение одаренные дети педагогика персональные данные подготовка космонавтов преподавание истории продолжительность жизни происхождение человека русский язык сланцевая революция финансовый рынок черные дыры эволюция эмбриональное развитие этнические конфликты ядерная физика Вольное историческое общество жизнь вне Земли естественные и точные науки НПО им.Лавочкина Центр им.Хруничева История человека. История институтов дело Baring Vostok Протон-М 3D Apple Big data Dragon Facebook Google GPS IBM MERS PRO SCIENCE видео ProScience Театр SpaceX Tesla Motors Wi-Fi

Редакция

Электронная почта: polit@polit.ru
Телефон: +7 929 588 33 89
Яндекс.Метрика
Свидетельство о регистрации средства массовой информации
Эл. № 77-8425 от 1 декабря 2003 года. Выдано министерством
Российской Федерации по делам печати, телерадиовещания и
средств массовой информации. Выходит с 21 февраля 1998 года.
При любом использовании материалов веб-сайта ссылка на Полит.ру обязательна.
При перепечатке в Интернете обязательна гиперссылка polit.ru.
Все права защищены и охраняются законом.
© Полит.ру, 1998–2019.