В вероятности и статистике , A Бернулли процесс (названный в честь Якоба Бернулли ) представляет собой конечный или бесконечная последовательность двоичных случайных величин , так что это случайный процесс с дискретным временем , который принимает только два значения, канонические 0 и 1. Компонент Бернулли переменных X я буду одинаково распределен и независим . Проще говоря, процесс Бернулли - это повторяющееся подбрасывание монеты , возможно, с несправедливой монетой (но с постоянной несправедливостью). Каждая переменная X i в последовательности связана с испытанием Бернулли.или поэкспериментируйте. Все они имеют одинаковое распределение Бернулли . Многое из того, что можно сказать о процессе Бернулли, можно также обобщить на более чем два результата (например, процесс для шестигранной кости); это обобщение известно как схема Бернулли .
Проблема определения процесса, учитывая лишь ограниченную выборку испытаний Бернулли, может быть названа проблемой проверки честности монеты .
Определение
Бернулли процесс является конечным или бесконечной последовательностью независимых случайных величин Х 1 , Х 2 , Х 3 , ..., таким образом, что
- для каждого i значение X i равно 0 или 1;
- для всех значений i вероятность p того, что X i = 1, одинакова.
Другими словами, процесс Бернулли - это последовательность независимых одинаково распределенных испытаний Бернулли .
Независимость испытаний подразумевает, что процесс не имеет памяти . Учитывая, что вероятность p известна, прошлые результаты не предоставляют информации о будущих результатах. (Однако, если p неизвестно, прошлое сообщает о будущем косвенно, посредством умозаключений о p .)
Если процесс бесконечен, то с любой точки будущие испытания составляют процесс Бернулли, идентичный всему процессу, свойству «новый старт».
Интерпретация
Два возможных значения каждого X i часто называют «успехом» и «неудачей». Таким образом, когда результат выражается числом 0 или 1, результат можно назвать количеством успехов в i- м «испытании».
Две другие распространенные интерпретации ценностей - истина или ложь и да или нет. При любой интерпретации этих двух значений отдельные переменные X i можно назвать испытаниями Бернулли с параметром p.
Во многих приложениях время между испытаниями проходит по мере увеличения индекса i. Фактически, испытания X 1 , X 2 , ... 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 ), частный случай отрицательного биномиального распределения.
Отрицательные биномиальные переменные можно интерпретировать как случайное время ожидания .
Формальное определение
Процесс Бернулли можно формализовать на языке вероятностных пространств как случайную последовательность независимых реализаций случайной величины, которая может принимать значения орла или решки. Пространство состояний для отдельного значения обозначается
Борелевская алгебра
Рассмотрим счетно бесконечное прямое произведение копий. Обычно рассматривают либо односторонний набор или двусторонний набор . На этом пространстве существует естественная топология , называемая топологией произведения . Множества в этой топологии являются конечными последовательностями бросков монеты, то есть конечная длина струна из Н и Т ( Н обозначает головки и Т обозначает хвосты), с остальной частью (бесконечно долго) последовательность , как принятая «Не забота". Эти наборы конечных последовательностей называются наборами цилиндров в топологии продукта. Набор всех таких цепочек образует сигма-алгебру , в частности, борелевскую алгебру . Затем эту алгебру обычно записывают как где элементы - последовательности подбрасываний монеты конечной длины (цилиндрические множества).
Мера Бернулли
Если шансы перевернуть орел или решку заданы вероятностями , то можно определить естественную меру на пространстве продуктов, задаваемую формулой (или для двустороннего процесса). Другими словами, если дискретная случайная величина X имеет распределение Бернулли с параметром p , где 0 ≤ p ≤ 1, и ее функция вероятностной массы определяется выражением
- а также .
Обозначим это распределение через Ber ( p ). [2]
Учитывая набор цилиндров, то есть определенную последовательность результатов подбрасывания монеты во время , вероятность наблюдения этой конкретной последовательности определяется выражением
где k - количество раз, которое H появляется в последовательности, а n - k - количество раз, которое T появляется в последовательности. Для вышеизложенного существует несколько различных видов обозначений; распространенный - написать
где каждый является двоичной случайной величиной св скобках Айверсона , что означает либо если или же если . Эта вероятностьобычно называется мерой Бернулли . [3]
Обратите внимание, что вероятность любой конкретной бесконечно длинной последовательности подбрасываний монеты равна нулю; это потому что, для любой . Вероятность, равная 1, означает, что любая заданная бесконечная последовательность имеет нулевую меру . Тем не менее, можно сказать, что некоторые классы бесконечных последовательностей подбрасываний монеты гораздо более вероятны, чем другие, это обеспечивается свойством асимптотической равнораспределенности .
В заключение формального определения, процесс Бернулли задается тройкой вероятностей , как определено выше.
Закон больших чисел, биномиальное распределение и центральная предельная теорема
Допустим, канонический процесс с представлена а также представлена . Закон больших чисел утверждает , что, в среднем последовательности, т.е., почти наверняка приблизится к ожидаемому значению , то есть события, которые не удовлетворяют этому пределу, имеют нулевую вероятность. Среднее значение листать головы , предполагается , должны быть представлены на 1, задается. Фактически, есть
для любой заданной случайной величины из бесконечной последовательности испытаний Бернулли , составляющих процесс Бернулли.
Часто бывает интересно узнать, как часто можно наблюдать H в последовательности из n подбрасываний монеты. Это дается простым подсчетом: для заданных n последовательных подбрасываний монеты, то есть для заданного набора всех возможных строк длины n , количество N ( k , n ) таких строк, которые содержат k вхождений H , определяется биномиальным коэффициентом
Если вероятность перевернуть орла задана как p , то общая вероятность увидеть строку длины n с k головами равна
где . Определенная таким образом вероятностная мера известна как биномиальное распределение .
Как видно из приведенной выше формулы, если n = 1, биномиальное распределение превратится в распределение Бернулли . Таким образом, мы можем знать, что распределение Бернулли является частным случаем биномиального распределения, когда n равно 1.
Особый интерес представляет вопрос о стоимости для достаточно длинной последовательности подбрасываний монеты, т. е. для предела . В этом случае можно использовать приближение Стирлинга к факториалу и написать
Вставляя это в выражение для P ( k , n ), получаем нормальное распределение ; это содержание центральной предельной теоремы , и это простейший ее пример.
Сочетание закона больших чисел и центральной предельной теоремы приводит к интересному и, возможно, удивительному результату: асимптотическому свойству равнораспределения . Выражаясь неформально, можно заметить, что да, во время многих подбрасываний монеты H будет наблюдаться ровно p часть времени, и что это точно соответствует пику гауссианы. Свойство асимптотического равнораспределения по существу утверждает, что этот пик бесконечно резкий, с бесконечным спадом с обеих сторон. То есть, учитывая набор всех возможных бесконечно длинных строк H и T, встречающихся в процессе Бернулли, этот набор делится на две части: те строки, которые встречаются с вероятностью 1, и те, которые встречаются с вероятностью 0. Это разбиение известно как Колмогорова 0-1 закона .
Размер этого множества тоже интересен, и его можно явно определить: его логарифм и есть энтропия процесса Бернулли. Еще раз рассмотрим набор всех строк длины n . Размер этого набора. Из них вероятна только определенная часть; размер этого набора для . Используя приближение Стирлинга, поместив его в выражение для P ( k , n ), определив местоположение и ширину пика и, наконец, взяв каждый обнаруживает, что
Это значение является энтропией Бернулли процесса Бернулли. Здесь H означает энтропию; не путайте его с тем же символом H, обозначающим головы .
Джон фон Нейман задал любопытный вопрос о процессе Бернулли: возможно ли, чтобы данный процесс изоморфен другому в смысле изоморфизма динамических систем ? Этот вопрос долго не поддавался анализу, но окончательный и полный ответ на него дал теорема об изоморфизме Орнштейна . Этот прорыв привел к пониманию того, что процесс Бернулли уникален и универсален ; в определенном смысле это самый случайный из возможных процессов; нет ничего «более» случайного, чем процесс Бернулли (хотя с этим неформальным утверждением следует быть осторожнее; конечно, смешивающие системы в определенном смысле «сильнее», чем процесс Бернулли, который является просто эргодическим, но не смешивающим. Однако такие процессы не состоят из независимых случайных величин: действительно, многие чисто детерминированные, неслучайные системы могут быть перемешивающими.
Динамические системы
Процесс Бернулли также можно понимать как динамическую систему , как пример эргодической системы и, в частности, как динамическую систему , сохраняющую меру , одним из нескольких различных способов. Один способ - как сдвиг , а другой - как одометр . Они рассматриваются ниже.
Сдвиг Бернулли
Один из способов создания динамической системы из процесса Бернулли - это пространство сдвига . На пространстве продукта существует естественная симметрия трансляции.заданный оператором сдвига
Мера Бернулли, определенная выше, инвариантна относительно трансляции; то есть для любого набора цилиндров, надо
таким образом, мера Бернулли является мерой Хаара ; это инвариантная мера в пространстве продукта.
Вместо вероятностной меры рассмотрим вместо этого некоторую произвольную функцию . прямым образом
определяется это снова какая-то функция Таким образом, карта вызывает другую карту на пространстве всех функций То есть, учитывая некоторые , один определяет
Карта является линейным оператором , так как (очевидно) а также для функций и постоянный . Этот линейный оператор называется передаточным оператором или оператором Рюэля – Фробениуса – Перрона . Этот оператор имеет спектр , то есть набор собственных функций и соответствующих собственных значений. Наибольшее собственное значение - это собственное значение Фробениуса – Перрона , и в данном случае оно равно 1. Соответствующий собственный вектор является инвариантной мерой: в данном случае это мера Бернулли. Это,
Если кто-то ограничивает чтобы действовать на многочлены, то собственные функции (что любопытно) являются многочленами Бернулли ! [4] [5] Это совпадение названий, по-видимому, не было известно Бернулли.
Карта 2x mod 1
Сказанное выше можно уточнить. Учитывая бесконечную строку двоичных цифр написать
Результирующий это действительное число в единичном интервале Смена индуцирует гомоморфизм , также называемый, на единичном интервале. С легко увидеть, что Эта карта называется диадическим преобразованием ; для дважды бесконечной последовательности битиндуцированный гомоморфизм - это отображение Бейкера .
Рассмотрим теперь пространство функций из . Учитывая некоторые можно легко найти, что
Ограничение действия оператора к функциям, которые находятся на многочленах, обнаруживается, что он имеет дискретный спектр, задаваемый формулой
где - многочлены Бернулли . Действительно, полиномы Бернулли подчиняются тождеству
Набор Кантора
Обратите внимание, что сумма
дает функцию Кантора , как принято определять. Это одна из причин, по которой набориногда называют множеством Кантора .
Одометр
Другой способ создать динамическую систему - определить одометр . Неформально это именно то, на что это похоже: просто «добавьте единицу» к первой позиции и позвольте одометру «перевернуться», используя биты переноса, когда одометр перевернется. Это не что иное, как сложение по основанию два на множестве бесконечных строк. Поскольку сложение образует группу (математика) , а процессу Бернулли уже была задана топология, выше, это дает простой пример топологической группы .
В этом случае преобразование дан кем-то
Он оставляет меру Бернулли инвариантной только для частного случая («честная монета»); иначе нет. Таким образом,в этом случае является динамической системой, сохраняющей меру , в противном случае это просто консервативная система .
Последовательность Бернулли
Термин последовательность Бернулли часто используется неформально для обозначения реализации процесса Бернулли. Однако у этого термина есть совершенно иное формальное определение, приведенное ниже.
Предположим, что процесс Бернулли формально определен как единственная случайная величина (см. Предыдущий раздел). Для каждой бесконечной последовательности x подбрасываний монеты существует последовательность целых чисел
называется последовательностью Бернулли [ требуется проверка ], связанной с процессом Бернулли. Например, если 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 . Это извлечение однородной случайности не требует, чтобы входные испытания были независимыми, а только некоррелированными . В более общем плане он работает для любой заменяемой последовательности битов: все последовательности, которые являются конечными перестановками, одинаково вероятны.
Экстрактор фон Неймана использует два входных бита для создания либо нулевого, либо одного выходных битов, поэтому выходной сигнал короче входного как минимум в два раза. В среднем вычисление отбрасывает долю p 2 + (1 - p ) 2 из входные пары (00 и 11), которые близки к единице, когда p близки к нулю или единице, и минимизируются на 1/4, когда p = 1/2 для исходного процесса (в этом случае выходной поток составляет 1/4 длины входящего потока в среднем).
Псевдокод основной операции фон Неймана (классический) :
if (Bit1 ≠ Bit2) { выход (Бит1)}
Итерированный экстрактор фон Неймана
Это снижение эффективности или растрата случайности, присутствующей во входном потоке, могут быть смягчены путем повторения алгоритма по входным данным. Таким образом, выходные данные могут быть «сколь угодно близкими к границе энтропии». [6]
Повторяющаяся версия алгоритма фон Неймана, также известная как Расширенная многоуровневая стратегия (AMLS), [7] была представлена Ювалем Пересом в 1992 году. [6] Она работает рекурсивно, перерабатывая «бесполезную случайность» из двух источников: последовательности. of discard / non-discard, и значения отброшенных пар (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) также позволяет использовать реализации с постоянным временем, устойчивые к атакам по времени .
Псевдокод основной операции фон Неймана – Переса (итерация):
if (Bit1 ≠ Bit2) { вывод (1, Последовательность1) выход (Бит1)} еще { вывод (0, Последовательность1) выход (Бит1, Последовательность2)}
В 2016 году была представлена еще одна настройка, основанная на наблюдении, что канал Sequence2 не обеспечивает большой пропускной способности, а аппаратная реализация с конечным числом уровней может выиграть от отказа от него раньше в обмен на обработку большего количества уровней Sequence1. [8]
Рекомендации
- ^ Деккинг, FM; Kraaikamp, C .; Лопухаа, HP; Мистер, Л. Е. (2005). Современное введение в вероятность и статистику . С. 45–46. ISBN 9781852338961.
- ^ Деккинг, FM; Kraaikamp, C .; Лопухаа, HP; Мистер, Л. Е. (2005). Современное введение в вероятность и статистику . С. 45–46. ISBN 9781852338961.
- ^ Кленке, Ахим (2006). Теория вероятностей . Springer-Verlag. ISBN 978-1-84800-047-6.
- ^ Пьер Гаспар, " r -адические одномерные отображения и формула суммирования Эйлера", Journal of Physics A , 25 (письмо) L483-L485 (1992).
- ^ Dean J. Driebe, Полностью хаотические Карты и Сломанный Время Symmetry (1999) Kluwer Academic Publishers, Dordrecht Нидерланды ISBN 0-7923-5564-4
- ^ а б Перес, Юваль (март 1992 г.). «Итерация процедуры фон Неймана для извлечения случайных битов» (PDF) . Летопись статистики . 20 (1): 590–597. DOI : 10.1214 / AOS / 1176348543 . Архивировано из оригинального (PDF) 18 мая 2013 года . Проверено 30 мая 2013 года .
- ^ «Подбрасывание необъективной монеты» (PDF) . eecs.harvard.edu . Проверено 28 июля 2018 .
- ^ Рожич, Владимир; Ян, Бохан; Дехайн, Вим; Verbauwhede, Ингрид (3–5 мая 2016 г.). Итерация постобработки фон Неймана при аппаратных ограничениях (PDF) . Международный симпозиум IEEE по безопасности и доверию, ориентированный на оборудование, 2016 г. (HOST). Маклин, Вирджиния, США. DOI : 10,1109 / HST.2016.7495553 .
дальнейшее чтение
- Карл В. Хелстром, Вероятность и случайные процессы для инженеров , (1984) Macmillan Publishing Company, Нью-Йорк. ISBN 0-02-353560-1 .
Внешние ссылки
- Использование диаграммы двоичного дерева для описания процесса Бернулли