Зсув Бернуллі

Схема Бернуллі — це дискретний часовий стохастичний процес, де кожна незалежна випадкова величина може приймати одне з ${\displaystyle N}$ різних можливих значень, причому ${\displaystyle i}$-й результат відбувається з імовірністю ${\displaystyle p_{i}}$, при ${\displaystyle i=1,\dots ,N}$, і

${\displaystyle \sum _{i=1}^{N}p_{i}=1.}$

Простір елементарних подій як правило позначається

${\displaystyle X=\{1,\ldots ,N\}^{\mathbb {Z} }}$

як скорочення для

${\displaystyle X=\{x=(\ldots ,x_{-1},x_{0},x_{1},\ldots ):x_{k}\in \{1,\ldots ,N\}\;\forall k\in \mathbb {Z} \}.}$

Пов'язана міра називається мірою Бернуллі[6]

σ-algebra ${\displaystyle {\mathcal {A}}}$ на ${\displaystyle X}$ є добутком ${\displaystyle \sigma }$-алгебр, тобто це (скінченний) прямий добуток ${\displaystyle \sigma }$-алгебр скінченної множини ${\displaystyle \{1,\dots ,N\}}$. Таким чином, трійка

${\displaystyle (X,{\mathcal {A}},\mu )}$

є простором з мірою. Базис ${\displaystyle {\mathcal {A}}}$ є циліндричною множиною. Нехай задано циліндричну множину ${\displaystyle [x_{0},x_{1},\ldots ,x_{n}]}$, її мірою є

${\displaystyle \mu \left([x_{0},x_{1},\ldots ,x_{n}]\right)=\prod _{i=0}^{n}p_{x_{i}}.}$

Еквівалентний вираз з використанням позначень теорії ймовірностей має вигляд

${\displaystyle \mu \left([x_{0},x_{1},\ldots ,x_{n}]\right)=\mathrm {Pr} (X_{0}=x_{0},X_{1}=x_{1},\ldots ,X_{n}=x_{n})}$

для випадкових величин ${\displaystyle \{X_{k}\}}$.

Схему Бернуллі, як і будь-який стохастичний процес, можна розглядати як динамічну систему з оператором зсуву ${\displaystyle T}$, де

${\displaystyle T(x_{k})=x_{k+1}.}$

Оскільки результати незалежні, то зсув зберігає міру, і, отже, ${\displaystyle T}$ є перетворенням, що зберігає міру. Четвірка

${\displaystyle (X,{\mathcal {A}},\mu ,T)}$

є динамічною системою, що зберігає міру, і називається схемою Бернуллі або зсувом Бернуллі. Її часто позначають як

${\displaystyle BS(p)=BS(p_{1},\ldots ,p_{N}).}$

При ${\displaystyle N}$ = 2 схема Бурнуллі називається ппроцесом Бернуллі. Зсув Бернуллі можна розуміти як окремий випадок , зсуву Маркова, де всі елементи матриці сумжності одиниці. Таким чином, відповідний граф є клікою.

Відстань геммінга забезпечує природну метрику для схеми Бернуллі. Інша важлива метрика, так звана ${\displaystyle {\overline {f}}}$-метрика, визначається через супремум над відповідностями рядків[7]

Нехай ${\displaystyle A=a_{1}a_{2}\cdots a_{m}}$ і ${\displaystyle B=b_{1}b_{2}\cdots b_{n}}$ — два набори символів. Відповідність є послідовністю ${\displaystyle M}$ пар ${\displaystyle (i_{k},j_{k})}$ набору. Тобто пари для яких ${\displaystyle a_{i_{k}}=b_{j_{k}}}$, вважаються повністю впорядкованими. Кожна окрема підпослідовність ${\displaystyle i_{k}}$ і ${\displaystyle j_{k}}$ впорядковується: ${\displaystyle 1\leq i_{1}<i_{2}<\cdots <i_{r}}$, і у такий же спосіб ${\displaystyle 1\leq j_{1}<j_{2}<\cdots <j_{r}\leq n}$.

${\displaystyle {\overline {f}}}$-відстанню між ${\displaystyle A}$ і ${\displaystyle B}$ є

${\displaystyle {\overline {f}}(A,B)=1-{\frac {2\sup |M|}{m+n}},}$

