Введение

Случайный процесс бинарных (булевых) случайных переменных.

В теории вероятностей и статистике процесс Бернулли (названный в честь Якоба Бернулли) представляет собой конечную или бесконечную последовательность бинарных случайных переменных, то есть дискретный стохастический процесс, принимающий только два значения, обычно 0 и 1. Компоненты, случайные величины Бернулли Xi, имеют одинаковое распределение и независимы друг от друга. Если говорить простым языком, процесс Бернулли – это многократное подбрасывание монеты, возможно, несбалансированной (но с постоянной степенью несбалансированности). Каждая случайная величина Xi в последовательности соответствует испытанию или эксперименту Бернулли. Все они подчиняются одному и тому же распределению Бернулли. Многие свойства процесса Бернулли могут быть обобщены на случай более чем двух возможных исходов (например, для шестигранного кубика); такое обобщение известно как схема Бернулли. Задача определения параметров процесса на основе ограниченной выборки испытаний Бернулли может быть сформулирована как задача проверки честности монеты.

Формальное определение

Процесс Бернулли может быть формализован на языке вероятностных пространств как случайная последовательность независимых реализаций случайной величины, которая может принимать значения "орёл" или "решка". Пространство состояний для отдельного значения обозначается

Алгебра Бореля

Рассмотрим счетно бесконечное прямое произведение копий . Обычно исследуют либо одностороннее множество , либо двухстороннее множество . На этом пространстве существует естественная топология, называемая топологией произведения. Множества в этой топологии представляют собой конечные последовательности подбрасываний монеты, то есть строки конечной длины, состоящие из символов H и T (H обозначает "орёл", а T - "решка"), при этом оставшаяся (бесконечно длинная) часть последовательности считается "не имеющей значения". Эти множества конечных последовательностей называются цилиндрическими множествами в топологии произведения. Множество всех таких строк образует сигма-алгебру, в частности, алгебру Бореля. Эта алгебра обычно записывается как , где элементы являются конечными последовательностями подбрасываний монеты (цилиндрическими множествами).

Меры Бернулли

Если вероятности выпадения орла или решки заданы вероятностями , то можно определить естественную меру на пространстве произведений, заданную (или для двустороннего процесса). Иными словами, если дискретная случайная величина X имеет распределение Бернулли с параметром p, где 0 ≤ p ≤ 1, и ее функция массы вероятности задается как

и

Мы обозначаем это распределение как Ber(p). Следует отметить, что вероятность любой конкретной, бесконечно длинной последовательности подбрасываний монеты равна точно нулю; это связано с тем, что , для любого множества A вероятность, равная 1, подразумевает, что любая заданная бесконечная последовательность имеет меру нуль. Тем не менее, можно утверждать, что некоторые классы бесконечных последовательностей подбрасываний монеты гораздо более вероятны, чем другие, что описывается асимптотическим свойством равнораспределенности. В заключение, формальное определение процесса Бернулли задается тройкой вероятностей , как определено выше.

Динамические системы

Процесс Бернулли также можно рассматривать как динамическую систему, являющуюся примером эргодической системы и, в частности, динамической системы, сохраняющей меру, одним из нескольких различных подходов. Один из них – представление в виде пространства сдвигов, а другой – в виде одометра. Они рассмотрены ниже.

Последовательность Бернулли

Термин "последовательность Бернулли" часто неформально используется для обозначения реализации процесса Бернулли. Однако этот термин имеет совершенно иное формальное определение, приведенное ниже. Пусть процесс Бернулли формально определен как одна случайная величина (см. предыдущий раздел). Для каждой бесконечной последовательности x результатов подбрасывания монеты существует последовательность целых чисел, называемая последовательностью Бернулли, связанной с этим процессом Бернулли. Например, если x представляет собой последовательность подбрасываний монеты, то связанная последовательность Бернулли – это список натуральных чисел или моментов времени, в которые выпала решка. Таким образом определенная последовательность Бернулли также является случайным подмножеством множества индексов, то есть натуральных чисел. Почти все последовательности Бернулли являются эргодическими последовательностями.

Выделение случайности

Из любого процесса Бернулли можно получить процесс Бернулли с p = 1/2 с помощью экстрактора фон Неймана — старейшего извлекателя случайности, который действительно генерирует равномерно распределённую случайность.

Итерационный экстрактор фон Неймана

Это снижение эффективности, или потеря случайности в исходном потоке данных, может быть уменьшено путем повторного применения алгоритма к входным данным. Таким образом, выходные данные могут быть сделаны "произвольно близкими к теоретическому пределу энтропии". Итерационная версия алгоритма фон Неймана, также известная как расширенная многоуровневая стратегия (AMLS), была предложена Ювалом Пересом в 1992 году.