Задачи к главе 6

135

сваивание в строке 5. Предполагается, что числа в массиве А различны и расположены в случайном порядке (все перестановки равновероятны).

а.Если число х случайно выбрано из г различных чисел, то с какой вероятностью оно окажется максимальным числом среди них?

б.Как соотносится A[i] с предыдущими элементами массива для тех г, при которых выполняется строка 5?

в.Чему равна вероятность выполнения строки 5 программы для данного значения г?

г.Пусть Si - случайная величина, равная 1 или 0 в зависимости от того, выполнялась строка 5 на г-м шаге цикла или нет. Чему равно M[s4-]?

д.Пусть s = S1+S2 + - • -+sn - общее число присваиваний в строке 5 при исполнении всей программы. Покажите, что M[s] = O(lgra).

6-3 Проблема выбора

Заведующая кафедрой принимает на работу нового сотрудника. Она назначила собеседования га претендентам и хочет выбрать наиболее квалифицированного из них. Однако университетские правила требуют, чтобы после беседы претенденту сразу сообщалось, принят он или нет.

Для этого она применяет такое правило. Сначала она говорит с первыми к претендентами, отказывая им независимо от их квалификации. Если среди оставшихся есть более квалифицированный, чем первые к, то первый из таковых принимается. Если нет, принимается последний из претендентов. Покажите, что вероятность выбрать таким способом лучшего из претендентов будет максимальна (и равна примерно 1/е), если к примерно равно га/е.

6-4 Вероятностный счётчик

С помощью -битного счётчика мы можем считать до 2* - 1. Следующий приём вероятностного подсчёта (probabilistic counting, R. Morris) даёт возможность вести счёт до куда больших значений, правда ценою некоторой потери точности.

Выберем возрастающую последовательность целых неотрицательных чисел щ (где г меняется от 0 до 2* - 1). Её смысл таков: если значение -битного регистра равно г, то это означает, что подсчитываемое количество (число выполненных операций Increment) примерно равно гц. Мы считаем, что щ = 0.

Операция Increment увеличивает значение счетчика, содержащего г, с некоторой вероятностью. Именно, число г увеличивается на 1 с вероятностью 1/(гаг+1 -щ), и остается неизменным в остальных случаях. (Если г = 2* - 1, то происходит переполнение.) Идея проста: в среднем для увеличения г на единицу потребуется как раз гаг 1 - щ операций.

Если гц = г для всех г 0, то получаем обычный счётчик. Более интересные ситуации возникают, если выбрать, например, гц = 28-1 для г > 0 или гц = Fi (г-е число Фибоначчи, см. разд. 2.2).

Мы будем предполагать, что гг2* 1 достаточно велико, и пренебрегать возможностью переполнения.

а.Покажите, что математическое ожидание содержимого счётчика после выполнения п операций Increment, в точности равно п.

б.Дисперсия случайной величины, равной содержимому счётчика после п операций Increment, зависит от выбора последовательности по,щ,.... Найдите эту дисперсию для случая гц = 100г.

Замечания

Общие методы решения вероятностных задач обсуждались в знаменитой переписке Паскаля (B.Pascal) и Ферма (P.de Fermat), начавшейся в 1654 году, и в книге Гюйгенса (C.Huygens, 1657). Более строгое изложение теории вероятностей было дано в работах Бернулли (J.Bernoulli, 1713) и Муавра (A.De Moivre, 1730). Дальнейшее развитие теории вероятностей связано с именами Лапласа (P. S.de Faplace), Пуассона (S.-D. Poisson) и Гаусса (C.F.Gauss).

Суммы случайных величин исследовались П. Л. Чебышёвым и А.А.Марковым (старшим). В 1933 году А.Н.Колмогоров сформулировал аксиомы теории вероятностей. Оценки хвостов распределений приводят Чернов [40] и Хофдинг [99]. Важные результаты о случайных комбинаторных структурах принадлежат Эрдёшу (P. Erd6s).

Литература по теме главы: Кнут [121], Лю [140] (хорошие пособия по элементарной комбинаторике и подсчету); Биллингсли [28], Чанг [41], Дрейк [57], Феллер [66], Розанов [171] (стандартные учебники по теории вероятностей); Боллобас [30], Хофри [100], Спенсер [179] (техника вероятностного анализа).