де супремум беремо за усіма відповідностями ${\displaystyle M}$ між ${\displaystyle A}$ і ${\displaystyle B}$. Так означена відстань задовольняє нерівність трикутника лише при умові, що ${\displaystyle m=n,}$ і тому це не зовсім справжня метрика. Незважаючи на це, в літературі загальновживаним є термін „відстань“.

Більшість властивостей схеми Бернуллі випливають із зліченного прямого добутку, ніж з скінченного базового простору. Таким чином, можна прийняти за базовий простір стандартний простір ймовірностей ${\displaystyle (Y,{\mathcal {B}},\nu )}$ і визначити схему Бернуллі як

${\displaystyle (X,{\mathcal {A}},\mu )=(Y,{\mathcal {B}},\nu )^{\mathbb {Z} }.}$

Такий підхід є конструктивним, оскільки зліченний прямий добуток стандартного простору ймовірностей знову є стандартним простором ймовірностей.

Для іншого узагальнення можна замінити цілі числа ${\displaystyle \mathbb {Z} }$ на зліченну дискретну групу ${\displaystyle G}$. Таким чином,

${\displaystyle (X,{\mathcal {A}},\mu )=(Y,{\mathcal {B}},\nu )^{G}.}$

У цьому випадку оператор зсуву замінюється на дію групи

${\displaystyle gx(f)=x(g^{-1}f)}$

для елементів групи, ${\displaystyle f,g\in G}$ і ${\displaystyle x\in Y^{G}}$ розуміється як функція ${\displaystyle x\colon G\to Y}$ (будь-який прямий добуток ${\displaystyle Y^{G}}$ розуміємо як множину функції ${\displaystyle [G\to Y]}$, оскільки це є експоненційний об'єкт . Мiра ${\displaystyle \mu }$ вибирається як міра Хаара, яка iнварiантна пiд дiєю групи:

${\displaystyle \mu (gx)=\mu (x).\,}$

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

Яків Синай показав, що ентропія Колмогорова схеми Бернулi визначається як[8][9]

${\displaystyle H=-\sum _{i=1}^{N}p_{i}\log p_{i}.}$

Ця формула для ентропiї випливає iз загального означення ентропiї прямого декартового добутку ймовiрносних просторiв, яке випливає з властивості асимптотичного розподілу. У випадку загального базового простору ${\displaystyle (Y,{\mathcal {B}},\nu )}$ (тобто базовий простiр, який не є злiченним) зазвичай розглядається відносна ентропія. Так, наприклад, якщо маємо злiченне розбиття

${\displaystyle H_{Y'}=-\sum _{y'\in Y'}\nu (y')\log \nu (y').}$

У загальному випадку ця ентропiя залежить вiд розбиття. Однак для багатьох динамічних систем, коли символьна динаміка не залежить вiд розбиття (скорiше iснують iзоморфiзми, якi пов’язують символьну ди намiку рiзних розбиттiв i залишають мiру iнварiантною), i тому такi системи можуть мати добре визначену ентропiю, яка не залежить вiд розбиття.

Теорема про iзоморфiзм Орнштейна стверджує, що двi схеми Бернуллi з однаковою ентропiєю ізоморфні.[4] Результат є дуже особливим,[10] оскiльки для несхематичних систем таких як автоморфiзми Колмогорова не має подiбної властивостi. Теорема про iзоморфiзм насправдi набагато глибша: вона забезпечує простий критерiй, за допомогою якого багато рiзних динамічних систем, що зберігають міру, можна вважати iзоморфними схемам Бернуллi. Результат виявився неочiкуваним, оскiльки багато систем, якi ранiше вважалися непов’язаними, виявились iзоморфними. До них вiдносяться скiнченнi стацiонарнi стохастичнi процеси, пiдзсуви скiнченного типу, скiнченнi ланцюги Маркова, дифероморфiзми Аносова і бiльярди Сiная: всi вони iзоморфнi до схем Бернуллi.

У узагальненого випадку теорема про iзоморфiзм Орнштейна залишається справедливою, якщо група ${\displaystyle G}$ є злiченною нескiнченною аменабельною групою. [11][12]

Оборотне перетворення, що зберігає міру стандартного простору ймовiрностей (простiр Лебега) називають автоморфiзмами Бернуллi , якщо воно ізоморфне зсуву Бернуллі[13].

• Зсув скiнченного типу
• Ланцюги Маркова
• Прихована модель Бернуллi