<<
>>

Случайные переменные и ожидания

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

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

о вероятности того, что X примет заданное значение, которое рассматривается как значение «случайной переменной».

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

ВД = ∑у'∙Рr[х = /Ь

7=0

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

Е\Х] = lp/л)+ го⅛) +...+ «(1 fп) = И^l|/и=(n+I)/2.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Случайные переменные и ожидания:

  1. Статья 772. Риск случайного уничтожения или случайного повреждения вещи
  2. Статья 323. Риск случайного уничтожения и случайного повреждения имущества
  3. Статья 580. Риск случайного уничтожения или случайного повреждения предмета залога
  4. Статья 668. Переход риска случайного уничтожения или случайного повреждения товара
  5. Статья 880. Риск случайного уничтожения или случайного повреждения объекта
  6. Статья 842. Риск случайного уничтожения или случайного повреждения материала
  7. Статья 809. Риск случайного уничтожения или случайного повреждения предмета договора лизинга
  8. Статья 742. Риск случайного уничтожения или случайного повреждения имущества, переданного под выплату бессрочной ренты
  9. Статья 743. Риск случайного уничтожения или случайного повреждения имущества, переданного под выплату ренты на определенный срок
  10. ПЕРЕМЕННАЯ ПРОМЕЖУТОЧНАЯ
  11. ПЕРЕМЕННАЯ
  12. ПЕРЕМЕННАЯ ЗАВИСИМАЯ
  13. ПЕРЕМЕННАЯ НЕЗАВИСИМАЯ
  14. Пять переменных У. Мичела.
  15. ПЕРЕМЕННАЯ КОНТРОЛИРУЕМАЯ
  16. Сопротивление переменам в нас