(d) (См. упр. 3.4.1-29.) Значение X •«- [N{1 - t ")J требуется отбросить с вероятностью, равной только 0{n/N). Точные детали тщательно проработаны в САСМ 27 (1984), 703-718, а практическое осуществление приведено в АСМ Тгалз. Math. Software 13 (1987), 58-67. (Этот метод хорош, когда, скажем, 5 < п < iV.)

После пропуска X записей и выбора следующих присвоим п<-п - 1, N<-N - X - 1 и будем повторять процесс до тех пор, пока п = 0. Подобное приближение ускоряет метод резервуара [см. АСМ Trans. Math. Software 11 (1985), 37-57].

9. В резервуар будет помещено семь записей: 1, 2, 3, 5, 9, 13, 16. В окончательной выборке содержатся записи 2, 5, 16.

10. Удалить шаг R6 и переменную т. Заменить таблицу / таблицей записей, инициализированных первых п записей на шаге R1, и, заменив М-е значение таблицы, перейти в алгоритме к шагу R4.

11. Поступая, как в разделе 1.2.10, в котором рассматривался частный случай, когда п = 1, получаем, что производящая функция равна

, „/1 nW2 п \ fN-п п \

Среднее значение равно п + IZn<t<N("/*) ~ "( + ~ "), дисперсия оказывается равной п(Ял -Нп)- п2(Я - Я).

12. Заметим, что п" = (btt)... (ЬзЗ)(Ь22), поэтому находим алгоритм, который переводит представление тг в тг~. Присвоить bj <- j для 1 < j < t. Затем для j = 2, 3, ..., t (в таком порядке) произвести взаимный обмен bj •е+ bay Наконец для j = 4, ..., 3, 2 (в таком порядке) присвоить baj <- bj. (Алгоритм основывается на том факте, что (att)-Ki = Ki(btt).)

13. Перенумеровав колоду О, 1, ..., 2тг - 2, находим, что номер (2ж) mod (2тг - 1) s раз присвоен карте с номером ж, в то время как номер (ж -I- l)mod(2Ti - 1) с раз присвоен карте с номером ж. Получим (с следует из s) = cs = sc. Значит, произведение любого количества с и s можно привести к виду ec*". Также 2*"("~ = 1 по модулю (2тг - 1). Поскольку s"" и с"~ - тождественные перестановки, то возможно не более (2тг - l)ifi{2n - 1) компоновок. {Точное число различных компоновок равно (2тг- l)fc, где к равно порядку 2 по модулю (2тг - 1). Для случая, когда s = с, сР устанавливает карту О, s = с> = тождество.) Дополнительные детали приводятся в SIAM Review 3 (1961), 293-297.

14. (а) §. Это можно установить, не обращая внимания на то, где и.менно была сдвинута карта, кроме случая, когда карта была взята из первых трех или последних двух позиций. (Ь) I. Три разрезания и перетасовки приведут к перемешиванию самое большее восьми циклически возрастающих подпоследовательностей а а(х,+1) mod п • • a(xj+i-i) mod п- Значит, подпоследовательности заблокированы. [Несколько магических трюков основано на том факте, что три разрезания и перетасовки являются совсем неслучайными; см. Martin Gardner, Mathematical Magic Show (Knopf, 1977), гл. 7.]

15. Присвоить Yj <- j для t - n < j < t. Затем для j = t, t - 1, ..., t - n + 1 проделать следующие операции. Присвоить к •«- [jU\ + 1. Если к > t - п, присвоить Xj <- Yk wYk <Yj, иначе, если к = Xi для некоторых г > j (можно использовать таблицу идентификаторов алгоритма), присвоить Xj <- У, и У{ <- У; иначе - присвоить Xj <- fc. (Идея основана на предположении,что У;-n+i, ,Yj представляют At-+i, ...,АГ,и, если i > j и Xi < t - n, на предположении, что У представляют Хх{ в исполнении алгоритма Р. Интересно доказать правильность алгоритма Дахла. Алгоритм основан на наблюдении, что на шаге Р2 из Хк ф к следует, что Xk > j для 1 < fc < j.)

16. Можно предположить, что п < jiV, иначе достаточно найти N - п элементов, не входящих в выборку. Идея заключается в том, чтобы, используя таблицу случайных данных размерности 2п, генерировать случайные числа между 1 и iV, хранить их в таблице и выбрасывать дубликаты до тех пор, пока не будут сгенерированы п различных чисел. Среднее число генерируемых случайных чисел равно N/N + N/{N - 1) + +N/{N-n+l) < 2п согласно упр. 3.3.2-10, а среднее время обработки каждого числа равно 0(1). Требуется получить выходные результаты в порядке возрастания, что можно сделать следующим образом. Если использовать таблицу упорядоченных случайных данных (упр. 6.4-66) с линейным зондированием, таблица случайных данных сформируется, как только значения будут включаться в порядке возрастания, и общее среднее число проб будет меньше п. Так, если использовать монотонные случайные адреса, например [2п{к - l)/N\, для ключа fc, получится вывод ключей в упорядоченном виде в результате самое большее двух просмотров таблицы. [См. САСМ 29 (1986), 366-367.]

17. Покажите по индукции перед шагом j, что множество 5 является случайной выборкой j - N -1 + п целых чисел из - 1}. [САСМ 30 (1987), 754-757. Метод Флойда может быть использован для ускорения выполнения упр. 16. Это, по существу, двойной алгоритм Дахла из упр. 15, который оперирует убывающими значениями j; см. упр. 12.]

РАЗДЕЛ 3.5

1. Ь-ичная последовательность - да (см. упр. 2); последовательность [0.. 1) - нет (так как предполагается только конечное множество значений элементов).

2. Последовательность 1- и 2-распределенная, только не 3-распределенная (двоичное число 111 никогда не появляется).

3. Повторите последовательность из упр. 3.2.2-17 с периодом длиной 27.

4. Если i/i(n), г/2(п), г/з(п), г/4(п) считать соответствующими четырем вероятностям, то получим i/i(n) -I- г/2(п) = г/з(п) -t-1/4(71) для всех п. Так что требуемый результат вытекает из сложения пределов.

5. Последовательность начинается так: j, , , j, j, j, j, , , , , , , , и т. д. Когда n = 1, 3, 7, 15, ..., получим г/(п) = 1, 1, 5, 5, ..., так что г/(2*" - 1) = «(2* - 1) = (2*-1)/3. Значит, и{п)1п колеблется между \ и приблизительно и предел не существует. Вероятность не определена. [Методы из раздела 4.2.4 показывают, однако, что численное значение может быть определено так: Рг((7п < \) - Рг(старший разряд представления п -t-1 в системе счисления с основанием 4 равен 1), т. е. log4 2 = 5.]

6. По индукции и согласно упр. 5

Рг(5,(п) для некоторого j, 1 < j < к) = Pr(5j(n)).

3 = 1

Когда fc 00, последняя является монотонной последовательностью, ограниченной 1, так что она сходится и

Рг(5j(n) для некоторых j > I) > y~]Pr(Sj(n))

для всех fc. В качестве контрпримера, показывающего, что равенство будет не всегда, не трудно устроить так, что Sj{n) будет всегда верно для некоторых j, однако Рг(5,(п)) = О для всех j.

7. Пусть Pi = EjiPi{Sij{n)). Результат предыдущего упражнения можно обобщить так: Pr(5j(n) ддя некоторого j > 1) > IZ ;>i Е(5(п)) для любых непересекающихся утверждений Sj{n). Так что получим 1 = Рг(5; ,(п) для некоторых г, j > 1) > Z!i>i Р1(5;(п)для некоторого j > 1) > J2i>iPi = 1 и, следовательно, Pr(5ij(n) для некоторого j > I) = Рг- Зададим б > 0; пусть I достаточно велико, так, что 5Z/=i Р" 1 ~ • Пусть

ij!>,(iV) = (число п < N с Sij{n) справедливых для некоторого j > l)/N.

Очевидно, что Y.i=i Фг{Ю < 1, и для всех достаточно больших N получим E/=2i*(-) -

Ef=2P - следовательно, фl{N) < 1 - ф2{N) - - </>y(iV) < 1 - рз----- Р/ + е <

1 - (1 - б -pi) + б = pi + 2б. Это доказывает, что Pr(5ij(п) для некоторого j > I) < pi + 2б. Значит, Pr(5ij(n) для некоторого j > 1) = pi и требуемый результат получается для i = 1. Из симметрии гипотез следует, что он справедлив для любого значения г.

8. Сложите вероятности для j, j + d, j + 2d, ..., m + j - d ъ определении E.

9. limsup„ (a„ + bn) < limsup„ , a„ + limsup„ , &„; отсюда найдем, что

limsup((yin - of H-----h {Утп - a)) < ma - 2ша + ma - 0,

и это может происходить только тогда, когда каждая {yjn - а) стремится к нулю. 10. В оценке суммы в равенстве (22).

11- {Uin} fe-распределена, если ({/„) (2, 2fc - 1)-распределена.

12. Примените теорему В с f{xi,... ,Хк) - [и <max(zi,.. ,Хк) < v].

13. Пусть

Рк = Рг(с Un начинается серия длиной fc - 1)

= Pr(t/„-i б[а../3), Uni[a..p), Un+k-2i[a..P), Un+k-i £ [а .. Р)) = р\1-р)-\

Остается преобразовать это выражение в вероятность того, что f{n) - f{n - 1) = fc. Пусть ik{n) = (число j <пс f{j) - f{j - 1) = fc); пусть pk{n) = (число j < n с Uj - началом серии длиной fc - 1) и пусть р{п) также равно числу 1 < j < п с Uj е [а . ./3). Получим pk{f{n)) = uk{n), p{f{n)) = п. Когда п оо, мы должны получить f{n) -> оо. Следовательно,

iyk{n)ln={pk{f{n))lf{n)) {f{n)/p{f{n)))-pk/p = p{l-p)-\

[Здесь используется только тот факт, что последовательность (fc + 1)-распределена.]

14. Пусть Рк = Рг({7п начало серии длиной fc)

= Pr(t/„ 1 >Un<--- < Un+k-1 > Un+k)

why.{ir)CV)-{r)-{r)-)

к fc + i

(fe + l)! (fe + 2)!

(cm. упр. 3.3.2-13). Сейчас поступим, как в предыдущем упражнении, чтобы преобразовать это выражение в Рг(/(п) - f{n - 1) = fc). [Только нужно предположить, что последовательность (fc -t- 2)-распределенная.]