Процесс Бернулли

Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Сентябрь 2011 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В вероятности и статистике , A Бернулли процесс (названный в честь Якоба Бернулли ) представляет собой конечный или бесконечная последовательность двоичных случайных величин , так что это случайный процесс с дискретным временем , который принимает только два значения, канонические 0 и 1. Компонент Бернулли переменных X _я буду одинаково распределен и независим . Проще говоря, процесс Бернулли - это повторяющееся подбрасывание монеты , возможно, с несправедливой монетой (но с постоянной несправедливостью). Каждая переменная X _i в последовательности связана с испытанием Бернулли.или поэкспериментируйте. Все они имеют одинаковое распределение Бернулли . Многое из того, что можно сказать о процессе Бернулли, можно также обобщить на более чем два результата (например, процесс для шестигранной кости); это обобщение известно как схема Бернулли .

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

Определение [ править ]

Бернулли процесс является конечным или бесконечной последовательностью независимых случайных величин Х ₁ ,  Х ₂ ,  Х ₃ , ..., таким образом, что

• для каждого i значение X _i равно 0 или 1;
• для всех значений i вероятность p того, что X _i  = 1, одинакова.

Другими словами, процесс Бернулли - это последовательность независимых одинаково распределенных испытаний Бернулли .

Независимость испытаний подразумевает, что процесс не имеет памяти . Учитывая, что вероятность p известна, прошлые результаты не предоставляют информации о будущих результатах. (Однако, если p неизвестно, прошлое сообщает о будущем косвенно, посредством умозаключений о  p .)

Если процесс бесконечен, то с любой точки будущие испытания составляют процесс Бернулли, идентичный всему процессу, свойству «новый старт».

Интерпретация [ править ]

Два возможных значения каждого X _i часто называют «успехом» и «неудачей». Таким образом, когда результат выражается числом 0 или 1, результат можно назвать количеством успехов в i- м «испытании».

Две другие распространенные интерпретации ценностей - истина или ложь и да или нет. При любой интерпретации этих двух значений отдельные переменные X _i можно назвать испытаниями Бернулли с параметром p.

Во многих приложениях время между испытаниями проходит по мере увеличения индекса i. Фактически, испытания X ₁ ,  X ₂ , ...  X _i , ... происходят в "моменты времени" 1, 2, ...,  i , .... Этот период времени и связанные с ним понятия Однако «прошлое» и «будущее» не нужны. В большинстве случаев любые X _i и X _j в процессе - это просто два из набора случайных величин, индексированных {1, 2, ...,  n }, конечными случаями или {1, 2, 3, .. .}, бесконечные случаи.

Один эксперимент только с двумя возможными исходами, часто называемыми «успехом» и «неудачей», обычно кодируемый как 1 и 0, может быть смоделирован как распределение Бернулли . ^[1] Некоторые случайные величины и распределения вероятностей помимо Бернулли могут быть получены из процесса Бернулли:

• Количество успехов в первых n попытках, которое имеет биномиальное распределение B ( n ,  p )
• Количество неудач, необходимое для получения r успехов, которое имеет отрицательное биномиальное распределение NB ( r ,  p )
• Количество неудач, необходимое для достижения одного успеха, который имеет геометрическое распределение NB (1,  p ), частный случай отрицательного биномиального распределения.

Отрицательные биномиальные переменные можно интерпретировать как случайное время ожидания .

Формальное определение [ править ]

Процесс Бернулли можно формализовать на языке вероятностных пространств как случайную последовательность независимых реализаций случайной величины, которая может принимать значения орла или решки. Пространство состояний для отдельного значения обозначается${\displaystyle 2=\{H,T\}.}$

Борелевская алгебра [ править ]

