Случайные переменные и ожидания - Рандомизированные алгоритмы

До настоящего момента наш анализ рандомизированных алгоритмов и процессов базировался на выявлении некоторых “плохих событий” и ограничении их вероятности. Такой анализ относится к качественному типу в том смысле, что алгоритм либо выполняется успешно, либо нет. Количественный анализ учтет некоторые характеристики, связанные с поведением алгоритма (например, его время выполнения, или качество предоставляемых решений), и постарается определить ожидаемые размеры этих характеристик для случайных решений, принимаемых алгоритмом. Чтобы такой анализ стал возможен, необходимо ввести фундаментальное понятие случайной переменной.

Для заданного вероятностного пространства случайной переменной X называется функция из пространства выборки в пространство натуральных чисел, такая, что для любого натурального числаj получение значения j множеством X^-1(j) всех точек выборки является событием. Конструкция Pr[X = j] может использоваться как неформальное сокращение для Pr[X^-1(j)]; фактически мы задаем вопрос о вероятности того, что X примет заданное значение, которое рассматривается как значение “случайной переменной”.

Для заданной случайной переменной X часто представляет интерес ее ожидание — “среднее значение”, принимаемое X. Определим его по формуле

в предположении, что при расхождении суммы оно принимает значение ∞. Итак, например, если Х принимает каждое из значений {1, 2, ..., n} с вероятностью 1/n, то

Пример: ожидание первого успеха

В следующем примере правильно выбранная случайная переменная позволяет оценить некоторый аналог “времени выполнения” простого случайного процесса. Допустим, вы бросаете монетку, на которой с вероятностью p > 0 выпадает “орел”, а с вероятностью 1 - p выпадает “решка”. Результаты разных бросков монетки независимы. Если бросать монетку до тех пор, пока не выпадет “орел”, какое ожидаемое число бросков придется выполнить? Чтобы ответить на этот вопрос, обозначим X случайную переменную, равную количеству выполненных бросков. Для j > 0 имеем Pr[X = j] = (1 - p)^j-1p: чтобы этот процесс состоял ровно из j шагов, на первых j - 1 бросках должна выпасть “решка”, а на j-м броске должен выпасть “орел”. Применяя определение, получаем

Таким образом, мы получили следующий интуитивно понятный результат.

(13.7) При многократном выполнении независимых испытаний в эксперимент, каждое из которых завершается успешно с вероятностью p > 0, ожидаемое количество испытаний, которые должны быть выполнены до первого успеха, составляет 1/p.

Линейность ожидания

В разделах 13.1 и 13.2 мы разбивали события на объединения более простых событий и работали с вероятностями этих более простых событий. Этот прием также эффективно работает со случайными переменными и базируется на принципе линейности ожидания.

(13.8) (Линейность ожидания). Для двух случайных переменных X и Y, определенных в одном вероятностном пространстве, можно определить X + Y как случайную переменную, равную Х(ω) + Y(ω) для точки выборки ω. Для любых X и Y выполняется E[X + Y] = E[X] + E[Y].

Доказательство не приводится, оно достаточно простое. Мощь (13.8) в основном обусловлена тем, что утверждение относится к сумме любых случайных переменных; никакие ограничивающие предположения не нужны. В результате, если потребуется вычислить ожидание сложной случайной переменной X, мы можем сначала записать ее как сумму более простых случайных переменных X = X₁ + X₂, + ... + X_n, вычислить каждое E[X_i], а затем определить E[X] = ∑E[X_i]. Рассмотрим несколько примеров практического применения этого принципа.

Пример: угадывание карт

Чтобы поразить ваших друзей, вы предлагаете им перетасовать колоду из 52 карт, а затем открывать по одной карте. Вы пытаетесь угадать, какая карта будет открыта следующей. К сожалению, ваши способности к ясновидению оставляют желать лучшего, а память не позволяет точно запомнить уже открытые карты, поэтому ваша стратегия заключается в простом случайном равномерном выборе карты из полной колоды. Сколько попыток окажутся успешными?

Рассмотрим более общую формулировку задачи: колода состоит из n разных карт, а X — случайная переменная, равная количеству правильных предсказаний. Существует неожиданно простой способ вычисления X: случайная переменная X_i (для i = 1, 2, ..., n) определяется равной 1, если i-е предсказание было правильным, и 0 в противном случае. При этом X = X₁ + X₂ + ... + X_n, и

Стоит отметить полезный факт, который неявно следует из предыдущих вычислений: если Z — случайная переменная, принимающая только значения 0 и 1, то E[Z] = Pr[Z = 1].

Так как E[X_i] = 1/n для всех i, получаем

Итак, нам удалось доказать следующее:

(13.9) Ожидаемое количество правильных предсказаний в стратегии без запоминания равно 1 независимо от n.

Попытка вычислить E[X] непосредственно из определения создаст куда больше проблем, потому что это потребует гораздо более сложного суммирования. За внешне безобидным утверждением (13.8) скрывается значительный уровень сложности.

Угадывание с запоминанием

