сеть магазинов Harris

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Harris chain" – news · newspapers · books · scholar · JSTOR (May 2022) (Learn how and when to remove this message)

В математическом исследовании стохастических процессов цепь Харриса — это цепь Маркова , в которой цепь возвращается в определенную часть пространства состояний неограниченное число раз. ^[1] Цепи Харриса являются регенерирующими процессами и названы в честь Теодора Харриса . Теория цепей Харриса и возврата Харриса полезна для рассмотрения цепей Маркова в общих (возможно, несчетно бесконечных) пространствах состояний.

Пусть будет цепью Маркова на общем пространстве состояний со стохастическим ядром . Ядро представляет собой обобщенный одношаговый закон вероятности перехода, так что для всех состояний в и всех измеримых множеств . Цепь является цепью Харриса ^[2], если существует , и вероятностная мера с такой, что ${\displaystyle \{X_{n}\}}$${\displaystyle \Omega }$ ${\displaystyle K}$${\displaystyle P(X_{n+1}\in C\mid X_{n}=x)=K(x,C)}$${\displaystyle x}$${\displaystyle \Omega }$${\displaystyle C\subseteq \Omega }$${\displaystyle \{X_{n}\}}$${\displaystyle A\subseteq \Omega ,\varepsilon >0}$ ${\displaystyle \rho }$${\displaystyle \rho (\Omega )=1}$

1. Если , то для всех .${\displaystyle \tau _{A}:=\inf\{n\geq 0:X_{n}\in A\}}$${\displaystyle P(\tau _{A}<\infty \mid X_{0}=x)=1}$${\displaystyle x\in \Omega }$
2. Если и (где измеримо), то .${\displaystyle x\in A}$${\displaystyle C\subseteq \Omega }$${\displaystyle C}$${\displaystyle K(x,C)\geq \varepsilon \rho (C)}$

Первая часть определения гарантирует, что цепь возвращается в некоторое состояние в пределах с вероятностью 1, независимо от того, где она начинается. Из этого следует, что она посещает состояние бесконечно часто (с вероятностью 1). Вторая часть подразумевает, что как только цепь Маркова находится в состоянии , ее следующее состояние может быть сгенерировано с помощью независимого подбрасывания монеты Бернулли. Чтобы увидеть это, сначала отметим, что параметр должен находиться в диапазоне от 0 до 1 (это можно показать, применив вторую часть определения к множеству ). Теперь пусть будет точкой в ​​и предположим . Чтобы выбрать следующее состояние , независимо подбросьте смещенную монету с вероятностью успеха . Если подбрасывание монеты прошло успешно, выберите следующее состояние в соответствии с мерой вероятности . В противном случае (и если ), выберите следующее состояние в соответствии с мерой (определенной для всех измеримых подмножеств ).${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle \varepsilon }$${\displaystyle C=\Omega }$${\displaystyle x}$${\displaystyle A}$${\displaystyle X_{n}=x}$${\displaystyle X_{n+1}}$${\displaystyle \varepsilon }$${\displaystyle X_{n+1}\in \Omega }$${\displaystyle \rho }$${\displaystyle \varepsilon <1}$${\displaystyle X_{n+1}}$${\displaystyle P(X_{n+1}\in C\mid X_{n}=x)=(K(x,C)-\varepsilon \rho (C))/(1-\varepsilon )}$${\displaystyle C\subseteq \Omega }$

Два случайных процесса и , которые имеют один и тот же закон вероятности и являются цепями Харриса согласно вышеприведенному определению, могут быть связаны следующим образом: Предположим, что и , где и являются точками в . Используя одно и то же подбрасывание монеты для определения следующего состояния обоих процессов, следует, что следующие состояния будут одинаковыми с вероятностью не менее .${\displaystyle \{X_{n}\}}$${\displaystyle \{Y_{n}\}}$${\displaystyle X_{n}=x}$${\displaystyle Y_{n}=y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle A}$${\displaystyle \varepsilon }$

Пусть Ω — счетное пространство состояний. Ядро K определяется вероятностями одношагового условного перехода P[ X _{n +1} = y | X _n  =  x ] для x , y ∈ Ω. Мера ρ — это функция массы вероятности на состояниях, так что ρ ( x ) ≥ 0 для всех x ∈ Ω, а сумма вероятностей ρ (x) равна единице. Предположим, что приведенное выше определение выполняется для заданного множества A ⊆ Ω и заданного параметра ε > 0. Тогда P[ X _{n +1} = c | X _n = x ] ≥ ερ ( c ) для всех x ∈ A и всех c ∈ Ω.

Пусть { X _n },  X _n ∈ R ^d — цепь Маркова с ядром , которое абсолютно непрерывно относительно меры Лебега :

К ( х , dy ) = К ( х , y )  dy

такой, что K ( x , y ) является непрерывной функцией .

Выберем ( x ₀ ,  y ₀ ) так, что K ( x ₀ ,  y ₀ ) > 0, и пусть A и Ω будут открытыми множествами, содержащими x ₀ и y ₀ соответственно, которые достаточно малы, так что K ( x ,  y ) ≥ ε > 0 на A  × Ω. Полагая ρ ( C ) = |Ω ∩  C |/|Ω|, где |Ω| — мера Лебега Ω, мы получаем, что (2) в приведенном выше определении выполняется. Если (1) выполняется, то { X _n } является цепью Харриса.

В дальнейшем ; ie — это первый раз после момента времени 0, когда процесс входит в область . Пусть обозначает начальное распределение цепи Маркова, ie . ${\displaystyle R:=\inf\{n\geq 1:X_{n}\in A\}}$${\displaystyle R}$${\displaystyle A}$${\displaystyle \mu }$${\displaystyle X_{0}\sim \mu }$

Определение: Если для всех , , то цепь Харриса называется рекуррентной.${\displaystyle \mu }$${\displaystyle P[R<\infty |X_{0}\in A]=1}$

Определение: Рекуррентная цепь Харриса является апериодической, если , такая, что ,${\displaystyle X_{n}}$${\displaystyle \exists N}$${\displaystyle \forall n\geq N}$${\displaystyle \forall \mu ,P[X_{n}\in A|X_{0}\in A]>0}$

Теорема: Пусть — апериодическая рекуррентная цепь Харриса со стационарным распределением . Если тогда как , где обозначает полную вариацию для знаковых мер, определенных на том же измеримом пространстве.${\displaystyle X_{n}}$${\displaystyle \pi }$${\displaystyle P[R<\infty |X_{0}\in A]=1}$${\displaystyle n\rightarrow \infty }$${\displaystyle ||{\mathcal {L}}(X_{n}|X_{0})-\pi ||_{TV}\rightarrow 0}$${\displaystyle ||\cdot ||_{TV}}$