Рассмотрим счетно бесконечное прямое произведение копий . Обычно рассматривают либо односторонний набор, либо двусторонний набор . На этом пространстве существует естественная топология , называемая топологией произведения . Множества в этой топологии являются конечными последовательностями бросков монеты, то есть конечная длина струна из Н и Т ( Н обозначает головки и Т обозначает хвосты), с остальной частью (бесконечно долго) последовательность , как принятая «Не забота". Эти наборы конечных последовательностей называются наборами цилиндров в топологии продукта. Набор всех таких строк образует${\displaystyle 2=\{H,T\}}$${\displaystyle \Omega =2^{\mathbb {N} }=\{H,T\}^{\mathbb {N} }}$${\displaystyle \Omega =2^{\mathbb {Z} }}$сигма-алгебра , в частности, борелевская алгебра . Эта алгебра затем обычно записывается как где элементы являются последовательностями подбрасывания монет конечной длины (цилиндрические множества).${\displaystyle (\Omega ,{\mathcal {B}})}$${\displaystyle {\mathcal {B}}}$

Мера Бернулли [ править ]

Если шансы выпадения орла или решки задаются вероятностями , то можно определить естественную меру в пространстве продукта, задаваемую (или для двустороннего процесса). Другими словами, если дискретная случайная величина X имеет распределение Бернулли с параметром p , где 0 ≤ p ≤ 1, и ее функция вероятностной массы определяется выражением ${\displaystyle \{p,1-p\}}$${\displaystyle P=\{p,1-p\}^{\mathbb {N} }}$${\displaystyle P=\{p,1-p\}^{\mathbb {Z} }}$

${\displaystyle pX(1)=P(X=1)=p}$и .${\displaystyle pX(0)=P(X=0)=1-p}$

Обозначим это распределение через Ber ( p ). ^[2]

Учитывая набор цилиндров, то есть определенную последовательность подбрасываний монеты временами , вероятность наблюдения этой конкретной последовательности определяется выражением ${\displaystyle [\omega _{1},\omega _{2},\cdots \omega _{n}]}$${\displaystyle 1,2,\cdots ,n}$

${\displaystyle P([\omega _{1},\omega _{2},\cdots ,\omega _{n}])=p^{k}(1-p)^{n-k}}$

где k - количество раз, которое H появляется в последовательности, а n - k - количество раз, которое T появляется в последовательности. Для вышеизложенного существует несколько различных видов обозначений; распространенный - написать

${\displaystyle P(X_{1}=x_{1},X_{2}=x_{2},\cdots ,X_{n}=x_{n})=p^{k}(1-p)^{n-k}}$

где каждая - случайная величина с двоичным значением, заключенная в скобки Айверсона , что означает либо если, либо если . Эта вероятность обычно называется мерой Бернулли . ^[3]${\displaystyle X_{i}}$${\displaystyle x_{i}=[\omega _{i}=H]}$${\displaystyle 1}$${\displaystyle \omega _{i}=H}$${\displaystyle 0}$${\displaystyle \omega _{i}=T}$${\displaystyle P}$

Обратите внимание, что вероятность любой конкретной бесконечно длинной последовательности подбрасываний монеты равна нулю; это потому , что по любому . Вероятность, равная 1, означает, что любая заданная бесконечная последовательность имеет нулевую меру . Тем не менее, можно сказать, что некоторые классы бесконечных последовательностей подбрасываний монеты гораздо более вероятны, чем другие, это дается свойством асимптотической равнораспределенности .${\displaystyle \lim _{n\to \infty }p^{n}=0}$${\displaystyle 0\leq p<1}$

Чтобы завершить формальное определение, процесс Бернулли задается тройкой вероятностей , как определено выше.${\displaystyle (\Omega ,{\mathcal {B}},P)}$

Закон больших чисел, биномиальное распределение и центральная предельная теорема [ править ]

Предположим, что канонический процесс представлен с помощью и представлен с помощью . Закон больших чисел утверждает , что, в среднем последовательности, то есть , будет приближаться к ожидаемому значению почти наверняка, то есть события , которые не удовлетворяют этот предел имеют нулевую вероятность. Среднее значение листать головок , предполагается , должны быть представлены на 1, задается . Фактически, есть${\displaystyle H}$${\displaystyle 1}$${\displaystyle T}$${\displaystyle 0}$${\displaystyle {\bar {X}}_{n}:={\frac {1}{n}}\sum _{i=1}^{n}X_{i}}$${\displaystyle p}$

