Секей Г. Парадоксы в теории вероятностей и математической статистике (1990) (1151962), страница 40
Текст из файла (страница 40)
В связи с псевдослучайными числами возникает следующий вопрос. В каком смысле их можно считать случайными, если они получены с помощью детерминированных (неслучайных) алгоритмов? После статьи фон Мизеса, вышедшей в 1919 г., некоторые выдающиеся математики исследовали эту проблему. (Философскими аспектами проблемы занимались П. Киршенманн, П. Макшейн и другие.) б) Парадокс В 1965 — 1966 гг. Колмогоров и Мартин-Леф представили понятие случайности в новом свете. Они определили, когда последовательность, состоящую из 0 и 1, можно считать случайной. Основная идея состоит в следующем. Чем сложнее описать последовательность (т. е. чем длиннее «самая короткая» программа, конструирующая эту последовательность), тем более случайной ее можно считать.
Длина «самой короткой» программы, естественно, различна для разных компьютеров. По этой причине выбирают стандартную машину, называемую машиной Тьюринга. Мерой сложности последовательности является длина наиболее короткой программы на машине Тьюринга, которая генерирует эту последовательность. Сложность — мера иррсгулярности. Последовательности, длина которых )Ч, называются случайными, если их сложность близка к максимальной. (Можно показать, что большинство последовательностей именно таковы.) МартинЛеф доказал, что эти последовательности можно считать с.чучайными, так как они удовлетворяют всем статистическим тс- стам на случайность. Таким образом, сложность и случайность тесно взаимосвязаны.
Если программист собирается получить «настоящие» случайные числа, то в силу результатов Колмогорова и Мартин-Лефа он может это сделать только с помощью достаточно длинной программы. В то же время на практике генераторы случайных чисел очень короткие. Как совместить эти два факта? в) Объяснение парадокса Последовательности, генерируемые короткими программамн и используемые в качестве случайных, в действительности удовлетворяют лишь некоторым, а не всем тестам на случайность. Однако в приложениях это почти не создает проблем. Например, для численного интегрирования достаточно иметь псевдослучайные числа, равномерно распределенные на некотором интервале.
Предположим, что надо проинтегрировать функцию ограниченной вариации на интервале (О, 1). Величина 1= ~ )(х)йх а приближается арифметическим средним г'н = — ~ ~) (х;) не только тогда, когда последовательность хь хь ..., хя случайна и равномерно распределена на интервале (О, 1). Достаточно потребовать равномерную распределенность этой последовательности. Это означает, что при )т' — оо Он = з и р 1 с (х, )т') — х (-ь О, О<я<~ где с(х, У) — отношение числа элементов последовательности хь хь, хя, принадлежащих (О, х), к У, т.
е. относительная частота. Можно показать, что где )г~ — постоянная, зависящая от функции 1 (полная вариация функции )). Отсюда следует, что приближение для! тем точнее, «ем меньше Оя. Однако значение Он минимально не тогда, ког- да берут случайную последовательность. Для случайной последовательности порядок приближения равен й1 †'ь, а для неслучайной последовательности можно получить точность порядка Лl — ! 10КМ. Часто вместо того, чтобы пытаться справиться с «неосязаемым понятием случайности», следует исйользовать детерминированные последовательности, которые лучше подходят для решения конкретной задачи. В этом суть квазиметода МонтеКарло.
г) Замечания (!) Взаимосвязь между случайностью и сложностью недавно привела к нескольким интересным открытиям. В течение долгого времени в математике существует общая практика обращения с очень сложными структурами как со случайными (например, поведение сложных последовательностей простых чисел часто описывается вероятностными законами). Идея о том, что случайность и сложность неразличимы, является настолько революционной, что она очень важна и с философской точки зрения. Используя эту идею, девиз Спинозы можно сформулировать следующим образом: люди предпочитают простые вещи сложным — это, безусловно, верно.
В то же время очевидно, что чем глубже мы пытаемся понять законы природы, тем яснее осознаем, что далеко не все они простые. (В) Последовательности случайных чисел применяются достаточно широко. Они нужны для численного интегрирования, для численного решения дифференциальных уравнений, для моделирования на ЭВМ физических, химических, биологических, технических и экономических задач и т. д. Они помогают при решении задач уличного движения, транспортных и других оптимизационных задач, а также при создании астрономических моделей.
С помощью случайных чисел можно проверять эффективность различных программ на ЭВМ. В заключение следует отметить совершенно иную область применения — компьютерное искусство, где последовательности случайных чисел предлагают миллионы вариаций (последовательности случайных чисел могут, очевидно, соответствовать последовательностям звуков, цветов, букв и т. д.), Из этих последовательностей компьютер оставляет только те, которые удовлетворяют установленным правилам.
Если компьютер работает с достаточно большим числом выборок, то художественное произведение будет очень хорошим. Например, греческий композитор Ксенакис использовал в своих работах звуки, полученные случайным образом с помощью ЭВМ. Уже проведено несколько выставок компьютерной графики. (Необходимо отме- тить, что не всякая компьютерная графика использует случайные последовательности.) В 1970 г.
образована международная организация компьютерных художников. д) Литература К|гьгьептапп Р. "Сопсер! о| гапбовпеьь", А Ра|1. Еоа!с, 1, 395 — 414, (|972). Кпий О. Е. Т|ге Аг1 о| Сотри1ег Ргоагавв)па, (СЬар1ег 3 — Напбот пивЬегь), Абб!ьоп-йгеь|еу, 1969. [Имеется перевод: Кнут Д. Искусство программирования для ЭВМ. Т.
1 (Гл, 3 — Случайные числа). — Ми Мир, 1976.) Магии-|.о1 Р. "ТЬе белл|!вп о| гапбот ьеяиепсеь", )гг)оггггаг!огг ала Сол. !го!, 9, 602 — 619, (1966). Мс5Ьапе Р. Ралаотлет, 5!а!!зг!сз алг1 Етегаелсе, ()п!ч, !чо!ге Вате, 1970. Ме1горо!|ь Ы., 11!ав 5, М. "ТЬе Моп1е Саг|о вейоб", А Атег.
5!а!!ь!. Аьзос., 44, 335 — 341, (1949). Мге) О. "Ап а)кот!!Ьв 1ог са|си|аноп о1 л", Тае Атепсал Май. Мол|Му, 86, 1979). !ебегге!!ег Н. "Яиаь|-Моп1е Саг|о ве!Ьобь апб рьеибогапбов пивЬегь". Ви!1. Атег. Май. 5ос., 84, 957 — 1041, (1978). 5свпогг С. Р, Хи)ос!наде!1 иЫ 2)авгьспегл!|свае!1, 1.ес!иге Мо!еь гп Май., 218, 5рппкег, Вег||п — Ыечг Уог!г, 1971. Соболь И. М. Метод Монте-Карло. — Мл Наука, 1978. 5ье!ге|у О. 3., Тиьпабу О. Уоп йе рЬ(!оьорыса! сопсер1 о1 гапбовпеьь |гав а гпайепгапса| ро|п! о1 ч!ечг" (иа венгерском языке), лрелринг. 4.
Парадокс неинтересных чисел; невычислимая вероятность а) История парадокса Мнение о том, является ли некоторое число интересным или неинтересным, полностью субъективно, но, опираясь на предыдущий парадокс, можно дать объективное определение интересного числа. Будем называть число интересным, если его сложность (которая определена в предыдущем разделе) мала. Таким образом, рациональные числа интересны, так как в их записи в десятичной системе знаки повторяются периодически. Среди иррациональных чисел числа и и е также интересны, поскольку цифры в их записи можно получить с помощью довольно простой программы на ЭВМ.
Однако существуют менее регулярные иррациональные числа. Например, нормальные числа обладают следующим свойством: в их записи в виде бесконечной десятичной дроби каждый знак (более того, любая группа цифр фиксированного размера) встречается с одной и той же вероятностью. Большинство иррациональных чисел нормальны, но трудно решить, является ли конкретное число нормальным или нет, Поэтому, например, неизвестно, нормально число и (первый миллион знаков которого опубликован в 1974 г.) или е или нет. В то же время существует очень простой (но искусственно построенный) пример нормального числа. В начале тридцатых годов Д. Шамперноун показал, что следующее число нормально: О.
123 456 789 101 112! 31 41 5 161 718 1% 021 222 324 252 6„. (десятичные знаки являются последовательными натуральными числами). Более ста лет назад похожая ситуация была в арифметике, когда в 1844 г. Лиувилль впервые построил трансцендентное число, т. е. число, не являющееся решением никакого алгебраического уравнения с целыми коэффициентами. Трансцендентность чисел и и е доказана позднее, соответственно в 1882 г. Ф. Линдеманом и в 1873 г.
Ш. Эрмигом. Изучение чисел в связи с их нормальностью началось лишь на рубеже веков, во многом благодаря исследованиям Э. Бореля. С этого времени, особенно после работ А. П. Колмогорова, П. Мартин-Лефа, Р, Соломонова и Г, Шайтана исследования по регулярности и иррегулярности последовательностей цифр развились в интересную теорию. Следующий парадокс — один из многих парадоксов в этой области. б) Парадокс У большинства чисел цифры следуют друг за другом случайно, т. е. большинство чисел неинтересны в следующем смысле: программы на ЭВМ, которые генерируют эти числа, ненамного короче самих чисел. Несмотря на обилие неинтересных чисел, для большинства из них нельзя доказать, что они неинтересны (в любой системе аксиом, лишенной противоречий).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
