Они ведут нас к загвоздке – чувствительности системы к исходному состоянию. Посчитаем итерации нашей функции, начиная с двух почти что равных величин: х = 0,1 и х = 0,10001. Интуитивно мы предполагаем, что скромная разница между исходными величинами не играет роли. Так ли это? Что произойдет?
Замечу, что первые десять итераций или около того не приводят к значительным отличиям. Но затем траектории начинают расходиться. Это можно проиллюстрировать на графиках эволюции той и другой системы. Сплошная линия соответствует итерированию системы с исходным значением 0,1. Пунктирная линия иллюстрирует итерирование системы с исходным значением 0,10001.
Каково значение f1000 (0,1)? К чему мы придем, если мы проделаем тысячу итераций функции f(x) = 3,9 x (1 – x)?
Разумеется, мы доверяем вычисления компьютеру, но получается какая-то чепуха. Проиллюстрируем этот факт, проделав вычисления трижды с разным уровнем точности (заданным количеством знаков после запятой). Мы получим следующие результаты:
Ни одна из этих величин не равна f1000 (0,1) в точности.
Мы будем биться до последней капли крови. Компьютер может работать с произвольной точностью. Он может не округлять полученное значение. К чему это приведет?
Точное значение f ⁶ (0,1) имеет длину 127 знаков после запятой, а точное значение f ⁷ (0,1) растягивается после запятой на 255 знаков. Количество знаков после запятой увеличится примерно вдвое на каждой итерации. Нет настолько мощного компьютера, чтобы вычислить точное значение f1000 (0,1).
К чему мы пришли? Несмотря на то что мы знаем исходное состояние системы и правило перехода от одного шага к другому, мы не в силах в точности предугадать ее состояние на 1000-м шаге.
Можно доказать, что точное значение f1000 (0,1) лежит между 0 и 1, и задаться вопросом: какова вероятность того, что f1000 (0,1), скажем, больше 0,5?
Ответ: либо 0, либо 1, потому что здесь нет ничего случайного. Либо f1000 (0,1) > 0,5, либо f1000 (0,1) ≤ 0,5, третьего не дано. Никаких «может быть», ничего случайного.
Даже настолько простая система способна оказаться хаотичной. Она абсолютно детерминирована и в то же время непредсказуема.
Огромное количество математических систем ведет себя хаотично, и многие из них позволяют строить модели явлений природы, например в метеорологии.
До сих пор мы говорили об итерациях логистических отображений. Мы закончили обсуждением разных типов функций и тернистой, неразрешимой проблемы их итерации.
Логистическое отображение – функция, заданная простой алгебраической формулой. Однако функции можно задавать иначе. Функция F, о которой сейчас пойдет речь, определена исключительно для положительных целых чисел и задана следующим образом:
Эта функция задается двумя простыми алгебраическими формулами, но мы выбираем формулу в зависимости от того, четное число x или нечетное.
Пример:
• F (9) = 28. Число 9 – нечетное, поэтому мы руководствуемся формулой 3х + 1 и получаем 3 × 9 + 1 = 28;
• F (10) = 5. Число 10 – четное, поэтому мы руководствуемся формулой x/2 и получаем 10/2 = 5.
Вне зависимости от того, четное число мы подставляем в функцию или нечетное, ее значение будет целым положительным числом.
Короче говоря, если x – целое положительное число, F (x) – тоже целое положительное число.
Мы можем итерировать нашу функцию, потому что выходное значение удовлетворяет условию, наложенному на входное значение. Что мы получим, итерируя функцию при начальном значении x = 12?
• F (12) = 6, потому что число 10 четное;
• F² (12) = F (6) = 3, потому что число 6 четное;
• F³ (12) = F (3) = 10, потому что число 3 нечетное;
• F⁴ (12) = F (10) = 5.
Вот удобный способ проиллюстрировать итерации. Мы записываем 12 → 6, подразумевая, что значение функции от 12 равно 6. Мы можем записать итерации F следующим образом:
Тройка 4 → 2 → 1 повторяется! А что дальше? Так как F(1) = 4, F(4) = 2, F(2) = 1, следующие три значения те же самые.
Другими словами, когда мы дошли до числа 1, тройка 4 → 2 → 1 будет повторяться до бесконечности.
Начнем с другой величины, скажем с 9. Вот что мы имеем: 9 → 28 → 14 → 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1.
Вот еще один впечатляющий ряд итераций:
27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1.
Мы снова дошли до 1, но после ста с лишним итераций.
Гипотеза Коллатца[213] заключалась в том, что вне зависимости от того, с какого целого положительного числа x мы начинаем, последовательность итераций рано или поздно достигает единицы и тройка 4 → 2 → 1 повторяется до бесконечности.
Проблема была решена самым умопомрачительным образом – штурм потребовал чудовищной дотошности математиков-профессионалов и математиков-любителей.
Глава 22Демократический выбор и теорема Эрроу
Демократия – процесс, основанный на предпочтениях членов общества. Людям дают возможность выразить свое мнение (путем голосования) и затем учитывают их голоса, когда принимают окончательное решение.
Знакомая всем демократическая процедура – выборы, на которых два кандидата претендуют на одну и ту же должность. Избиратели отдают голоса за первого или второго кандидата, и побеждает тот, кто наберет больше голосов.
Ключевая фраза: побеждает тот, кто наберет больше голосов – краеугольный камень демократического общества. Но насколько справедлив этот принцип?
Вообразим, что два кандидата, претендующих на одну и ту же должность, зовутся A и B. Избиратели отдают голос за того или другого[214]. Если отдано n голосов, данные голосования выглядят следующим образом[215]:
Как используется такой профиль предпочтений для принятия решения? Обычно просто подсчитывают, сколько голосов было отдано за каждого кандидата. Победителем оказывается тот, кто набрал больше голосов. Мы назовем такой подход правилом большинства – это метод демократических сообществ. Но это не единственный метод учета профиля предпочтений для принятия решения. Посмотрим на альтернативы.
Правило диктатора подразумевает, что решение принимается на основе голоса одного-единственного человека, скажем избирателя № 1. Если № 1 выбирает A, побеждает A; если № 1 выбирает B, побеждает B. Другие мнения не учитываются.
Мы будем называть правило большинства и правило диктатораметодами принятия решений. На входе – голоса избирателей, на выходе – решение о победе того или другого кандидата. В мире используют оба метода, но правило диктатора считается нечестным. Почему?
Для вящей справедливости метод принятия решения должен обладать определенными свойствами. Обидная особенность правила диктатора заключается в том, что голоса не учитываются равным образом. Более формально: справедливый метод принятия решения должен следовать нейтральности учета голосов[216] – не важно, кто голосует, важно, сколько голосов отдано за того или другого кандидата. Правило большинства отвечает требованию нейтральности учета голосов, а правило диктатора – нет.
Если мы руководствуется только теми методами, которые обладают свойством нейтральности учета голосов, мы просто суммируем голоса, отданные за того или другого кандидата. Итоговая статистика может выглядеть следующим образом:
Есть и другой метод. Назовем его правилом алфавита. Побеждает тот кандидат, чье имя идет первым по алфавиту. Тогда в любом случае побеждает кандидат A.
Очевидно, и этот метод несправедлив, но почему?
Он обладает свойством нейтральности учета голосов: все избиратели равны в том плане, что не учитывается ничье мнение! Проблема состоит в том, что кандидаты поставлены в неравное положение. Мы будем говорить, что метод обладает свойством нейтральности учета кандидатов[217], если к кандидатам относятся одинаково; если кандидат сменит имя, это не повлияет на итог выборов.
Чувство справедливости требует нейтральности учета голосов и нейтральности учета кандидатов. Достаточно ли этого?
Есть еще один метод, который мы будем называть правилом нечетности: победу одерживает тот кандидат, который набрал нечетное число голосов. Если A предпочли 20 избирателей, а B – 13 избирателей, побеждает B. Этот метод отвечает требованиям нейтральности учета голосов