${\displaystyle \mathbb {E} [X_{i}]=\mathbb {P} ([X_{i}=1])=p,}$

для любой заданной случайной величины из бесконечной последовательности испытаний Бернулли , составляющих процесс Бернулли.${\displaystyle X_{i}}$

Часто бывает интересно узнать, как часто можно наблюдать H в последовательности из n подбрасываний монеты. Это дается простым подсчетом: для заданных n последовательных подбрасываний монеты, то есть для заданного набора всех возможных строк длины n , количество N ( k , n ) таких строк, которые содержат k вхождений H , определяется биномиальным коэффициентом

${\displaystyle N(k,n)={n \choose k}={\frac {n!}{k!(n-k)!}}}$

Если вероятность перевернуть орла задана как p , то общая вероятность увидеть строку длины n с k головами равна

${\displaystyle \mathbb {P} ([S_{n}=k])={n \choose k}p^{k}(1-p)^{n-k},}$

где . Определенная таким образом вероятностная мера известна как биномиальное распределение .${\displaystyle S_{n}=\sum _{i=1}^{n}X_{i}}$

Как видно из приведенной выше формулы, если n = 1, биномиальное распределение превратится в распределение Бернулли . Таким образом, мы можем знать, что распределение Бернулли является частным случаем биномиального распределения, когда n равно 1.

Особый интерес представляет вопрос о значении для достаточно длинной последовательности подбрасываний монеты, т. Е. Для предела . В этом случае можно использовать приближение Стирлинга к факториалу и написать${\displaystyle S_{n}}$${\displaystyle n\to \infty }$

${\displaystyle n!={\sqrt {2\pi n}}\;n^{n}e^{-n}\left(1+{\mathcal {O}}\left({\frac {1}{n}}\right)\right)}$

Вставляя это в выражение для P ( k , n ), получаем нормальное распределение ; это содержание центральной предельной теоремы , и это простейший ее пример.

Сочетание закона больших чисел и центральной предельной теоремы приводит к интересному и, возможно, удивительному результату: асимптотическому свойству равнораспределения . Выражаясь неформально, можно заметить, что да, во время многих подбрасываний монеты H будет наблюдаться ровно p часть времени, и что это точно соответствует пику гауссианы. Свойство асимптотического равнораспределения по существу утверждает, что этот пик бесконечно резкий, с бесконечным спадом с обеих сторон. То есть, учитывая множество всех возможных бесконечно длинных цепочек H и Tпроисходящее в процессе Бернулли, это множество делится на два: те строки, которые встречаются с вероятностью 1, и те, которые встречаются с вероятностью 0. Это разбиение известно как закон Колмогорова 0-1 .

Размер этого множества тоже интересен, и его можно явно определить: его логарифм и есть энтропия процесса Бернулли. Еще раз рассмотрим набор всех строк длины n . Размер этого набора составляет . Из них вероятна только определенная часть; размер этого набора для . Используя приближение Стирлинга, поместив его в выражение для P ( k , n ), вычислив местоположение и ширину пика и, наконец, взяв, можно найти, что${\displaystyle 2^{n}}$${\displaystyle 2^{nH}}$${\displaystyle H\leq 1}$${\displaystyle n\to \infty }$

${\displaystyle H=-p\log _{2}p-(1-p)\log _{2}(1-p)}$

Это значение является энтропией Бернулли процесса Бернулли. Здесь H означает энтропию; не путайте его с тем же символом H, обозначающим головы .

Джон фон Нейман задал любопытный вопрос о процессе Бернулли: возможно ли, чтобы данный процесс изоморфен другому в смысле изоморфизма динамических систем ? Этот вопрос долго не поддавался анализу, но окончательный и полный ответ на него дал теорема об изоморфизме Орнштейна . Этот прорыв привел к пониманию того, что процесс Бернулли уникален и универсален ; в определенном смысле это самый случайный из возможных процессов; нет ничего более случайного, чем процесс Бернулли (хотя с этим неформальным утверждением следует быть осторожным; конечно, системы, которые смешиваютв определенном смысле «сильнее», чем процесс Бернулли, который является просто эргодическим, но не перемешивающим. Однако такие процессы не состоят из независимых случайных величин: действительно, многие чисто детерминированные, неслучайные системы могут быть перемешивающими).

