AOP_Tom2 (1021737), страница 189
Текст из файла (страница 189)
При 6 = 2 мы предсказываем значение, приблизительно равное 45%, в то время как таблица даст 44%, Эти расхождения, конечна, лежат в допускаемых пределах, если учтена ошибка эксперимента. 15. Если Й = О, то старшая цифра равна 1 тогда и только тогда, когда возникает перенос. (Возможно, что при 6 ) 4 в результате переполнения дробной части и последующего округления! появится ведущий разряд, равный 2, но в этом упражнении округление игнорируется.) Как показано в предыдущем упражнении, вероятность переполнения дробной части равна приблизительно .272, а .272 < !ой~о 2.
Если Й ) О, то ведущий разряд равен 1 с вероятностью )(/ гг/ ) ( )(/ гг/ — )-»~ 2 16. Для доказательства положения, сформулированного в указании (его авторство принадлежит Ландау (Ьапдав, Ргасе Магещагусгпо-Р!гусгле 21 (1910), 103-113)), сначала предположим, что!плевра» ж Л > О. Пусть е = Л/(Л+ 4М), и выберем М так, что (а~ + + а„) < —,' <Ли для всех и > Х, Пусть и > 57/(1 — г), и ) 5/г будет таким, что а» ) гЛ. 1огда по индукции а -ь ) а» ЙМ/(и ги) ) гЛ для 0 < Й < еи и г „,„<ь<„аь ) 1Л(<и — 1) > -'Лги. Но Предполагая, что Р ч~(и) -+ Л при и -э оо, положим аь = Р (й) — Л.
Если гп > О, то аь удовлетворяют гипотезе, сформулированной в указании, поскольку 0 < Рм(й) < 1 (см. 4.2.2 — (15) ); отсюда Р (и) -+ Л. 17. См. Х Маей. Зос.,7арэп 4 (1952), 313-322. (Тот факт, что гармоническая вероятность расширяет понятие обычной вероятности, следует из теоремы Чезаро (Севйго, АЬН с(е11а Кеа)е Ассадет1а с)е( й/псе!, НепаЗсопН (4) 4 (1888), 452-457). Перси Дьяконис (Регв! П!асов!э, РЛ. П.
!Леэ!э, Нагчагд Нппегжсу, 1974) среди прочего показал, что определение вероятности через повторяющееся усреднение является более слабым, чем определение гармонической вероятности, в смысле следующей строгой формулировки. Если !!т„, !пиш1,««Р (и) = !пп „1ппэпр« „Р (и) = Л, то гармоническая вероятность «2 ь« равна Л. С другой стороны, утверждение «10" < и < 10" +" для целых чисел й > 0" имеет гармоническую вероятность -', в то время как повторяющееся усреднение никогда не присвоит этому утверждению некоторой конкретной вероятности.) 18.
Пусть р(а) = Р(Л,) и р(а,Ь) = ч,<ь< р(й) для 1 < а < 6. Поскольку Г, = Гаэ«!! Гае«ы 0 . О Гпа +э для всех а, имеем р(а) = р(10а, 10(а + 1)) вследствие (!). Далее, поскольку Р(Б) = Р(2З) + Р(2З + 1) вследствие (!)-(ш), имеем р(а) = р(2а, 2(а + 1)). Отсюда следует, что р(а,Ь) = р(2 10"а,2 10"Ь) для всех т,и > О.
Если 1 < Ь/а < Ь'/а', то р(а, 6) < р(а', Ь'). Причина в том, что существуют целые числа т, и, т', и', такие, что 2 10" а' < 2 10"а < 2 10"Ь < 2™ 10" Ь' как следствие из того факта, что 1ой 2/ !ой 10 является иррациональным числом; следовательно можно применить аксиому (ч).
(См. упр 3.5 — 22, в котором нужно пачожить й = 1 и Н = и!о82/!о810.) В частности, р(а) > р(а + 1) и отсюда следует, что р(а,6)/р(а,6 + 1) > (6 — а)/(Ь+ 1 — а). (См. формулу 4.2.2-(15).) Теперь можно доказать, что р(а,Ь) = р(а',6'), если только 6/а = 6'/а'; для любого большого значения и выполняется р(а,Ь) = р(10"а, 10" Ь) < с„р(10" а, 10"Ь вЂ” 1) < с р(а', Ь'), где с„= 10" (Ь вЂ” а)/(10" (Ь вЂ” а) — 1) = 1+ О(10 "). Для любого положительного целого числа и имеем р(а", Ь") = р(а", Ьа" ) + р(Ьа" ', Ь а™) ч- ..
+ р(6" ~а, Ь") = ир(а,6), Если 10 < а" < 10 +' и 10м < Ь" < 10м +', то р(10 +', 10 ) < р(а", Ь") < р(10"', 10"' «') согласно (ч). Но р(1, 10) = 1 вследствие (и ); отсюда р(10, 10м ) = т' — т для всех т' > т. Приходим к заключению, что [1об,оЬ") — [1ойша"1 — 1 < ир(а,6) < (1ойш 6") + [!ой,о а"! + 1 длЯ всех и и Р(а, Ь) =!ой,э(Ь/а).
[На зто упражнение автора вдохновил Д. И. А. Колен (П. 1. А. Со!геп), который доказал несколько более слабый результат в «. СопзЫпасопа1 ТЛеогу А20 (1976), 367 — 370.) 19. Эквивалентно утверждению, что ((1об 10Р ) тоб 1) имеет равномерное распределение в смысле определения 3.5В. Поскольку 1ой,о Р„ж и 1ой 10ф — 1ой,р з«5 + 0(ф э") согласно 1.2.8 — (14), это эквивалентно равномерному распределению (и!ой,о ф), что следует из упр.
3.5 — 22. [ЛОЬопасс! ()иэггег!у б (1967), 137-140.) То же доказательство показывает, что последовательности (6") подчиняются логарифмическому закону для всех целых чисел 6 > 1, которые не являются степенями 10 [Яглом А. М и Яглом И. М., Незлементараые задачи в элеменгарном изложении (М: Гостехиздат, 1954; Епй!!вЛ !гала!айоп, 1964), Задача 916). Замечание. Этим же свойством обладают многие другие последовательности целых чисел. Например, в работе Регз! П!асов!э, Аппа)з о/РгобаЬ18гу 5 (1977), 72 — 81, показано, что одной из них является (и!) и что последовательность биномиэльных коэффициентов также подчиняется догарифмическому закону в том смысле, что 1 1сш 2 [10~(-) <г) = )оНса г.
ь=о В работе Р. БсЛаьье, МаьЛ. ХасЛпсЛьеп 14В (1990), 137-144, доказано, что знаменатели в непрерывных разложениях дробей имеют логарифмические дробные части, если только частичные отношения имеют повторяющуюся форму с полиномивльной вариацией, как в упр. 4.5 3-16. Очень интересен вопрос, который до сих пор остается открытыьс будет ли последовательность (2!, (2!)!, ((2!)!)!,... ) иметь логарифмические дробные части; см. 3. Н. Сопюау и М. Ю. Т. Сну, Еигейа 25 (1962), 18-19. РАЗДЕЛ 4.3.1 2. Если с-м слагаемым нвляется ис = (иц„м, .. и,сиса)ь, то используем алгоритм А, в котором шаг А2 модифицирован следующим образом.
А2'. [Сложить разряды.) Присвоить юс +- (исс + + и + 1с) шобЬ и /с ь- [(им + + и; + А)/Ь). Сбросить индикатор переполнения. /с +- О. (гХ и гледующее значение А.) (ЬОС(ио) ь— н 0 -Ь п(с — 1) Ь,у.) гА с- гА+ ич, Перенос единицы. Повторить для сп > с > 1. (г13 щ п(ь - 1) + 1,) юз ь- гА. Повторить для 0 < 1 < и. Зассомнить последний перенос в ю„. 3 Время выполнения в предположении, что К = -,',МХ, равно 5.БЛЯХ+ 7Х+ 4 циклов, 4.
Перед шагом А1 можно сделать следующее утверждение "и > 1 и 0 < и„о, < Ь прн 0 < ь < и". Перед шагом А2 справедливо утверждение "0 < у < и; 0 < ип о, < Ь при 0 < ь < и; 0 < ю, < Ь при О < с < с: 0 < А < 1; (и,. с... ио)ь+(оз-с .. оо)ь = (Люс-с .. юо)ь'.
Более точная форма последнего утверждения такова: ис6'+ ~ осЬ' = ЛЬ'+ ~ ~юс6'. а<с<1 а<с<с а<с<с Перед шагом АЗ справедливо утверждение "0 < 1 < и; 0 < ип а, < Ь при 0 < с < и; 0 < тщ < Ь при О < с < 1; 0 < Л < 1 и (из... ссо)ь+(ос .. оа)ь = (1сиб .. юо)ь". После шага АЗ справедливо утверждение, что 0 < юс < Ь при 0 < ь < и; 0 < ю < 1 и (ио-с ..иа)ь+ (о — и . ссо)ь = (юо ., юо)ь.
После етого можно довольно просто закончить доказательство, проверив справедливость нужных импликаций для утверждений и показав, что выполнение алгоритма всегда завершается. (Максимальное значение Ь 3. ЕНН1 И 1 109 ОГЬО 1 ЕНТХ 0 1 2Н БЬАХ 5 Х ЕИТЗ Ньй,1 Х ЗН А00 0.3 МХ ЗНОИ ь+2 МХ 1ИСХ 1 Х ОЕСЗ Н МХ 13ИН ЗВ ЛХХ БТА Н+Н,1 Х 1НС1 1 Х 11Н 2В Х БТХ Ы+Н 1 равно сп — 1, поэтому при т > Ь потребуется изменить шаг АЗ ) б. В1. Присвоить у г — и — 1, и» г — О. В2. Присвоить С с — н, + о,, та +- С шо66, г г- /.
ВЗ. Если С > Ь, прнсвоиты +- г' -г- 1, С г- ш, + 1, ш, г- С шоб Ь и повторить этот шаг до тех пор, пока не будет выполнено неравенство с < Ь. В4. Уменьшить у на единипу н. если 1 > О, вернуться к шагу В2. ! 6. С1. Присвоить у г — и — 1, г +- и, г+- О. С2. Присвоить с +- н + ь;. Если С > Ь, присвоить ш, г — г + 1 н шэ +- 0 при г > А > 1: затем присвоиты г — / и г +- С шод Ь В противном случае, если С < 6 — 1, присвоить гиг г- г и гиь +- 6 — 1 при г > А > с.
После этого прнсвоиты г — у и г+- С, СЗ. Уменьшить 1 на единицу. Если / > О. вернуться к шагу С2, в противном случае присвоить ш, г — г и шь +- 6 — 1 при г > А > О. Т. Если, к примеру, у' = и — 3, то А = 0 с вероятностью (Ь+ 1)/2Ь; Ь = 1 с вероятностью ((6 — 1)/2Ь)(1 — 1/6), а это вероятность того, что произошел перенос н предшествующий разряд не был равен 6 — 1; Ь = 2 с вероятностью ((Ь вЂ” 1)/2Ь)(1/Ь)(1 — 1/Ь) и Ь = 3 с вероятностью И6 — 1)/2Ь)(1/Ь)(1/Ь)(1) При фиксированных А можно просуммировать все вероятности по параметру /д который изменяется от и — 1 до 0: это даст среднее число случаев, когда перенос распространяется на А разрядов: Ь вЂ” 1 / гпэ = ~(п + 1 — А) (1 — — ) + — /г .
2Ь" 6/ Ь/' Для проверки найдем среднее число переносов 1/ 1 тг + 2тс+ + пгл = — '[и — (1 — (-) )), что согласуется с формулой (6). Н. ЕМТ1 М-1 1 ЗН ЬРА Ч 2 К ЛОЧ ОЕЕО 1 1МСА 1 К БТ2 М+М 1 БТА Ы,2 К 2НЕРА О 1 Х 1МС2 1 К АРР Ч,1 Х 10Ч ЗН К БТА М,1 Х 4Н РЕС1 1 Х 1МОЧ 4Г Х 11ММ 2Н Х ! ЕМТ2 1,1 Е Время выполнения программы зависит от Š— числа позиций, в которых и + е, > 6, и от К вЂ” общего числа переносов Нетрудно заметить, что К вЂ” это та же самая величина, которая появляется в программе А. Анализ в тексте раздела показывает, что среднее значение Е равно Х((Ь вЂ” 1)/2Ь), а среднее значение К равно -г(Х вЂ” Ь ' — Ь э — — Ь "). Таким образом, если пренебречь членами порядка 1/Ь, время выполнения программы будет равно ОХ+ 7 + 7К+ 3 13Х+ 3 циклам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
