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

Случайный процесс двоичных (логических) случайных величин

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

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

• 1 Определение
  • 1.1 Интерпретация
• 2 Формальное определение
  • 2.1 Алгебра Бореля
  • 2.2 Мера Бернулли
• 3 Закон больших чисел, биномиальное распределение и центральная предельная теорема
• 4 Динамические системы
  • 4.1 Сдвиг Бернулли
  • 4.2 Карта 2x mod 1
  • 4.3 Набор Кантора
  • 4.4 Одометр
• 5 Последовательность Бернулли
• 6 Извлечение случайности
  • 6.1 Базовый экстрактор фон Неймана
  • 6.2 Итерация экстрактор фон Неймана
• 7 Ссылки
• 8 Дополнительная литература
• 9 Внешние ссылки

A Процесс Бернулли - это конечная или бесконечная последовательность независимых случайных переменные X1, X 2, X 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,..., я,.... Однако это течение времени и связанные с ним понятия «прошлое» и «будущее» не являются необходимыми. В большинстве случаев любые 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\}.\; \{\backslash \; displaystyle\; 2\; =\; \backslash \; \{H,\; T\; \backslash \}.\}$

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

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

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

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

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

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

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

$П\; ([\omega \; 1,\; \omega \; 2,\; \cdots ,\; \omega \; N])\; знак\; равно\; пк\; (1\; -\; п)\; n\; -\; к\; \{\backslash \; displaystyle\; P\; ([\backslash \; omega\; \_\; \{1\},\; \backslash \; omega\; \_\; \{2\},\; \backslash \; cdots,\; \backslash \; omega\; \_\; \{n\}])\; =\; p\; ^\; \{k\}\; (1-p)\; ^\; \{nk\}\}$

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

$P\; (X\; 1\; =\; x\; 1,\; X\; 2\; =\; x\; 2,\; \cdots ,\; X\; n\; =\; xn)\; =\; pk\; (1\; -\; p)\; n\; -\; k\; \{\backslash \; displaystyle\; P\; (X\_\; \{1\}\; =\; x\_\; \{1\},\; X\_\; \{2\}\; =\; x\_\; \{2\},\; \backslash \; cdots,\; X\_\; \{n\}\; =\; x\_\; \{n\})\; =\; p\; ^\; \{k\}\; (1-p)\; ^\; \{nk\}\}$

где каждый $Икс\; i\; \{\backslash \; displaystyle\; X\_\; \{i\}\}$- это двоичная случайная величина с $xi\; =\; [\omega \; i\; =\; H]\; \{\backslash \; displaystyle\; x\_\; \{i\}\; =\; [\backslash \; omega\; \_\; \{i\}\; =\; H]\}$в записи скобок Айверсона, что означает либо $1\; \{\backslash \; displaystyle\; 1\}$, если $\omega \; я\; знак\; равно\; H\; \{\backslash \; displaystyle\; \backslash \; omega\; \_\; \{i\}\; =\; H\}$или $0\; \{\backslash \; displaystyle\; 0\}$, если $\omega \; i\; =\; T\; \{\backslash \; displaystyle\; \backslash \; омега\; \_\; \{i\}\; =\; T\}$. Эта вероятность $P\; \{\backslash \; displaystyle\; P\}$обычно называется мерой Бернулли.

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

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

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

$E\; [X\; i]\; =\; P\; ([X\; i\; =\; 1])\; =\; p,\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{E\}\; [X\_\; \{i\}]\; =\; \backslash \; mathbb\; \{P\}\; ([X\_\; \{\; i\}\; =\; 1])\; =\; p,\}$

для любой заданной случайной величины $X\; i\; \{\backslash \; displaystyle\; X\_\; \{i\}\}$из бесконечной последовательности испытаний Бернулли которые составляют процесс Бернулли.

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

$N\; (k,\; n)\; =\; (nk)\; =\; n!\; к!\; (п\; -\; к)!\; \{\backslash \; displaystyle\; N\; (k,\; n)\; =\; \{n\; \backslash \; choose\; k\}\; =\; \{\backslash \; frac\; \{n!\}\; \{k!\; (nk)!\}\}\}$

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

$P\; ([S\; n\; =\; k])\; =\; (nk)\; pk\; (1\; -\; p)\; n\; -\; k,\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{P\}\; ([S\_\; \{n\}\; =\; k])\; =\; \{n\; \backslash \; choose\; k\}\; p\; ^\; \{k\}\; (1-p)\; ^\; \{nk\},\}$

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

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

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