Динамические системы [ править ]

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

Сдвиг Бернулли [ править ]

Один из способов создания динамической системы из процесса Бернулли - это пространство сдвига . В пространстве произведения существует естественная трансляционная симметрия, задаваемая оператором сдвига${\displaystyle \Omega =2^{\mathbb {N} }}$

${\displaystyle T(X_{0},X_{1},X_{2},\cdots )=(X_{1},X_{2},\cdots )}$

Мера Бернулли, определенная выше, инвариантна относительно трансляции; то есть для любого набора цилиндров , один имеет${\displaystyle \sigma \in {\mathcal {B}}}$

${\displaystyle P(T^{-1}(\sigma ))=P(\sigma )}$

таким образом, мера Бернулли является мерой Хаара ; это инвариантная мера в пространстве продукта.

Вместо вероятностной меры рассмотрим некоторую произвольную функцию . прямым образом${\displaystyle P:{\mathcal {B}}\to \mathbb {R} }$${\displaystyle f:{\mathcal {B}}\to \mathbb {R} }$

${\displaystyle f\circ T^{-1}}$

определяется снова некоторая функция Таким образом, отображение индуцирует другую карту на пространстве всех функций То есть, учитывая некоторые , один определяет${\displaystyle \left(f\circ T^{-1}\right)(\sigma )=f(T^{-1}(\sigma ))}$${\displaystyle {\mathcal {B}}\to \mathbb {R} .}$${\displaystyle T}$${\displaystyle {\mathcal {L}}_{T}}$${\displaystyle {\mathcal {B}}\to \mathbb {R} .}$${\displaystyle f:{\mathcal {B}}\to \mathbb {R} }$

${\displaystyle {\mathcal {L}}_{T}f=f\circ T^{-1}}$

Карта представляет собой линейный оператор , так как (очевидно) один имеет и для функций и констант . Этот линейный оператор называется передаточным оператором или оператором Рюэля – Фробениуса – Перрона . Этот оператор имеет спектр , то есть набор собственных функций и соответствующих собственных значений. Наибольшее собственное значение - это собственное значение Фробениуса – Перрона , и в данном случае оно равно 1. Соответствующий собственный вектор является инвариантной мерой: в данном случае это мера Бернулли. То есть,${\displaystyle {\mathcal {L}}_{T}}$${\displaystyle {\mathcal {L}}_{T}(f+g)={\mathcal {L}}_{T}(f)+{\mathcal {L}}_{T}(g)}$${\displaystyle {\mathcal {L}}_{T}(af)=a{\mathcal {L}}_{T}(f)}$${\displaystyle f,g}$${\displaystyle a}$${\displaystyle {\mathcal {L}}_{T}(P)=P.}$

Если ограничиться действием на многочлены, то собственные функции будут (что любопытно) многочленами Бернулли ! ^{[4] [5]} Это совпадение названий, по-видимому, не было известно Бернулли.${\displaystyle {\mathcal {L}}_{T}}$

Карта 2x mod 1 [ править ]

Отображение T  : [0,1) → [0,1) сохраняет меру Лебега .${\displaystyle x\mapsto 2x{\bmod {1}}}$

Сказанное выше можно уточнить. Учитывая бесконечную строку двоичных цифр, напишите${\displaystyle b_{0},b_{1},\cdots }$

${\displaystyle y=\sum _{n=0}^{\infty }{\frac {b_{n}}{2^{n+1}}}.}$

В результате получается действительное число в единичном интервале . Сдвиг индуцирует гомоморфизм , также называемый , на единичном интервале. Поскольку легко видеть, что это отображение называется диадическим преобразованием ; для дважды бесконечной последовательности бит индуцированный гомоморфизм является отображением Бейкера .${\displaystyle y}$${\displaystyle 0\leq y\leq 1.}$${\displaystyle T}$${\displaystyle T}$${\displaystyle T(b_{0},b_{1},b_{2},\cdots )=(b_{1},b_{2},\cdots ),}$${\displaystyle T(y)=2y{\bmod {1}}.}$${\displaystyle \Omega =2^{\mathbb {Z} },}$

