Конечные вероятностные пространства
Всем нам интуитивно понятны выражения типа «Если подбросить монетку, то «орел» выпадет с вероятностью 1/2» или «При броске кубика вероятность выпадения 6 составляет 1/6». Начнем с описания математической инфраструктуры, которая позволяет точно анализировать подобные утверждения.
К счастью, в большинстве алгоритмических задач ситуация определяется так же четко, как при бросках кубиков и монеток, — разве что масштабнее и сложнее.
Чтобы иметь возможность вычислять вероятности, введем понятие конечного вероятностного пространства. (Не забывайте, что пока речь идет только о конечных множествах.) Конечное вероятностное пространство определяется нижележащим пространством выборки, которое состоит из всех возможных результатов рассматриваемого процесса.
Каждой точке пространства выборки ставится в соответствие неотрицательная вероятностная мера p(i) ≥ 0; единственное ограничение для вероятностных мер заключается в том, что их сумма должна быть равна 1, то есть.
Событие определяется как произвольное подмножество Ω (то есть просто как множество результатов, образующих это событие), а вероятность события определяется как сумма вероятностных мер всех точек в, то есть.
Во многих ситуациях, которые мы будем рассматривать, все точки пространства выборки имеют одинаковую вероятностную меру, а вероятность события вычисляется как отношение его размера к размеру Ω; то есть в этом частном случае.
Таким образом, точки в пространстве выборки и соответствующие им вероятности образуют полное описание рассматриваемой системы; мы собираемся вычислять вероятности событий — подмножеств пространства выборки. Скажем, для представления одного броска «правильной» монетки можно определить пространство выборки Ω = {heads, tails} и присвоить p(heads) = p(tails) = 1/2.
Чтобы смоделировать несимметричную монетку, в которой «орел» выпадает вдвое чаще «решки», достаточно определить вероятностные меры p(heads) = 2/3 и p(tails) = 1/3.
Даже в этом простом примере важно заметить, что определение вероятностных мер является частью задачи; мы указываем, симметрична монетка или нет, при определении условий, а не выводим это из неких дополнительных данных.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Разработка универсального класса хеш-функций
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу