Глава 2. Сложность в среднем

42. Пусть изначально у нас имеется генератор случайных веще­ственных чисел, принадлежащих отрезку [0,1], и вероятность появ­ления числа, принадлежащего отрезку [а,Ъ], О ^ а ^ Ъ ^ 1, есть Ъ - а. Пусть даны неотрицательные вещественные числа a_n,a-i,...,a та-кие, что a_n + ai + ... + a =1. Как определить генератор чисел, при-надлежащих множеству {0,1, ...,JV - 1}, такой, что вероятность появ­ления числа к, 0 s= к s= N - 1, равна а_к?

42. Предположим, что у нас нет другого генератора случайных чи­сел, кроме генератора, в результате обращения к которому появляет­ся 0 с вероятностью р или 1 с вероятностью 1 - р, причем о р мы ничего не знаем, кроме того, что р^0ир/1. Как с помощью этого генератора можно сконструировать генератор, в результате обраще­ния к которому появляется 0 или 1 с одинаковой вероятностью 1/2?

Указание. Порождая подряд две цифры с помощью имеющегося генера­тора, мы получаем комбинации 0,1 и 1, 0 с одинаковой ненулевой вероят­ностью.

44. (Продолжение предыдущей задачи.) Чему равно математиче­ское ожидание числа обращений к изначально имеющемуся генерато­ру случайных чисел при построении последовательности пар до появ­ления 0,1 или 1, 0? Найти сложность в среднем алгоритма получения к «равновероятных» нулей и единиц с помощью сконструированного генератора (затраты определяются количеством обращений к изна­чально имеющемуся генератору). Можно ли указать значения р, для которых эта сложность имеет минимальное и, соответственно, мак­симальное значение?

44. Предложенную в указании к задаче 43 идею обобщить на слу­чай, когда необходимо сконструировать генератор random(JV), N^ 1, описанный в § 8. Найти сложность в среднем алгоритма получения к равновероятных случайных чисел из отрезка [0,JV-1] (затраты определяются числом обращений к изначально имеющемуся генера­тору).

44. Сохранится ли для сложности в среднем формула 2n In п + 0(п), если в задаче о разрезании полоски клетчатой бумаги на отдельные клетки (см. пример 8.1) считать, что плата за вырезание одной слу­чайно выбранной клетки равна не п -1, а п рублей? Тот же вопрос, если эта плата составляет п² рублей.

44. Известное утверждение (теорема Дирихле, 1849 г.), что два

случайных числа x,yeN⁺ с вероятностью Р, равной —, оказываются взаимно простыми, имеет тот смысл, что если ввести в рассмотрение число М{п), равное количеству пар (х,у) таких, что х и у взаимно

Задачи

73

просты и, дополнительно, 1 ^ x, y ^ n, то предел lim —т- существует

и равен 4. Предполагая (не обосновывая и не вникая в то, мож­но ли это^обосновать; это соответствует «физическому уровню стро­гости»), что множество N⁺ может быть превращено в вероятност­ное пространство так, что случайное xeN+ кратно фиксированно­му deN⁺ с вероятностью -, можно предложить несколько довольно

простых доказательств равенства P = —. Для этого можно восполь­зоваться тем, что

7 =

Zjn2 6

n=1

(доказано Эйлером в 1734 г.) или свойством дзета-функции Римана, согласно которому

со

V 1 П 1

7 = II

Z-in^s 11 1 - p^s

n=1 p — простое

и которое справедливо, например, для всех целых s > 1, и, в частно­сти, для s = 2.

В упомянутых выше предположениях доказать равенство P = —, используя следующие подходы.

а) Для произвольного d е N⁺ вычислить вероятность ip{d) того, что для случайных x,yeN+ выполнено d = нод(x,y). Из равенства

со

P = 1 - Х>d определить P.^г

d=2

б) Для произвольного простого p вычислить вероятность т/>(p) то­ го, что по крайней мере одно из случайных x, y е N+ не делится на p. Из равенства P = V'(p) определить P.²

p — простое

Указания. а) _V(d) = -^ ; б) т/>(p) = 1 - \.

Для того чтобы сделать доказательство «настоящим», надо для произволь­ного neN⁺ детально рассмотреть ситуацию 1 ^x,y ^n и перейти к пределу при n^ оо, что потребует более кропотливой работы.³

См. [19, разд. 4.5.2].

См. [50, гл. I, разд. 3, прим. 3.3].

См. [19, разд. 4.5.2, упр. 10].