Рассмотрим теперь пространство функций в . Учитывая, что кто-то может легко найти, что${\displaystyle y}$${\displaystyle f(y)}$

${\displaystyle \left[{\mathcal {L}}_{T}f\right](y)={\frac {1}{2}}f\left({\frac {y}{2}}\right)+{\frac {1}{2}}f\left({\frac {y+1}{2}}\right)}$

Ограничивая действие оператора функциями, которые находятся на многочленах, обнаруживается, что он имеет дискретный спектр, задаваемый формулой ${\displaystyle {\mathcal {L}}_{T}}$

${\displaystyle {\mathcal {L}}_{T}B_{n}=2^{-n}B_{n}}$

где - многочлены Бернулли . Действительно, полиномы Бернулли подчиняются тождеству${\displaystyle B_{n}}$

${\displaystyle {\frac {1}{2}}B_{n}\left({\frac {y}{2}}\right)+{\frac {1}{2}}B_{n}\left({\frac {y+1}{2}}\right)=2^{-n}B_{n}(y)}$

Набор Кантора [ править ]

Обратите внимание, что сумма

${\displaystyle y=\sum _{n=0}^{\infty }{\frac {b_{n}}{3^{n+1}}}}$

дает функцию Кантора , как принято определять. Это одна из причин, почему набор иногда называют набором Кантора .${\displaystyle \{H,T\}^{\mathbb {N} }}$

Одометр [ править ]

Другой способ создать динамическую систему - определить одометр . Неформально это именно то, на что это похоже: просто «добавьте единицу» к первой позиции и позвольте одометру «перевернуться», используя биты переноса, когда одометр перевернется. Это не что иное, как сложение по основанию два на множестве бесконечных строк. Поскольку сложение образует группу (математика) , а процессу Бернулли уже была задана топология, выше, это дает простой пример топологической группы .

В этом случае преобразование дается выражением${\displaystyle T}$

${\displaystyle T\left(1,\dots ,1,0,X_{k+1},X_{k+2},\dots \right)=\left(0,\dots ,0,1,X_{k+1},X_{k+2},\dots \right).}$

Он оставляет меру Бернулли инвариантной только для частного случая («честная монета»); иначе нет. Таким образом, в данном случае является мерой, сохраняющей динамическую систему, в противном случае это просто консервативная система .${\displaystyle p=1/2}$${\displaystyle T}$

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

Термин последовательность Бернулли часто используется неформально для обозначения реализации процесса Бернулли. Однако у этого термина есть совершенно иное формальное определение, приведенное ниже.

Предположим, что процесс Бернулли формально определен как единственная случайная величина (см. Предыдущий раздел). Для каждой бесконечной последовательности x подбрасываний монеты существует последовательность целых чисел

${\displaystyle \mathbb {Z} ^{x}=\{n\in \mathbb {Z} :X_{n}(x)=1\}\,}$

называется последовательностью Бернулли ^{[ требуется проверка ],} связанной с процессом Бернулли. Например, если x представляет собой последовательность подбрасываний монеты, то соответствующая последовательность Бернулли представляет собой список натуральных чисел или моментов времени, для которых результатом подбрасывания монеты является решка .

Таким образом определенная последовательность Бернулли также является случайным подмножеством набора индексов, натуральных чисел .${\displaystyle \mathbb {Z} ^{x}}$${\displaystyle \mathbb {N} }$

Почти все последовательности Бернулли являются эргодическими последовательностями . ^{[ требуется проверка ]}${\displaystyle \mathbb {Z} ^{x}}$

Извлечение случайности [ править ]

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

Базовый экстрактор фон Неймана [ править ]

Представьте наблюдаемый процесс как последовательность нулей и единиц или битов и сгруппируйте этот входной поток в неперекрывающиеся пары последовательных битов, например (11) (00) (10) .... Затем для каждой пары

• если биты равны, отбросить;
• если биты не равны, вывести первый бит.

В этой таблице приведены результаты вычислений.

Например, входной поток из восьми битов 10011011 будет сгруппирован в пары как (10) (01) (10) (11) . Затем, согласно приведенной выше таблице, эти пары транслируются в выходные данные процедуры: (1) (0) (1) () (= 101 ).

В выходном потоке 0 и 1 равновероятны, так как 10 и 01 одинаково вероятны в оригинале, причем оба имеют вероятность p (1− p ) = (1− p ) p . Это извлечение однородной случайности не требует, чтобы входные испытания были независимыми, а только некоррелированными . В более общем смысле, это работает для любой заменяемой последовательности битов: все последовательности, которые являются конечными перестановками, одинаково вероятны.

Экстрактор фон Неймана использует два входных бита для создания либо нулевого, либо одного выходных битов, поэтому выходной сигнал короче входного как минимум в 2 раза. В среднем вычисление отбрасывает долю p ²  + (1 -  p ) ² из входные пары (00 и 11), которые близки к единице, когда p близки к нулю или единице, и минимизируются на 1/4, когда p  = 1/2 для исходного процесса (в этом случае выходной поток составляет 1/4 длины входящего потока в среднем).

Псевдокод основной операции фон Неймана (классический) :

if (Bit1 ≠ Bit2) { выход (Бит1)}

Итерированный экстрактор фон Неймана [ править ]

Это снижение эффективности или растрата случайности, присутствующей во входном потоке, могут быть смягчены путем повторения алгоритма по входным данным. Таким образом, выходные данные могут быть «сколь угодно близкими к границе энтропии». ^[6]

Повторяющаяся версия алгоритма фон Неймана, также известная как Advanced Multi-Level Strategy (AMLS), ^[7] была представлена ​​Ювалем Пересом в 1992 году ^[6].Он работает рекурсивно, повторно используя «потерянную случайность» из двух источников: последовательность отбрасывания / неотбрасывания и значения отброшенных пар (0 для 00 и 1 для 11). Интуитивно он основан на том факте, что, учитывая уже сгенерированную последовательность, оба этих источника по-прежнему являются последовательностями битов, которые можно обменивать, и, таким образом, имеют право на другой раунд извлечения. Хотя такое создание дополнительных последовательностей может повторяться бесконечно для извлечения всей доступной энтропии, требуется бесконечное количество вычислительных ресурсов, поэтому количество итераций обычно фиксируется на низком значении - это значение либо фиксируется заранее, либо рассчитывается во время выполнения.

Более конкретно, во входной последовательности алгоритм использует входные биты парами, генерируя выходные данные вместе с двумя новыми последовательностями:

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

Пример: входной поток сверху, 10011011 , обрабатывается следующим образом:

Начиная с шага 1, входные данные становятся новой последовательностью1 последнего шага для продолжения этого процесса. Таким образом, на выходе получается (101) (1) (0) () () () (= 10110 ), так что из восьми битов ввода было сгенерировано пять битов вывода, в отличие от трех битов с помощью базового алгоритма выше. Постоянный выход ровно 2 бита на раунд (по сравнению с переменным от 0 до 1 бит в классической VN) также позволяет использовать реализации с постоянным временем, устойчивые к атакам по времени .

Псевдокод основной операции фон Неймана – Переса (итерация):

if (Bit1 ≠ Bit2) { вывод (1, Последовательность1) выход (Бит1)} еще { вывод (0, Последовательность1) выход (Бит1, Последовательность2)}

В 2016 году была представлена ​​еще одна настройка, основанная на наблюдении, что канал Sequence2 не обеспечивает большой пропускной способности, а аппаратная реализация с конечным числом уровней может выиграть от отказа от него раньше в обмен на обработку большего количества уровней Sequence1. ^[8]

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Карл У. Хелстром, Вероятность и случайные процессы для инженеров , (1984) Macmillan Publishing Company, Нью-Йорк ISBN 0-02-353560-1 . 

Внешние ссылки [ править ]

• Использование диаграммы двоичного дерева для описания процесса Бернулли