$n!\; Знак\; равно\; 2\; \pi \; nnne\; -\; n\; (1\; +\; O\; (1\; n))\; \{\backslash \; displaystyle\; n!\; =\; \{\backslash \; Sqrt\; \{2\; \backslash \; pi\; n\}\}\; \backslash ;\; n\; ^\; \{n\}\; e\; ^\; \{-\; n\}\; \backslash \; left\; (1+\; \{\; \backslash \; mathcal\; \{O\}\}\; \backslash \; left\; (\{\backslash \; frac\; \{1\}\; \{n\}\}\; \backslash \; right)\; \backslash \; right)\}$

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

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

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

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

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

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

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

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

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

$T\; (Икс\; 0,\; Икс\; 1,\; Икс\; 2,\; \cdots )\; =\; (Икс\; 1,\; Икс\; 2,\; \cdots )\; \{\backslash \; Displaystyle\; T\; (X\_\; \{0\},\; X\_\; \{1\},\; X\_\; \{2\},\; \backslash \; cdots)\; =\; (X\_\; \{\; 1\},\; X\_\; \{2\},\; \backslash \; cdots)\}$

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

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

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

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

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

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

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

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

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

Карта 2x mod 1

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

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

$y\; =\; \sum \; n\; =\; 0\; \infty \; бн\; 2\; п\; +\; 1.\; \{\backslash \; displaystyle\; y\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{\backslash \; infty\}\; \{\backslash \; frac\; \{b\_\; \{n\}\}\; \{2\; ^\; \{n\; +\; 1\}\}\}.\}$

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

Теперь рассмотрим пространство функций в $y\; \{\backslash \; displaystyle\; y\}$. Для некоторого $f\; (y)\; \{\backslash \; displaystyle\; f\; (y)\}$легко найти, что

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

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

$LTB\; n\; =\; 2\; -\; n\; B\; n\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{L\}\}\; \_\; \{T\}\; B\_\; \{n\}\; =\; 2\; ^\; \{-\; n\}\; B\_\; \{n\}\}$

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

$1\; 2\; B\; n\; (y\; 2)\; +\; 1\; 2\; B\; n\; (y\; +\; 1\; 2)\; =\; 2\; -\; n\; B\; n\; (y)\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{2\; \}\}\; B\_\; \{n\}\; \backslash \; left\; (\{\backslash \; frac\; \{y\}\; \{2\}\}\; \backslash \; right)\; +\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; B\_\; \{n\}\; \backslash \; left\; (\{\backslash \; frac\; \{y\; +\; 1\}\; \{2\; \}\}\; \backslash \; right)\; =\; 2\; ^\; \{-\; n\}\; B\_\; \{n\}\; (y)\}$

Множество Кантора

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

$y\; =\; \sum \; n\; =\; 0\; \infty \; bn\; 3\; n\; +\; 1\; \{\backslash \; displaystyle\; y\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{\backslash \; infty\}\; \{\backslash \; frac\; \{b\_\; \{n\}\}\; \{3\; ^\; \{n\; +\; 1\}\}\}\}$

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

Одометр

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

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

$T\; (1,\dots ,\; 1,\; 0,\; X\; k\; +\; 1,\; X\; k\; +\; 2,\dots )\; =\; (0,\dots ,\; 0,\; 1,\; X\; k\; +\; 1,\; X\; k\; +\; 2,\dots ).\; \{\backslash \; Displaystyle\; T\; \backslash \; left\; (1,\; \backslash \; точки,\; 1,0,\; X\_\; \{k\; +\; 1\},\; X\_\; \{k\; +\; 2\},\; \backslash \; dots\; \backslash \; right)\; =\; \backslash \; left\; (0,\; \backslash \; dots,\; 0,1,\; X\_\; \{\; k\; +\; 1\},\; X\_\; \{k\; +\; 2\},\; \backslash \; dots\; \backslash \; right).\}$

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

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

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

$Z\; x\; =\; \{n\; \in \; Z:\; X\; n\; (x)\; =\; 1\}\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; ^\; \{\; x\}\; =\; \backslash \; \{n\; \backslash \; in\; \backslash \; mathbb\; \{Z\}:\; X\_\; \{n\}\; (x)\; =\; 1\; \backslash \}\; \backslash ,\}$

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

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

Почти все последовательности Бернулли $Z\; x\; \{\backslash \; displaystyle\; \backslash \; 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. Это извлечение однородной случайности не требует, чтобы входные испытания были независимыми, только некоррелированными. В более общем смысле, это работает для любой заменяемой последовательности битов: все последовательности, которые являются конечными перестановками, одинаково вероятны.

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

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

if (Bit1 ≠ Bit2) {output (Bit1)}

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

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

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

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

input	output	новая последовательность 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) {output (1, Sequence1) output (Bit1)} else {output (0, Sequence1) output (Bit1, Sequence2)}

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

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

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