столь большим, что будут выполняться неравенства 10 * • 5*" < <J и 4*" > М; следовательно, в связи с монотонностью функции F получаем

EH10*"-5*=)-F(10*="-4*=))

< Е (F(10*"-5*)-F(10*""--5*=)) + E И10"-4*)-(10""-4))

m<0 7П>0

= F(10"*"5*) +1 - F(10V) < 2е.

8. Если S > г, то Po(10"s) равно 1 при малых п и равно О, если LlO"sJ > [10"rJ. Наименьшее п, для которого так бывает, может быть произвольно большим, так что для No{e) нельзя дать никакой равномерной оценки, не зависящей от s. (Вообще говоря, в учебниках по анализу доказывается, что из такой равномерной оценки следовало бы, что предельная функция So(s) непрерывна, а это не так.)

9. Пусть gi, 92, • • таковы, что Ро(п) = gi("o) +g2("7) + • • • Для всех п. Тогда Рт{п) = l-"gi ("о ) + 2-"д2("7) + • • • для всех тип.

10. Если 1 < г < 10, производящая функция C{z) имеет простые полюсы в точках 1 + w„, где Wn = 2%ni/ In 10. Следовательно,

" - 1-Z + Е (1п10)(.-1-ш) +

где E{z) есть аналитическая функция на всей плоскости. Таким образом, если в = arctan(27r/ In 10), то