Возьмем второй сценарий: с ясновидением ситуация не изменилась, но вы научились запоминать, какие карты уже были открыты. Следовательно, при предсказании следующей карты равномерный случайный выбор ограничивается только теми картами, которые еще не открывались. На сколько правильных предсказаний можно рассчитывать при такой стратегии?

И снова случайная переменная X_i принимает значение 1, если i-е предсказание верно, и 0 в противном случае. Чтобы i-е предсказание было правильным, необходимо угадать карту только из n- i + 1 оставшихся карт; следовательно,

и приходим к

Последнее выражение называется гармоническим числомH(n); эти числа уже неоднократно встречались в двух предыдущих главах. В частности, в главе 11 было показано, что Н(n) как функция n близко воспроизводит значение Для наших целей базовая граница Н(n) будет переформулирована следующим образом.

(13.10) ln(n + 1) < H(n) < 1 + ln n, или менее формально, Н(n) = Ө(log n).

Итак, когда вы получаете возможность запоминать уже открытые карты, ожидаемое количество правильных предсказаний значительно превышает 1.

(13.11) Ожидаемое число правильных предсказаний в стратегии предсказания с запоминанием составляет Н(n) = Ө(log n).

Пример: сбор купонов

Прежде чем переходить к более сложным примерам, рассмотрим еще один тривиальный пример, в котором линейность ожиданий приносит существенную пользу. Предположим, фирма-производитель овсяных хлопьев кладет в каждую коробку купон. Всего существуют n разных видов купонов. Сколько коробок придется купить, чтобы собрать купоны всех типов?

Очевидно, понадобится не менее n коробок; но будет весьма удивительно, если после покупки n коробок будут собраны все n типов купонов. По мере того как в коллекции будет появляться все больше разных типов, вероятность обнаружить отсутствующий купон становится все ниже. После того, как у вас появятся n - 1 из n видов купонов вероятность того, что новая коробка содержит купон отсутствующего типа, равна всего 1/n.

Следующий метод позволяет точно определить ожидаемое время. Пусть X — случайная переменная, равная количеству коробок, купленных до первого обнаружения купона каждого типа. Как и в наших предыдущих примерах, эта случайная переменная выражается достаточно сложно, и ее было бы удобнее записать в виде суммы более простых случайных переменных. Для этого рассмотрим следующую естественную идею: процесс сбора купонов продвигается вперед каждый раз, когда вы покупаете коробку с купоном, которого у вас еще нет. Таким образом, основная цель процесса — обеспечить продвижение n раз. Какова вероятность того, что в заданный момент времени вы добьетесь прогресса на следующем шаге? Это зависит от того, сколько разных типов купонов у вас уже есть. Если у вас уже есть j типов, то вероятность продвижения на следующем шаге составляет (n - j)/n: из n типов купонов n - j позволяют продвинуться вперед. Так как вероятность зависит от того, сколько разных типов купонов у вас уже есть, отсюда следует естественная идея разбиения X на более простые случайные переменные.

Предположим, процесс сбора купонов находится в фазе j, вы уже собрали купоны j разных типов и ждете возможности получить новый тип. При обнаружении нового типа купона завершается фаза j и начинается фаза j + 1. Таким образом, процесс начинается в фазе 0 и завершается в фазе n - 1. Пусть X_j — случайная переменная, равная количеству шагов, выполненных в фазе j. Тогда X = X₀ + X₁ + ... + X_n-1, а значит, достаточно найти E[X_j] для каждого j.

(13.12) E[X_j] = n/(n - j).

Доказательство. В каждом шаге фазы j фаза завершается немедленно в том и только в том случае, если следующий купон принадлежит к числу n - j типов, которые еще не встречались ранее. Таким образом, в фазе j в действительности ожидается событие с вероятностью (n - j)/n, и, согласно (13.7), ожидаемая длина фазы j равна E[X_j] = n/(n - j). ■

Используя эту формулу, получаем общее ожидаемое время.

(13.13) Ожидаемое время до сбора всех n типов купонов составляет E[X] = nH(n) = Ө(n log n).

Доказательство. Из линейности ожидания получаем

Из (13.10) следует, что эта величина асимптотически равна Ө(n log n). ■

Динамику процесса интересно сравнить с нашим интуитивным представлением о ней. После того, как будут собраны n - 1 из n типов купонов, вы ожидаете, что до появления последнего типа придется купить еще n коробок хлопьев. Вам снова и снова попадаются купоны, которые у вас уже есть, и начинает казаться, что последний тип “самый редкий”. Но на самом деле он встречается с такой же частотой, как и все остальные; просто на поиск последнего типа купона, каким бы он ни был, потребуется много времени.

Последнее определение: условное ожидание

Перейдем к последнему, очень полезному понятию, которое связано со случайными переменными и встречается при последующем анализе. По аналогии с тем, как мы определяем условную вероятность одного события при условии наступления другого, можно определить условное ожидание случайной переменной при условии наступления некоторого события. Предположим, имеется случайная переменная X и событие E с положительной вероятностью. Условное ожидание X для заданного E определяется как ожидаемое значение X, вычисленное только по части пространства выборки, соответствующей E. Обозначим эту величину E[X | E]. Для этого достаточно заменить вероятности Pr[X = j] в определении ожидания условными вероятностями: