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

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

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

Определение

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

• для каждого i значение X _i равно 0 или 1;
• для всех значений ${\textstyle 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, можно смоделировать как распределение Бернулли . Несколько случайных величин и распределений вероятностей , помимо Бернулли, могут быть получены из процесса Бернулли:

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

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

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

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

Борелевская алгебра

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

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

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

$pX(1)=P(X=1)=p$ и $pX(0)=P(X=0)=1-p$.

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

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

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

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

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

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

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

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

Закон больших чисел, биномиальное распределение и

Основные статьи: Закон больших чисел , Центральная предельная теорема и Биномиальное распределение.

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

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

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

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

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

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

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

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

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

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

$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 . Размер этого набора $2^{n}$. Из них вероятны только определенные подмножества; размер этого набора $2^{nH}$ для $H\leq 1$. Используя приближение Стирлинга, поместив его в выражение для P ( k , n ), определив местоположение и ширину пика и, наконец, взяв $n\to \infty$ человек обнаруживает, что

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

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

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

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

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

Сдвиг Бернулли

Основные статьи: схема Бернулли и диадическое преобразование

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

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

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

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

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

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

$f\circ T^{-1}$

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

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

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

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

Карта 2x mod 1

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

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

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

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

Рассмотрим теперь пространство функций из $y$. Учитывая некоторые $f(y)$ можно найти это

$\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)$

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

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

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

${\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)$

Набор Кантора

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

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

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

Одометр

Основная статья: Марковский одометр

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

В этом случае преобразование $T$ дан кем-то

$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).$

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

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

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

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

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

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

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

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

Извлечение случайности

Основная статья: Экстрактор случайности

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

Базовый экстрактор фон Неймана

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

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

Эта таблица суммирует вычисления.

вход	выход
00	отказаться
01	0
10	1
11	отказаться

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

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

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

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

если (Бит1 ≠ Бит2) {
    выход (бит1)
 }
 

Итерированный

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

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

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

вход	выход	новая последовательность 1	новая последовательность 2
00	никто	0	0
01	0	1	никто
10	1	1	никто
11	никто	0	1

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

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

номер шага	вход	выход	новая последовательность 1	новая последовательность 2
0	(10)(01)(10)(11)	(1)(0)(1)()	(1)(1)(1)(0)	()()()(1)
1	(11)(10)	()(1)	(0)(1)	(1)()
1.1	(01)	(0)	(1)	()
1.1.1	1	никто	никто	никто
1.2	1	никто	никто	никто
2	1	никто	никто	никто

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

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

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

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

Дальнейшее чтение

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

Внешние ссылки

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