2 - / е"""" "" - 1 N

Ст = logior - 1 - - Е{„Ц + „)т) +

sin(m6 + 27г1ов,п г) - sin(m6) = logior-l+ - ------

mg + 27rlogior)-sin(m6) 1 \

7Г(1 + 47Г2/(1П 10)2)™ V (1 + 167Г7(1П 10)2)"/ /

11. Если величина (log U) mod 1 равномерно распределена в интервале [О .. 1), то так же распределена и величина (log;, 1/U) mod 1 = (1 - log;, U) mod 1.

12. Имеем

h{z)= Г f{x)dxg{z/bx)/bx+ f fix)dxgiz/x)/x;

Jl/b Jz

следовательно,

hjz) - l{z) l(z)

Так как f(x) > О, \{h(z) - l{z))ll{z)\ < J)Jix)dxA{g) + Jf{x)dxAig) для всех z, то A{h) < A{g). В силу симметрии A{h) < A{f). [Bell System Tech. J. 49 (1970), 1609-1625.]

13. Пусть X = (log;, f/) mod 1 и У = (log;, F) mod 1, так что .Y и У независимо и равномерно распределены в интервале [О .. 1). Ни одного сдвига влево не потребуется тогда и только тогда, когда ЛГ + У > 1, и это происходит с вероятностью .

(Аналогично результат выполнения деления по алгоритму 4.2.1М не нуждается в нормализующих сдвигах с вероятностью I; здесь достаточно более слабого предположения о совпадении распределений независимых операндов.)

14. Для удобства вычисления проводятся здесь для b = 10. Если Л = О, то вероятность переноса равна

/J f /• dxdy

\\п10) yi<.v<io X у

l+V>10

(рис. А-7). Интеграл равен

rlO J.. /-10

Jo у ]\о-у X Jo У ho-y

/ 7ЧгТо) =/(l

у

200 3000

+

(Последний интеграл, по существу, является "билогарифмическим".) Значит, вероятность переноса при Л = О равна (1/In 10)(7г7б - 2 X;„>i 1/"10") « .27154. [Замечание. Если Ь = 2 и Л = О, переполнение дробной части происходит всего, так что этот вывод подтверждает справедливость соотнощения I]n>i l/nS" = 7г712 - (In 2)72.] Если Л > О, вероятность равна

/у/--Ч Г dx( L.\4Y l y- i

VlnlO/ Ую-* у Jio-v X WlQj \n4Q> -п210"(*+1)у

Таким образом, если b = 10, переполнение дробной части должно возникать с вероятностью приблизительно .272po+.017pi +.002р2+- • •. Когда 6 = 2, соответствующие величины равны Ро + .655р1 + .288р2 + .137рз + .067р4 + .033р5 + .016рб + .ООВрт + .004р8 + .002р9 + .OOlpio + • • .

Если теперь воспользоваться значениями вероятностей из табл. 1, разделив их на .91 для устранения нулевых операндов, и принять, что вероятности не зависят от знака операндов, можно при Ь = 10 предсказать значение вероятности около 14% против 15% из упр. 1. При 6 = 2 мы предсказываем значение, приблизительно равное 48%, в то время как таблица даст 44%. Эти расхождения, конечно, лежат в допускаемых пределах, если учтена ошибка эксперимента.

15. Если Л = О, то старшая цифра равна 1 тогда и только тогда, когда возникает перенос. (Возможно, что при 6 > 4 в результате переполнения дробной части и последующего округление появится ведущий разряд, равный 2, но в этом упражнении округление игнорируется.) Как показано в предыдущем упражнении, вероятность переполнения дробной части равна приблизительно .272, а .272 < logjo 2.

Если Л > О, то ведущий разряд равен 1 с вероятностью

()"a:rif / f)<()t/:rif/<.<,f)--«

или 10-к<1<10 - -

16. Для доказательства положения, сформулированного в указании [его авторство принадлежит Ландау (Landau, Prace Matematyczno-Fizyczne 21 (1910), 103-113)], сначала предположим, что lim sup о„ = А > 0. Пусть е = А/(А + 4М), и выберем Л так, что oi -f- • -f- а„ < eAn для всех п > N. Пусть п > N/{1 - е), п > 5/е будет таким, что о„ > jA. Тогда по индукции йп-к > Оп - кМ/{п - еп) > jX для О < Л < en и Е„-,„<*<„ а* > А(бп - 1) > iAen. Но

<к<п

так как п - en > N. Аналогичное противоречие возникает и если liminf Оп < 0.

Предполагая, что Pm+iin) А при п оо, положим о* = Рт{к) - А. Если m > О, то Ofc удовлетворяют гипотезе, сформулированной в указании, поскольку О < Рт{к) < 1 (см. 4.2.2-(15)); отсюда Рт{п) А.

17. См. J. Math. 5ос. Japan 4 (1952), 313-322. (Тот факт, что гармоническая вероятность расширяет понятие обычной вероятности, следует из теоремы Чезаро (Cesaro, Atti deHa Reaie Accademia. dei Lincei, Rendiconti (4) 4 (1888), 452-457). Перси Дьяконис (Persi Diaconis, Ph. D. thesis. Harvard University, 1974) среди прочего показал, что определение вероятности через повторяющееся усреднение является более слабым, чем определение гармонической вероятности, в смысле следующей строгой формулировки. Если limm-.oo liminf„-..oo Pm(n) = limm-»oo limsup„.oo Pm(n) = A, TO гармоническая вероятность равна A. С другой стороны, утверждение "10* < п < 10*°+* для целых чисел к > О" имеет гармоническую вероятность 1, в то время как повторяющееся усреднение никогда не присвоит этому утверждению некоторой конкретной вероятности.)

18. Пусть р(о) = Р{Ьа) и р{а,Ь) = 1]„<к<ьР(А) для 1 < а < Ь. Поскольку La = Lioa U iioa+i и • • • и Lioa+9 ДЛЯ всех о, имеем р{а) = р(10о, 10(а + 1)) вследствие (i). Далее, поскольку Р(5) = Р(25) -I- Р(25 -- 1) вследствие (i)-(iii), имеем р(о) = р(2о,2(о + 1)). Отсюда следует, что р{а,Ь) = р(2"10"а, 2"10"Ь) для всех m,n > 0.

Если 1 < Ь/а < Ь/а, то р{а,Ь) < р{а, Ь). Причина в том, что существуют целые числа т, п, т, п, такие, что 2"lOa < 2"10"а < 2"10Ь < 2"l0"b как следствие из того факта, что log 2/ log 10 является иррациональным числом; следовательно можно применить аксиому (v). (См. упр. 3.5-22, в котором нужно положить Л = 1 и {/„ = п log 2/log 10.) В частности, р(а) > р(а -- 1) и отсюда следует, что p{a,b)/p{a,b + 1) > (Ь - о)/(Ь +1 - а). (См. формулу 4.2.2-(15).)

Теперь можно доказать, что р(а,Ь) = р(а,Ь), если только Ь/а = Ь/а; для любого большого значения п выпапняется р{а,Ь) = р(10"а, 10"Ь) < Спр(10о, 10"Ь - 1) < с„р(о, 5), где Сп = 10"(5 - а)/(10"(Ь - а) - I) = 1 + 0(10-").

Для любого положительного целого числа п имеем

р(о", 5") = р(а", Ьа"-) + р{Ьа"-\Ьа") + + р{Ь"-\5") = пр{а, Ь).

Если 10"" < а" < 10"+ и 10"" < 5" < 10"+S то р(10"+\ Ю") < р(а", 5") < р(10", 10""+) согласно (v). Но р(1,10) = 1 вследствие (iv); отсюда р(10", 10") = т - m для всех т > т. Приходим к заключению, что [logiob"J - [iogio ""J ~ 1 "?(".) < [logio b"J + [logio ""J +1 ДЛЯ всех n и р{а,Ь) = logio(b/a).

[На это упражнение автора вдохновил Д. И. А. Кохен (D. I. А. Cohen), который доказал несколько более слабый результат в J. Combinatorial Theory А20 (1976), 367-370.]

19. Эквивалентно утверждению, что ((log 10Р„) mod 1) имеет равномерное распределение в смысле определения 3.5В. Поскольку logjo Р„ = nlog 100 - logm \/5 -I- О(0~") согласно 1.2.8-(14), это эквивалентно равномерному распределению (nlogjo), что следует из упр. 3.5-22. [Fibonacci Quarterly 5 (1967), 137-140.] То же доказательство показывает, что последовательности (5") подчиняются логарифмическому закону для всех целых чисел 5 > 1, которые не являются степенями 10 [Яглом А. М. и Яглом И. М., Неэяемен-тариые задачи в элементарном изложении (М: Гостехиздат, 1954; English translation, 1964), Задача 91b].

Замечание. Этим же свойством обладают многие другие последовательности целых чисел. Например, в работе Persi Diaconis, AnnaJs of Piobability 5 (1977), 72-81, показано, что одной из них является (п!) и что последовательность биномиальных коэффициентов