Harris kedja

I den matematiska studien av stokastiska processer är en Harris-kedja en Markov-kedja där kedjan återvänder till en viss del av tillståndsrummet ett obegränsat antal gånger. Harris-kedjor är regenerativa processer och är uppkallade efter Theodore Harris . Teorin om Harris-kedjor och Harris-recidiv är användbar för att behandla Markov-kedjor på allmänna (möjligen oräkneligt oändliga) tillståndsutrymmen.

Definition

Låt $\{X_{n}\}$ vara en Markov-kedja på ett allmänt tillståndsutrymme $\Omega$ med stokastisk kärna $K$ . Kärnan representerar en generaliserad övergångssannolikhetslag i ett steg, så att $P(X_{n+1}\in C\ mid X_{n}=x)=K(x,C)$ för alla tillstånd $x$ i $\Omega$ och alla mätbara mängder $C\subseteq \Omega$ . Kedjan $\{X_{n}\}$ är en Harris-kedja om det finns $A\subseteq \Omega ,\varepsilon >0$ och sannolikhetsmått $\rho$ med $\rho (\Omega )=1$ så att

1. Om ${\displaystyle \tau _{A}:=\inf\{n\geq 0:X_{n}\in A\}},$ då $P(\tau _{A}<\infty \mid X_{0}=x)=1$ för alla $x\in \Omega$ .
2. Om $x\in A$ och $C\subseteq \Omega$ (där $C$ är mätbar), då $K(x,C)\geq \varepsilon \rho (C)$ .

Den första delen av definitionen säkerställer att kedjan återgår till något tillstånd inom $A$ med sannolikhet 1, oavsett var den börjar. Det följer att det besöker tillstånd $A$ oändligt ofta (med sannolikhet 1). Den andra delen innebär att när Markov-kedjan väl är i tillstånd $A$ , kan dess nästa tillstånd genereras med hjälp av en oberoende Bernoulli-myntvändning. För att se detta, notera först att parametern $\varepsilon$ måste vara mellan 0 och 1 (detta kan visas genom att tillämpa den andra delen av definitionen på mängden $C=\Omega$ ) . Låt nu $x$ vara en punkt i $A$ och anta att $X_{n}=x$ . För att välja nästa tillstånd $X_{n+1}$ vänder du självständigt ett partiskt mynt med framgångsannolikhet $\varepsilon$ . Om myntvändningen lyckas, välj nästa tillstånd $X_{n+1}\in \Omega$ enligt sannolikhetsmåttet $\rho$ . Annars (och om $\varepsilon <1$ ), välj nästa tillstånd $X_{n+1}$ enligt måttet $P(X_{n+1}\in C\mid X_{n}=x)=(K (x,C)-\varepsilon \rho (C))/(1-\varepsilon )$ (definierad för alla mätbara delmängder ${\displaystyle C\subseteq \Omega } )$ .

Två slumpmässiga processer $\{X_{n}\}$ och $\{Y_{n}\}$ som har samma sannolikhetslag och är Harris-kedjor enligt ovanstående definition kan kopplas enligt följande: Antag att $X_{n}=x$ och $Y_{n}=y$ , där $x$ och ${\ displaystyle y}$ är punkter i $A$ . Genom att använda samma myntvändning för att bestämma nästa tillstånd för båda processerna, följer det att nästa tillstånd är desamma med sannolikhet åtminstone $\varepsilon$ .

Exempel

Exempel 1: Räknebart tillståndsutrymme

Låt Ω vara ett räknebart tillståndsrum. Kärnan K definieras av enstegs villkorad övergångssannolikhet P[ X _{n +1} = y | X _n = x ] för x , y ∈ Ω. Måttet ρ är en sannolikhetsmassfunktion på tillstånden, så att ρ ( x ) ≥ 0 för alla x ∈ Ω, och summan av ρ (x)-sannolikheterna är lika med ett. Antag att definitionen ovan är uppfylld för en given mängd A ⊆ Ω och en given parameter ε > 0. Då P[ X _{n +1} = c | X _n = x ] ≥ ερ ( c ) för alla x ∈ A och alla c ∈ Ω.

Exempel 2: Kedjor med kontinuerliga densiteter

Låt { X _n }, X _n ∈ R ^d vara en Markov-kedja med en kärna som är absolut kontinuerlig med avseende på Lebesgue-måttet :

K ( x , dy ) = K ( x , y ) dy

så att K ( x , y ) är en kontinuerlig funktion .

₀₀₀₀₀₀ Välj ( x , y ) så att K ( x , y ) > 0, och låt A och Ω vara öppna mängder som innehåller x respektive y som är tillräckligt små så att K ( x , y ) ≥ ε > 0 på A × Ω . Låter ρ ( C ) = |Ω ∩ C |/|Ω| där |Ω| är Lebesgue-måttet på Ω, har vi att (2) i definitionen ovan gäller. Om (1) gäller är { X _n } en Harris-kedja.

Reducerbarhet och periodicitet

I följande $R:=\inf\{n\geq 1:X_{n}\in A\}$ ; dvs $R$ är första gången efter tid 0 som processen går in i region $A$ . Låt $\mu$ beteckna den initiala fördelningen av Markov-kedjan, dvs $X_{0}\sim \mu$ .

Definition: Om för alla $\mu$ , ${\displaystyle P[R<\infty |X_{0}\in A]=1} ,$ då kallas Harris-kedjan återkommande.

Definition: En återkommande Harris-kedja $X_{n}$ är aperiodisk om $\exists N$ , så att $\forall n\geq N$ , $\forall \mu ,P[X_{n}\in A|X_{0}\in A]>0$

Sats: Låt $X_{n}$ vara en aperiodisk återkommande Harris-kedja med stationär fördelning $\pi$ . Om $P[R<\infty |X_{0}\in A]=1$ sedan som $n\rightarrow \infty$ , $||{\mathcal {L}}(X_{n}|X_{0})-\pi ||_{TV}\högerpil 0$ där $||\cdot ||_{TV}$ anger den totala variationen för signerade mått definierade på samma mätbara utrymme.