guide:294efc642d: Difference between revisions
No edit summary |
No edit summary |
||
Line 1: | Line 1: | ||
<div class="d-none"><math> | |||
\newcommand{\R}{\mathbb{R}} | |||
\newcommand{\A}{\mathcal{A}} | |||
\newcommand{\B}{\mathcal{B}} | |||
\newcommand{\N}{\mathbb{N}} | |||
\newcommand{\C}{\mathbb{C}} | |||
\newcommand{\Rbar}{\overline{\mathbb{R}}} | |||
\newcommand{\Bbar}{\overline{\mathcal{B}}} | |||
\newcommand{\Q}{\mathbb{Q}} | |||
\newcommand{\E}{\mathbb{E}} | |||
\newcommand{\p}{\mathbb{P}} | |||
\newcommand{\one}{\mathds{1}} | |||
\newcommand{\0}{\mathcal{O}} | |||
\newcommand{\mat}{\textnormal{Mat}} | |||
\newcommand{\sign}{\textnormal{sign}} | |||
\newcommand{\CP}{\mathcal{P}} | |||
\newcommand{\CT}{\mathcal{T}} | |||
\newcommand{\CY}{\mathcal{Y}} | |||
\newcommand{\F}{\mathcal{F}} | |||
\newcommand{\mathds}{\mathbb}</math></div> | |||
From now on we will only use the canonical Markov chain. Recall that for <math>x\in E</math> we have | |||
<math display="block"> | |||
\begin{align*} | |||
H_x&=\inf\{n\geq 1\mid X_n=x\},\\ | |||
N_x&=\sum_{n\geq 0}\one_{\{ X_n=x\}}. | |||
\end{align*} | |||
</math> | |||
{{proofcard|Proposition (Recurrence and Transience)|prop-1|Let <math>x\in E</math>. Then we have two situations, which can occur. | |||
<ul style{{=}}"list-style-type:lower-roman"><li><math>\p_x[H_x < \infty]=1</math> and <math>N_x=\infty</math> <math>\p_x</math>-a.s. In this case <math>x</math> is said to be reccurrent. | |||
</li> | |||
<li><math>\p_x[H_x < \infty] < 1</math> and <math>N_x < \infty</math> <math>\p_x</math>-a.s. More precisely | |||
<math display="block"> | |||
\E_x[N_x]=\frac{1}{\p_x[H_x < \infty]} < \infty. | |||
</math> | |||
In this case <math>x</math> is said to be transient. | |||
</li> | |||
</ul> | |||
|For <math>k\geq 1</math>, it follows from the strong Markov property that | |||
<math display="block"> | |||
\p_x[N_x\geq k+1]=\E_x[\one_{H_x < \infty}\one_{N_x\geq k}\circ \Theta_{H_x}]=\E_x[\one_{H_x < \infty}\E_x[\one_{N_x\geq k}]]=\p_x[H_x < \infty]\p_x[N_x\geq k]. | |||
</math> | |||
Now since <math>\p_x[N_x\geq 1]=1</math>, it follows by induction that | |||
<math display="block"> | |||
\p_x[N_x\geq k]=\p_x[H_x < \infty]^{k-1}. | |||
</math> | |||
If <math>\p_x[H_x < \infty]=1</math>, then <math>\p_x[N_x=\infty]=1</math>. If <math>\p_x[H_x < \infty] < 1</math>, then | |||
<math display="block"> | |||
\E_x[N_x]=\sum_{k\geq 1}\p_x[N_x\geq k]=\sum_{k\geq 1}\p_x[H_x < \infty]^{k-1}=\frac{1}{1-\p_x[H_x < \infty]}=\frac{1}{\p_x[H_x < \infty]} < \infty | |||
</math>}} | |||
{{definitioncard|Potential kernel| | |||
The potential kernel of the chain is given by the function | |||
<math display="block"> | |||
U:E\times E\to [0,\infty],(x,y)\mapsto \E_x[N_y]. | |||
</math> | |||
}} | |||
{{proofcard|Proposition|prop-2|The following hold. | |||
<ul style{{=}}"list-style-type:lower-roman"><li>For all <math>x,y\in E</math> we have | |||
<math display="block"> | |||
U(x,y)=\sum_{n\geq 0}Q_n(x,y). | |||
</math> | |||
</li> | |||
<li><math>U(x,x)=\infty</math> if and only if <math>x</math> is recurrent. | |||
</li> | |||
<li>For all <math>x,y\in E</math> it follows that if <math>x\not=y</math> then | |||
<math display="block"> | |||
U(x,y)=\p_x[H_y < \infty]U(y,y). | |||
</math> | |||
</li> | |||
</ul> | |||
|We need to show all three points. | |||
<ul style{{=}}"list-style-type:lower-roman"><li>Note that | |||
<math display="block"> | |||
U(x,y)=\E_x\left[\sum_{n\geq 0}\one_{\{N_x=y\}}\right]=\sum_{n\geq 0}\p_x[X_n=y]=\sum_{n\geq 0}Q_n(x,y). | |||
</math> | |||
</li> | |||
<li>Exercise. | |||
</li> | |||
<li>This follows from the strong Markov property. We get | |||
<math display="block"> | |||
\E_x[N_y]=\E_x[\one_{\{H_y < \infty\}}N_y\circ\Theta_{H_y}]=\E_x[\one_{\{H_y < \infty\}}\E_y[N_y]]=\p_x[H_y < \infty]U(y,y). | |||
</math> | |||
</li> | |||
</ul>}} | |||
'''Example''' | |||
Let us consider the Markov chain, starting at 0, on <math>\mathbb{Z}^d</math> with transition matrix given by | |||
<math display="block"> | |||
Q((x_1,...,x_d),(y_1,...,y_d))=\frac{1}{2^d}\prod_{i=1}^d\one_{\{\vert y_i-x_i\vert=1\}}. | |||
</math> | |||
This Markov chain has the same distribution as <math>(Y_n^1,...,Y_n^d)_{n\geq 0}</math>, where <math>Y^1,...,Y^d</math> are iid r.v.'s of a simple random walk on <math>\mathbb{Z}</math>, starting at 0. Hence we get | |||
<math display="block"> | |||
Q_n(0,0)=\p[Y_n^1=0,...,Y_n^d=0]=\p[Y_n^1=0]^d. | |||
</math> | |||
Moreover, <math>\p[Y_n^1=0]=0</math> if <math>n</math> is odd and for <math>n=2k</math> we get | |||
<math display="block"> | |||
\p[Y_{2k}^1=0]=2^{-2k}\binom{2k}{k}. | |||
</math> | |||
Therefore we get that | |||
<math display="block"> | |||
U(0,0)=\sum_{k\geq 0}Q_{2k}(0,0)=\sum_{k\geq 0}\left(2^{-2k}\binom{2k}{k}\right)^d. | |||
</math> | |||
Now with Stirling's formula{{efn|Recall that <math>n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n</math>}} we get | |||
<math display="block"> | |||
2^{-2k}\binom{2k}{k}\approx_{k\to\infty}\frac{\left(\frac{2k}{e}\right)^{2k}\sqrt{4\pi k}}{2^{2k}\left(\left(\frac{k}{e}\right)^k\sqrt{2\pi k}\right)^2}\approx_{k\to\infty}\sqrt{\frac{1}{\pi k}}. | |||
</math> | |||
Consequently, 0 is recurrent if <math>d=1</math> and transient if <math>d\geq 2</math>. | |||
Now let us denote the set of all recurrent points by <math>R</math>. Then we can obtain the following lemma. | |||
{{proofcard|Lemma|lem-1|Let <math>x\in R</math> and let <math>y\in E</math> such that <math>U(x,y) > 0</math>. Then <math>y\in R</math> and | |||
<math display="block"> | |||
\p_y[H_x < \infty]=1. | |||
</math> | |||
In particular we get that <math>U(y,x) > 0</math>. | |||
|Let us first show that <math>\p_y[H_x < \infty]=1</math>. We have that | |||
<math display="block"> | |||
\begin{multline*} | |||
0=\p_x[N_x < \infty]\geq \p_x[H_y < \infty, H_x\circ\Theta_{H_y}=\infty]=\E_x[\one_{\{H_y < \infty\}}\one_{\{H_x=\infty\}}\circ\Theta_{H_y}]\\=\E_x[\one_{\{H_y < \infty\}}\p_y[H_x=\infty]]=\p_x[H_y < \infty]\p_y[H_x=\infty]. | |||
\end{multline*} | |||
</math> | |||
Then <math>U(x,y) > 0</math> implies that <math>\p_x[H_y < \infty] > 0</math> and thus <math>\p_y[H_x=\infty]=0</math>. Hence we can find <math>n_1,n_2\geq 1</math> such that | |||
<math display="block"> | |||
Q_{n_1}(x,y)\geq 0, Q_{n_2}(y,x) > 0. | |||
</math> | |||
Then for all <math>p\geq 0</math> we get that | |||
<math display="block"> | |||
Q_{n_1+p+n_2}(y,y)\geq Q_{n_2}(y,x)Q_p(x,x)Q_{n_1}(x,y), | |||
</math> | |||
and thus we have | |||
<math display="block"> | |||
U(y,y)\geq\sum_{p=0}^\infty Q_{n_1+p+n_2}(y,y)\geq Q_{n_2}(y,x)\left(\sum_{p=0}^\infty Q_p(x,x)\right)Q_{n_1}(x,y)=\infty, | |||
</math> | |||
since <math>x\in R</math>.}} | |||
{{alert-info | | |||
The above lemma has the following important consequence. If <math>x\in R</math> and <math>y\in E\setminus R</math>, then <math>U(x,y)=0</math>, which means that one cannot go from a recurrent point to a transient point. | |||
}} | |||
{{proofcard|Theorem (Classification of states)|thm-1|Let <math>R</math> be the set of all recurrent points and let <math>N_x</math> be defined as above. Then there exists a partition of <math>R</math>, denoted <math>(R_i)_{i\in I}</math> for some index set <math>I</math>, i.e. | |||
<math display="block"> | |||
R=\bigcup_{i\in I}R_i, | |||
</math> | |||
such that the following properties hold. | |||
<ul style{{=}}"list-style-type:lower-roman"><li>If <math>x\in R</math> and <math>i\in I</math> such that <math>x\in R_i</math>, we get that | |||
\begin{itemize | |||
</li> | |||
<li><math>N_y=\infty</math>, <math>\p_x</math>-a.s. for all <math>y\in R_i</math>, | |||
</li> | |||
<li><math>N_y=0</math>, <math>\p_x</math>-a.s. for all <math>y\in E\setminus R_i</math>.} | |||
\end{itemize} | |||
</li> | |||
<li>If <math>x\in E\setminus R</math> and <math>T=\inf\{n\geq 0\mid X_n\in R\}</math>, we get that | |||
\begin{itemize | |||
</li> | |||
<li><math>T=\infty</math> and <math>N_y < \infty</math>, <math>\p_x</math>-a.s. for all <math>y\in E</math>, | |||
</li> | |||
<li><math>T < \infty</math> and then there exists <math>j\in I</math> such that for all <math>n\geq T</math> we get <math>X_n\in R_j</math>, <math>\p_x</math>-a.s.} | |||
\end{itemize} | |||
</li> | |||
</ul> | |||
|For <math>x,y\in R</math>, let us note <math>x\sim Y</math> if <math>U(x,y) > 0</math>. It follows from lemma 3.3. that this is an equivalence relation{{efn|for transitivity observe that if <math>Q_n(x,y) > 0</math> and <math>Q_m(y,z) > 0</math>, then <math>Q_{n+m}(x,z)</math>.}} on <math>R</math>. Let <math>i\in I</math> and <math>x\in R_i</math>. We have that <math>U(x,y)=0</math> for all <math>y\in E\setminus R_i</math> and hence <math>N_y=0</math>, <math>\p_x</math>-a.s. for all <math>y\in E\setminus R_i</math>. If <math>y\in R_i</math>, we have from lemma 3.3. that <math>\p_x[H_y < \infty]=1</math> and it follows from the strong Markov property that | |||
<math display="block"> | |||
\p_x[N_y=\infty]=\E_x[\one_{\{H_y < \infty\}}\one_{\{N_y=\infty\}}\circ\Theta_{H_y}]=\p_x[H_y < \infty]\p_y[N_y=\infty]=1. | |||
</math> | |||
If <math>x\in E\setminus R</math> and <math>T=\infty</math>, it easily follows from the strong Markov property that <math>N_y < \infty</math> for all <math>y\in E\setminus R</math>. If <math>T < \infty</math>, let <math>j\in I</math> such that <math>X_T\in R_j</math>. Then apply the strong Markov property with <math>T</math> and the first part of the theorem, which then gives us that <math>X_n\in R_j</math> for all <math>n\geq T</math>.}} | |||
{{definitioncard|Irreducibility| | |||
A chain is called irreducible if <math>U(x,y) > 0</math> for all <math>x,y\in E</math>. | |||
}} | |||
{{proofcard|Corollary|cor-1|If the chain is irreducible, then the following hold. | |||
<ul style{{=}}"list-style-type:lower-roman"><li>Either all states are recurrent and there exists a recurrent chain and for all <math>x\in E</math> we get | |||
<math display="block"> | |||
\p_x[N_y=\infty, \forall y\in E]=1, | |||
</math> | |||
</li> | |||
<li>or all states are transient and then for all <math>x\in E</math> we get | |||
<math display="block"> | |||
\p_x[N_y < \infty,\forall y\in E]=1. | |||
</math> | |||
Moreover, if <math>\vert E\vert < \infty</math>, then only the first case can occur. | |||
</li> | |||
</ul> | |||
|If there exists a recurrent state, the lemma 3.3. shows that all states are recurrent with <math>U(x,y) > 0</math> for all <math>x,y\in E</math> and there is only one recurrent chain. If <math>\vert E\vert < \infty</math> and if all states are transient, then we get <math>\p_x</math>-a.s. that | |||
<math display="block"> | |||
\sum_{y\in E}N_y < \infty, | |||
</math> | |||
but we know | |||
<math display="block"> | |||
\sum_{y\in E}N_y=\sum_{y\in E}\sum_{n\geq 0}\one_{\{X_n=y\}}=\sum_{n\geq 0}\sum_{y\in E}\one_{\{X_n=y\}}=\infty. | |||
</math>}} | |||
'''Example''' | |||
Let us first recall that the results obtained for the canonical Markov chain hold for any arbitrary Markov chain. Now let <math>(Y_n)_{n\geq 0}</math> be a Markov chain with transition matrix <math>Q</math>. For instance, if <math>Y_0=y</math> and <math>N_x^Y=\sum_{n\geq0} \one_{\{ Y-n=x\}}</math>, we have for that <math>k\in\bar\N</math> | |||
<math display="block"> | |||
\p[N_x^Y=k]=\p_y[N_x=k], | |||
</math> | |||
since the left hand side is <math>\p[(Y_n)_{n\geq 0}\in B]</math> with <math>B:=\{\omega\in E^\N\mid N_x(\omega)=k\}</math>. | |||
{{proofcard|Theorem|thm-2|Let <math>(\xi_j)_{j\geq 1}</math> be iid r.v.'s having the law <math>\mu</math> with <math>\xi_j\in\mathbb{Z}</math> for all <math>j\geq 1</math> and assume that <math>\E[\vert\xi_1\vert] < \infty</math> and <math>m=\E[\xi_1]</math>. Moreover, set <math>Y_n=Y_0+\sum_{j=1}^n\xi_j</math>. Then | |||
<ul style{{=}}"list-style-type:lower-roman"><li>if <math>m\not=0</math>, then all states are transient. | |||
</li> | |||
<li>if <math>m=0</math>, then all states are recurrent. Moreover, the chain is irreducible if and only if the subgroup given by <math>\{y\in\mathbb{Z}\mid \mu(y) > 0\}</math> is in <math>\mathbb{Z}</math>. | |||
</li> | |||
</ul> | |||
|We need to show both points. | |||
<ul style{{=}}"list-style-type:lower-roman"><li>If <math>m\not=0</math>, we know from the strong law of large numbers that <math>(Y_n)\xrightarrow{n\to\infty\atop a.s.}\infty</math> and hence all states are transient. | |||
</li> | |||
<li>Assume <math>m=0</math> and <math>0</math> is transient. Thus <math>U(0,0) < \infty</math>. We can assume that <math>Y_0=0</math>. For <math>x\in\mathbb{Z}</math> we get | |||
<math display="block"> | |||
U(0,x)\leq U(x,x)=U(0,0). | |||
</math> | |||
Therefore we get that for all <math>n\geq 1</math> | |||
<math display="block"> | |||
\sum_{\vert x\vert\leq n}U(0,x)\leq (2n+1)U(0,0)\leq Cn, | |||
</math> | |||
where <math>C=3 U(0,0)</math>. Moreover, by the law of large numbers, there exists some <math>N</math> sufficiently large such that for all <math>n\geq N</math> | |||
<math display="block"> | |||
\p[\vert Y_n\vert\leq \varepsilon n] > Y_2 | |||
</math> | |||
with <math>\varepsilon=\frac{1}{6C}</math>, or equivalently | |||
<math display="block"> | |||
\sum_{\vert x\vert\leq \varepsilon n}Q_n(0,x)\geq \frac{1}{2}. | |||
</math> | |||
If <math>p\geq n\geq N</math>, then | |||
<math display="block"> | |||
\sum_{\vert x\vert\leq \varepsilon n}Q_p(0,x)\geq \sum_{\vert x\vert\leq \varepsilon p}Q_p(0,x) > \frac{1}{2}, | |||
</math> | |||
and by summing over <math>p</math>, we get | |||
<math display="block"> | |||
\sum_{\vert x\vert\leq \varepsilon n}U(0,n)\geq \sum_{p=N}^n\sum_{\vert x\vert\leq \varepsilon p}Q_p(0,x) > \frac{n-N}{\varepsilon}. | |||
</math> | |||
But if <math>\varepsilon n\geq 1</math>, then | |||
<math display="block"> | |||
\sum_{\vert x\vert\leq \varepsilon n}U(0,x)\leq C\varepsilon n=\frac{n}{6}, | |||
</math> | |||
which leads to a contradiction for <math>n</math> sufficiently large. For the last statement, write <math>G=\langle x\in\mathbb{Z}\mid \mu(x) > 0\rangle</math>. Then, since <math>Y_0=0</math>, we get | |||
<math display="block"> | |||
\p[Y_n\in G\mid \forall n\in \N]=1. | |||
</math> | |||
If <math>G\not=\mathbb{Z}</math>, then obviously <math>(Y_n)_{n\geq 0}</math> is irreducible. If <math>G=\mathbb{Z}</math>, then write | |||
<math display="block"> | |||
H:=\{x\in\mathbb{Z}\mid U(0,x) > 0\}. | |||
</math> | |||
It follows that <math>H</math> is a subgroup of <math>\mathbb{Z}</math>, indeed, for <math>x,y\in H</math>, we get that | |||
<math display="block"> | |||
Q_{n+p}(0,x+y)\geq Q_n(0,x)Q_p(x,x+y)=Q_n(0,x)Q_p(0,y), | |||
</math> | |||
and thus we get that <math>x+y\in H</math>. For <math>x\in H</math> and with <math>0</math> being recurrent, we get that <math>U(0,x) > 0</math> implies that <math>U(x,x) > 0</math> and therefore <math>U(x,0)=U(0,-x)</math>, which implies that <math>-x\in H</math>. Now since <math>H\supset\{ x\in\mathbb{Z}\mid \mu(x) > 0\}</math>, we get that <math>H=\mathbb{Z}</math> and the claim follows. | |||
</li> | |||
</ul>}} | |||
'''Example''' | |||
Let <math>\mu=\frac{1}{2}\delta_{-2}+\frac{1}{2}\delta_{2}</math>. Then all states are recurrent but there are two recurrence classes. | |||
===Random variable on a graph=== | |||
Assume that <math>\vert E\vert < \infty</math>. Moreover, let <math>A\subset\mathcal{P}(E)</math> and for <math>x\in E</math> let | |||
<math display="block"> | |||
A_x=\{y\in E\mid \{x,y\}\in A\}\not=\varnothing. | |||
</math> | |||
A graph <math>\mathcal{G}</math> is said to be connected if every pair of vertices in the graph is connected. | |||
{{proofcard|Proposition|prop-3|The simple random walk on a finite graph is recurrent and irreducible. | |||
|Exercise{{efn|Connected implies irreducible. Then apply corollary 3.5.}}.}} | |||
==General references== | |||
{{cite arXiv|last=Moshayedi|first=Nima|year=2020|title=Lectures on Probability Theory|eprint=2010.16280|class=math.PR}} | |||
==Notes== | |||
{{notelist}} |
Latest revision as of 01:53, 8 May 2024
From now on we will only use the canonical Markov chain. Recall that for [math]x\in E[/math] we have
Let [math]x\in E[/math]. Then we have two situations, which can occur.
- [math]\p_x[H_x \lt \infty]=1[/math] and [math]N_x=\infty[/math] [math]\p_x[/math]-a.s. In this case [math]x[/math] is said to be reccurrent.
- [math]\p_x[H_x \lt \infty] \lt 1[/math] and [math]N_x \lt \infty[/math] [math]\p_x[/math]-a.s. More precisely
[[math]] \E_x[N_x]=\frac{1}{\p_x[H_x \lt \infty]} \lt \infty. [[/math]]In this case [math]x[/math] is said to be transient.
For [math]k\geq 1[/math], it follows from the strong Markov property that
The potential kernel of the chain is given by the function
The following hold.
- For all [math]x,y\in E[/math] we have
[[math]] U(x,y)=\sum_{n\geq 0}Q_n(x,y). [[/math]]
- [math]U(x,x)=\infty[/math] if and only if [math]x[/math] is recurrent.
- For all [math]x,y\in E[/math] it follows that if [math]x\not=y[/math] then
[[math]] U(x,y)=\p_x[H_y \lt \infty]U(y,y). [[/math]]
We need to show all three points.
- Note that
[[math]] U(x,y)=\E_x\left[\sum_{n\geq 0}\one_{\{N_x=y\}}\right]=\sum_{n\geq 0}\p_x[X_n=y]=\sum_{n\geq 0}Q_n(x,y). [[/math]]
- Exercise.
- This follows from the strong Markov property. We get
[[math]] \E_x[N_y]=\E_x[\one_{\{H_y \lt \infty\}}N_y\circ\Theta_{H_y}]=\E_x[\one_{\{H_y \lt \infty\}}\E_y[N_y]]=\p_x[H_y \lt \infty]U(y,y). [[/math]]
Example
Let us consider the Markov chain, starting at 0, on [math]\mathbb{Z}^d[/math] with transition matrix given by
This Markov chain has the same distribution as [math](Y_n^1,...,Y_n^d)_{n\geq 0}[/math], where [math]Y^1,...,Y^d[/math] are iid r.v.'s of a simple random walk on [math]\mathbb{Z}[/math], starting at 0. Hence we get
Moreover, [math]\p[Y_n^1=0]=0[/math] if [math]n[/math] is odd and for [math]n=2k[/math] we get
Therefore we get that
Now with Stirling's formula[a] we get
Consequently, 0 is recurrent if [math]d=1[/math] and transient if [math]d\geq 2[/math].
Now let us denote the set of all recurrent points by [math]R[/math]. Then we can obtain the following lemma.
Let [math]x\in R[/math] and let [math]y\in E[/math] such that [math]U(x,y) \gt 0[/math]. Then [math]y\in R[/math] and
Let us first show that [math]\p_y[H_x \lt \infty]=1[/math]. We have that
Then [math]U(x,y) \gt 0[/math] implies that [math]\p_x[H_y \lt \infty] \gt 0[/math] and thus [math]\p_y[H_x=\infty]=0[/math]. Hence we can find [math]n_1,n_2\geq 1[/math] such that
Then for all [math]p\geq 0[/math] we get that
and thus we have
since [math]x\in R[/math].
The above lemma has the following important consequence. If [math]x\in R[/math] and [math]y\in E\setminus R[/math], then [math]U(x,y)=0[/math], which means that one cannot go from a recurrent point to a transient point.
Let [math]R[/math] be the set of all recurrent points and let [math]N_x[/math] be defined as above. Then there exists a partition of [math]R[/math], denoted [math](R_i)_{i\in I}[/math] for some index set [math]I[/math], i.e.
- If [math]x\in R[/math] and [math]i\in I[/math] such that [math]x\in R_i[/math], we get that \begin{itemize
- [math]N_y=\infty[/math], [math]\p_x[/math]-a.s. for all [math]y\in R_i[/math],
- [math]N_y=0[/math], [math]\p_x[/math]-a.s. for all [math]y\in E\setminus R_i[/math].} \end{itemize}
- If [math]x\in E\setminus R[/math] and [math]T=\inf\{n\geq 0\mid X_n\in R\}[/math], we get that \begin{itemize
- [math]T=\infty[/math] and [math]N_y \lt \infty[/math], [math]\p_x[/math]-a.s. for all [math]y\in E[/math],
- [math]T \lt \infty[/math] and then there exists [math]j\in I[/math] such that for all [math]n\geq T[/math] we get [math]X_n\in R_j[/math], [math]\p_x[/math]-a.s.} \end{itemize}
For [math]x,y\in R[/math], let us note [math]x\sim Y[/math] if [math]U(x,y) \gt 0[/math]. It follows from lemma 3.3. that this is an equivalence relation[b] on [math]R[/math]. Let [math]i\in I[/math] and [math]x\in R_i[/math]. We have that [math]U(x,y)=0[/math] for all [math]y\in E\setminus R_i[/math] and hence [math]N_y=0[/math], [math]\p_x[/math]-a.s. for all [math]y\in E\setminus R_i[/math]. If [math]y\in R_i[/math], we have from lemma 3.3. that [math]\p_x[H_y \lt \infty]=1[/math] and it follows from the strong Markov property that
A chain is called irreducible if [math]U(x,y) \gt 0[/math] for all [math]x,y\in E[/math].
If the chain is irreducible, then the following hold.
- Either all states are recurrent and there exists a recurrent chain and for all [math]x\in E[/math] we get
[[math]] \p_x[N_y=\infty, \forall y\in E]=1, [[/math]]
- or all states are transient and then for all [math]x\in E[/math] we get
[[math]] \p_x[N_y \lt \infty,\forall y\in E]=1. [[/math]]Moreover, if [math]\vert E\vert \lt \infty[/math], then only the first case can occur.
If there exists a recurrent state, the lemma 3.3. shows that all states are recurrent with [math]U(x,y) \gt 0[/math] for all [math]x,y\in E[/math] and there is only one recurrent chain. If [math]\vert E\vert \lt \infty[/math] and if all states are transient, then we get [math]\p_x[/math]-a.s. that
Example
Let us first recall that the results obtained for the canonical Markov chain hold for any arbitrary Markov chain. Now let [math](Y_n)_{n\geq 0}[/math] be a Markov chain with transition matrix [math]Q[/math]. For instance, if [math]Y_0=y[/math] and [math]N_x^Y=\sum_{n\geq0} \one_{\{ Y-n=x\}}[/math], we have for that [math]k\in\bar\N[/math]
since the left hand side is [math]\p[(Y_n)_{n\geq 0}\in B][/math] with [math]B:=\{\omega\in E^\N\mid N_x(\omega)=k\}[/math].
Let [math](\xi_j)_{j\geq 1}[/math] be iid r.v.'s having the law [math]\mu[/math] with [math]\xi_j\in\mathbb{Z}[/math] for all [math]j\geq 1[/math] and assume that [math]\E[\vert\xi_1\vert] \lt \infty[/math] and [math]m=\E[\xi_1][/math]. Moreover, set [math]Y_n=Y_0+\sum_{j=1}^n\xi_j[/math]. Then
- if [math]m\not=0[/math], then all states are transient.
- if [math]m=0[/math], then all states are recurrent. Moreover, the chain is irreducible if and only if the subgroup given by [math]\{y\in\mathbb{Z}\mid \mu(y) \gt 0\}[/math] is in [math]\mathbb{Z}[/math].
We need to show both points.
- If [math]m\not=0[/math], we know from the strong law of large numbers that [math](Y_n)\xrightarrow{n\to\infty\atop a.s.}\infty[/math] and hence all states are transient.
- Assume [math]m=0[/math] and [math]0[/math] is transient. Thus [math]U(0,0) \lt \infty[/math]. We can assume that [math]Y_0=0[/math]. For [math]x\in\mathbb{Z}[/math] we get
[[math]] U(0,x)\leq U(x,x)=U(0,0). [[/math]]Therefore we get that for all [math]n\geq 1[/math][[math]] \sum_{\vert x\vert\leq n}U(0,x)\leq (2n+1)U(0,0)\leq Cn, [[/math]]where [math]C=3 U(0,0)[/math]. Moreover, by the law of large numbers, there exists some [math]N[/math] sufficiently large such that for all [math]n\geq N[/math][[math]] \p[\vert Y_n\vert\leq \varepsilon n] \gt Y_2 [[/math]]with [math]\varepsilon=\frac{1}{6C}[/math], or equivalently[[math]] \sum_{\vert x\vert\leq \varepsilon n}Q_n(0,x)\geq \frac{1}{2}. [[/math]]If [math]p\geq n\geq N[/math], then[[math]] \sum_{\vert x\vert\leq \varepsilon n}Q_p(0,x)\geq \sum_{\vert x\vert\leq \varepsilon p}Q_p(0,x) \gt \frac{1}{2}, [[/math]]and by summing over [math]p[/math], we get[[math]] \sum_{\vert x\vert\leq \varepsilon n}U(0,n)\geq \sum_{p=N}^n\sum_{\vert x\vert\leq \varepsilon p}Q_p(0,x) \gt \frac{n-N}{\varepsilon}. [[/math]]But if [math]\varepsilon n\geq 1[/math], then[[math]] \sum_{\vert x\vert\leq \varepsilon n}U(0,x)\leq C\varepsilon n=\frac{n}{6}, [[/math]]which leads to a contradiction for [math]n[/math] sufficiently large. For the last statement, write [math]G=\langle x\in\mathbb{Z}\mid \mu(x) \gt 0\rangle[/math]. Then, since [math]Y_0=0[/math], we get[[math]] \p[Y_n\in G\mid \forall n\in \N]=1. [[/math]]If [math]G\not=\mathbb{Z}[/math], then obviously [math](Y_n)_{n\geq 0}[/math] is irreducible. If [math]G=\mathbb{Z}[/math], then write[[math]] H:=\{x\in\mathbb{Z}\mid U(0,x) \gt 0\}. [[/math]]It follows that [math]H[/math] is a subgroup of [math]\mathbb{Z}[/math], indeed, for [math]x,y\in H[/math], we get that[[math]] Q_{n+p}(0,x+y)\geq Q_n(0,x)Q_p(x,x+y)=Q_n(0,x)Q_p(0,y), [[/math]]and thus we get that [math]x+y\in H[/math]. For [math]x\in H[/math] and with [math]0[/math] being recurrent, we get that [math]U(0,x) \gt 0[/math] implies that [math]U(x,x) \gt 0[/math] and therefore [math]U(x,0)=U(0,-x)[/math], which implies that [math]-x\in H[/math]. Now since [math]H\supset\{ x\in\mathbb{Z}\mid \mu(x) \gt 0\}[/math], we get that [math]H=\mathbb{Z}[/math] and the claim follows.
Example
Let [math]\mu=\frac{1}{2}\delta_{-2}+\frac{1}{2}\delta_{2}[/math]. Then all states are recurrent but there are two recurrence classes.
Random variable on a graph
Assume that [math]\vert E\vert \lt \infty[/math]. Moreover, let [math]A\subset\mathcal{P}(E)[/math] and for [math]x\in E[/math] let
A graph [math]\mathcal{G}[/math] is said to be connected if every pair of vertices in the graph is connected.
General references
Moshayedi, Nima (2020). "Lectures on Probability Theory". arXiv:2010.16280 [math.PR].