"Хеломскiя Вѣдомости"'s Journal

Всё сложно

Одни орлы собрались

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

a_shen и

ver1958, разбирающихся в этих вопросах гораздо лучше меня.

1. Начнём с первого пункта, про теорию вероятностей. По самой своей природе, эта теория не способна дать детерминистский (не-вероятностый) ответ ни на один бинарный (да/нет) или любой другой вопрос. Какова вероятность, что мы выбросим миллион орлов? спросите

varanaу, она помнит ответ из учебника. Какова вероятность, что монетка, выпавшая миллион раз орлом, фальшивая? спросите у статистика. Какова вероятность, что вы долетите своим рейсом до цели? спросите страхового агента. Некоторые вас ещё переспросят, что вы априорно думали про монетку или авиакомпанию, но никто из них не скажет вам ответ наверняка. Это всегда ваше личное дело - думать, десять в минус пятой, - это много или мало. Если это шанс получить "паровоз" на мизере, - смело берите прикуп, а если это шанс, что ваш самолёт потерпит аварию - примерно половина пассижиров (как показывают эксперименты на людях) сдаст билет. Интересно, как американская юриспруденция определяет понятие beyond the reasonable degree of doubt. Наверное, именно для этого там используются ~~лабораторные мыши~~ присяжные.

2. Человеку непривычно иметь дело с бесконечностью, поэтому мы говорим про миллион орлов, имея в виду "миллион - это бесконечно много". Но математикам проще встречать врага с открытым забралом и иметь дело сразу с бесконечными последовательностями. Там этих ваших экивоков нет и утверждение предельно просто: вероятность любой конкретной бесконечной последовательности, хоть из одних нулей, хоть самой расслучайной на вид, одна и та же - ноль. Только надо иметь в виду, что "вероятность равна нулю" и "событие невозможно" - совершенно разные высказывания. Вероятность случайным образом выбрать рациональное число - нулевая, однако ж это отнюдь не значит, что рациональных чисел нет (это я возвернулся к п. 1). Для зануд, - я смешал в одну кучу меру Лебега на числовой прямой и равномерное распределение на отрезке [0,1]. Да простят меня ЖЖ-духи.

3. На этом можно было бы попросить Теорию Вероятностей покинуть сцену, чтоб не смущать своим присутствием почтеннейшую публику. Но пусть пока посидит в сторонке. Мы тем временем займёмся другим вопросом: чем (бесконечная) последовательность из одних нулей отличается от последовательности, которую (как мы верим, честно) получили бросанием монетки или наблюдая за распадом радиоактивных атомов (вроде бы наилучший сегодня "природный" источник случайных чисел).

Ответов будет бесконечно много. "Случайная" последовательность из нулей и единиц "с вероятностью единица" удовлетворяет миллиону теорем про случайные последовательности: тут тебе и среднее значение 1/2, и корреляции между вероятностью совпадениия/различных блоков на определённом расстоянии друг от друга, и вероятности "больших уклонений" (появления длинных кусков единиц или нулей), - короче, покажите вашу бесконечную последовательность специалисту по теории вероятности, и он очень быстро скажет вам, что с вероятностью 0 ваша последовательность случайная или, наоборот, она случайна с вероятностью единица. (Замечательное простое рассуждение, называемое ~~леммой Бореля-Кантелли~~ "законом 0 или 1 Колмогорова", состоит в том, что воображаемый эксперт никогда не даст вам ответа в виде "вероятность того, что бесконечная последовательность случайная, равна 1/2". Либо ноль, либо единица, промежуточных значений не может быть).

Тут бы и в бубен бить, однако ж см. п.1 и 2. Нулевая вероятность не значит невозможность, и ничего порочащего про последовательность из одних орлов сказать нельзя (подозревать можно сколько угодно).

4. Так если вероятнось оказалась бессильной, что же, никак не поймать за руку шулера? Проблему решил Колмогоров (? я не назову навскидку предшественников), открыв понятие "сложности".

