Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 80
Текст из файла (страница 80)
п.) из какого-либо справочника. Заглянув, например, в Нкпс)Ьоо)г о1МагЬ- ешабса! Рилсгюпэ (В. 8. Оерг оЕ Сошшегсе, 1964), можно обнаружить, что у 8 из 28 различных физических постоянных, приведенных в табл. 2.3, а это примерно 29% случаев, ведущий разряд равен 1.
Значения н! в десятичной системе при 1 < и < 100 включают ровно 30 элементов, начинающихся с 1; то же самое относится к десятичным значениям 2" н Г„при 1 < п < 100. Можно было бы заглянуть также в отчеты о переписи населения или в 'Календарь фермера" (но не в телефонный справочник). В те не такие уж далекие времена, когда не было карманных калькуляторов, в таблицах логарифмов, которые часто использовались, как правило, первые страницы были довольно грязными, потрепанными, а последние оставались сравнительно чистыми и, на первый взгляд, нетронутыми. По-видимому, впервые это явление было отмечено в печати американским астрономом Саймоном Ньюкомбом !8!шоп ХеасошЬ, Ашег. Х Ммй, 4 (1881), 39-40), который привел разумные доводы в пользу того, что цифра И встречается в качестве ведущей с вероятностью !ойщ(1+1/с().
Тот же закон распределения много лет спустя был эмпирически открыт Ф. Бенфордом (г. Веп(огд, Ргос. Ашег, РЬ!!оэор!йса! Бос. 78 (1938), 551-572) который сообщил о результатах 20 229 наблюдений, взятых из других источников. Для того чтобы "прочувствовать" этот закон ведущего разряда, давайте внимательно посмотрим, как записываются числя в формате с плавающей точкой. Если взять произвольное положительное число и, то его дробная часть будет определяться по формуле 107'„= 100оам Ы "'~" ' Следовательно, ведущий разряд в ней будет меньше, чем И, тогда и только тогда, когда (!о%он) шо61 < 1ой~ог!. Далее, если имеется какое-либо "случайное" положительное число !7, выбранное иэ совокупности, которая существует в природе, то можно ожидать, что числа (!ойш !7) спой 1 будут равномерно распределены между нулем н единицей или по крайней мере их распределение будет достаточно близко к равномерному.
(Аналогично мы ожидаем, что так же равномерно распределены величины !7шо61, Уз пик1 1, зФ'+ я пкк1 1 и т. д. Мы уверены, что колесо рулетки беспристрастно, в основном, по этой же причине.) Значит, из неравенства (1) следует, что единица будет ведущей цифрой с вероятностью 1ойю 2 ж 30.103%, двойка — с вероятностью !ойш 3 — 1ой,е 2 ж 17.609%, н вообще, если г — произвольное вещественное число, заключенное между 1 и 10, приблизительно в 1ойго г всех случаев должно выполняться неравенство 10~о < т. Поскольку ведущие цифры, в основном, небольшие, наиболее распространенная методика оценки "средней ошибки" при вычислениях в формате с плавающей точкой становится неверной.
Относительная ошибка вследствие округления обычно оказывается несколько большей, чем ожидается. Рг((!ой,е (/ шоб 1) < !ойш г — !ойш с или ()ой,е(/шоб1) > 1- !ойьэс), Рг((!ой~о(/шоб1) < !ой~ос+1 — !ой~ос и (!ойш (/ шог! 1) > 1 — (ойш с ), если с < г; если с > г; р(т/с) + 1 — р(10/с), если с < г; ж р(10г/с) — р(10/с), если с > г. Продолжим теперь функцию р(г) вне интервала 1 < г < 10, положив р(10"г) = р(г) + и.
Тогда, заменив 10/с нв И, можно записать последнее соотношение в (2) в виде р(М) = р(г) +р(д). (3) Еслп верно предположение об инвариантности распределения относительно умножения на произвольный постоянный множитель, то соотношение (3) должно выполняться для всех г > О и 1 <И < 10. Из того факта, что р(Ц = О и р(10) = 1, теперь следует: 1 = р(10) = р((ЯО)") = р(ъИ) + р((ЯО)" ') = " = пр(ЯО) отсюда приходим к заключению, что для всех положительных целых пэ и и справедливо равенство р(10 У") = гп/и. Если дополнительно потребовать, чтобы распределение р было непрерывным, то можно прийти к заключению, что р(г) = !ой,е г, а это и есть искомый закон. Хотя данный аргумент, возможно, и убедительнее предыдущих, он тоже в действительности не выдерживает придирчивой проверки, если строго придерживаться Разумеется, можно справедливо утверждать, что приведенные выше эвристические доводы не доказывают сформулированного закона, Они только указывают правдоподобные причины того, что поведение ведущих цифр именно таково, каково оно есть на самом деле.
Интересный подход к анализу значений ведущих разрядов был предложен Р. Хэммингом (К. Напипшк). Пусть р(г) — вероятность того, что 1О/и < г, гдв 1 < г < 10 и /и — нормализованная дробная часть случайным образом выбранного нормализованного числа Г Если говорить о случайных величинах в реальном мире, то можно заметить, что онн измеряются в произвольных единицах, и если изменить, скажем, опредвненне метра илн грамма, то многие из фундаментальных физических постоянных будут иметь другое значение. Предположим поэтому, что все числа во Вселенной внезапно оказались умноженными на некоторый постоянный множитель с; наша "Вселенная" случайных величин с плавающей точкой должна после этого преобразования остаться, по существу, неизменной, так что вероятности р(г) не должны измениться.
Умножение всех чисел на с имеет тот эффект, что (1ойю П) шоб 1 превращается в (!ойю 1/+!ойю с) пюб 1. Выведем формулы, описывающие искомое распределение. Можно считать, что 1 < с < 10. По определению р(г) = Рг((!ой~э 1/) шоб 1 < !ой~с г) ° Согласно Сляпанному ранее предположению имеем также р(г) =Рг((1ой, 1~+!ой, с)шоб1<!ой, г) общепринятого определения вероятности. Традиционный способ точной формулировки подобных аргументов подразумевает, что существует некое лежащее в основе рассматриваемого явления распределение чисел К(и), такое, что вероятность того, что данное произвольное число У не превосходит и, равна Г(н); тогда интересующая нас вероятность равна р(г) = ~~' (Г(10 г) — л(10 )), (4) где суммирование проводится по всем значениям -со < т < оо. Наше предположение об инварнантности по отношению к масштабированию и о непрерывности приводит к заключению, что р(г) = 1ой~ог Используя те же доводы, можно "доказать", что (Г(Ь~г) — г (Ь )) 108 при 1 < г < Ь для любого целого числа Ь > 2.
Но не с1пкесшвйеш функции распределения Е. которая удовлетворяла бы этому равенству для всех таких Ь и г (см. упр. 7). Один из способов выхода из этой затруднительной ситуации состоит в рассмотРенин логаРиФмического закона Р(г) = 1ойгег лишь как очень хоРошего пРиближенел к истинному распределению. Возможно, истинное распределение изменяется при расширении Вселенной, делая с течением времени наше приближение все лучшим и лучшим; и, если заменить основание 10 произвольным основанием Ь, наше приближение будет тем менее точным (в любой данный момент времени), чем больше Ь. Другой довольно привлекательный способ решения дилеммы, связанный с отказом от традиционного понятия функции распределения, предложен Р. А, Рэйми [К.
А. Кайп1, АММ Тб (1969), 342-348). Витиеватые рассуждения последнего абзаца, по-видимому, ни в коей мере нельзя признать удовлетворительным объяснением, так что следует весьма ноложительно отнестись к проводимым ниже вычислениям (где мы придерживаемся строгого математического канона и избегаем любых интуитивно понятных (и вдобавок к тому еще и парадоксалыгых) понятий теории вероятностей). Рассмотрим вместо распределения некоего воображаемого множества вещественных чисел распределение значений ведущих (старших значащих) разрядов положительимя целых чисел.
Исследование этого вопроса чрезвычайно интересно, и не только потому, что оно проливает некоторый свет на распределения вероятностей для данных, представленных в формате с плавающей точкой, но и потому, что оно служит весьма поучительным примером сочетания методов дискретной математики с методами исчисления бесконечно малых. Во всех последующих рассуждениях г будет обозначать фиксированное вещественное число, 1 < г < 10; мы попытаемся дать разумков определение р(г) как "вероятности" того, что представление 10'" .
~м "случайного" положительного целого числа Ж удовлетворяет неравенству 10Ул < г в предположении о бесконечной точности представления. Для начала попытаемся найти эту вероятность, используя методику предельного перехода, аналогично тому, как мы определяли "Рг" в разделе 3.5. Вот удобный способ перефразирования этого определения: Ро(п) = !и = 10' У, где 107" <т) = [(!о61еп)шо61 < !о61ет~. (6) Итак, последовательность Ре(1), Ре(2), ... есть бесконечная последовательность нулей и единиц, причем единицы соответствуют случаям, вносящим вклад в значение вероятности, которую мы ищем.
Можно попытаться "усреднить" эту последовательность, положив Р,(п) = - ~ ' Ре(й). 1 (7) з=1 Таким образом, если сформировать случайное целое число в интервале между 1 и и, используя методику главы 3, и преобразовать его в десятичный формат с плавающей точкой (е, г), то вероятность того, что 107 < т, н будет е точности равна Р,(и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