Наивным образом понимаемая, сложность бесконечной последовательности есть длина предложения, её описывающего. "Одни нули" - 8 букв русского языка. "Одни единицы" - немного сложнее, но явно не по математическим соображениям, а по филологическим. Инструкция "кусок 01001101 пишется на n-м месте, если n - простое число, а если n - составное, то пишется кусок 100110011111011" - тоже недлинная, хотя угадать её, гляда на предъявленную вам бесконечную последовательность будет довольно трудно.

Чтобы избежать филологических проблем, зафиксируем язык программирования (ФОРТРАН, а эстеты могут думать о машине Тьюринга) и определим "сложность" бесконечной последовательности, как наименьшую длину программы, которая эту последовательность напечатает. Тут, конечно, надо заплатить небольшую цену за наше желание работать именно с бесконечными последовательностями: таких программ может не быть вовсе, ну, или по крайней мере, мы их можем не знать. Если же мы будем сурово рассматривать только конечные последовательности, то хотя бы одна такая программа тривиально есть, - PRINT "010111000100....101", где в кавычках наша последовательность выписана явно. В учебниках сложность определяется лишь для конечных строк, а для бесконечных можно смотреть на рост сложности с длиной, - остаётся ли она ограниченной или растёт неограниченно. Несложные (конечные) числа - это числа, которые могут быть напечатаны программой, значительно короче, чем их собственная длина (к чёрту детали). Наоборот, сложные числа - всё то, что не может быть объяснено, стоя на одной ноге.

Очевидно, что мера (=вероятность) всех бесконечных последовательностей, имеющих конечную "сложность" (определённую как выше), равна нулю. Дело в том, что все последовательности, которые могут быть напечатаны конечными программами, образуют счётное множество, а такие множества имеют нулевую вероятность (меру Лебега). Это объясняет наше желание признать последовательность из одних орлов "совершенно невероятной": она и все ей подобные ВСЕ ВМЕСТЕ образуют множество нулевой меры/вероятности.

5. Естественный вопрос, - а почему ФОРТРАН а не Python? Ответ (теорема универсальности) сложность описания на любом приличном языке одна и та же с точностью до константы. Доказательство: любая программа на ФОРТРАНЕ превращается в программу на Python'e и обратно, если в начало программы добавить компилятор с одного языка на другой.

Тем не менее вычислить сложность нельзя: не такая это простая штука, как кажется.

6. Комментарии по поводу толиной заметки. Тот факт, что мы работаем с единицами и нулями, и важен, и не важен по-своему. У нас могут быть в самом деле любые пары (чулки-носки, инь-янь, север-юг, ...), которыми мы можем по нашему произволу перекодировать нули и единицы. Например, можно превратить череду из одних орлов в нечто несусветное и никакому видимому закону не подчиняющееся.

Однако ж колмогоровскую сложность так не объехать. Если мы заменили алфавит (0,1) на алфавит из произвольных 2n символов и напишем для себя правила перекодировки, то мы, может, и обманем наивного наблюдателя, но не определение сложности. Потому что эту (конечную) перекодировочную таблицу мы добавим к печатающей программе - et voila. А вот если новый алфавит бесконечен, то всё меняется неконтролируемым образом, и связь исходной и перекодированной задач теряется.

7. Комментарий для зануд: идеологически сложность конечных последовательностей и "сложность" бесконечных последовательностей связаны друг с другом примерно как бесконечные последовательности и их пределы. Разговор о пределах - проще лингвистически, но таит в себе подводные камни. Разговор о конечном числе членов - проще технически (результаты всех конечных вычислений конечны и определены), но на них надо навешивать надлежащие кванторы в немалых количествах. Профессионалы к ним привыкли и проглатывают, а дилетантам трудно освоить, в каком порядке эти кванторы следуют друг за другом. Хотите пример? Попробуйте аккуратно написать определение того, что последовательность положительных чисел растёт субэкспоненциально.

♣ Когда вы не сможете прочесть эту надпись здесь, вы сможете всегда её прочесть тут. Комментируйте где хотите, на Дриме уже таких осторожных комментаторов набралось.

А Оккам... да хрен с ним, с Оккамом!