0
$\begingroup$

Another probability theory question I am kind of confused about.

Consider a finite ergodic Markov chain with the initial distribution $\gamma_{x}$ where $\gamma_{x}$ is the measure concentrated at $x \in X$, $X$ the state space. Let $\tau$ be the first positive $k$ such that $\omega_{k}=x$. Evaluate $\lim_{n \rightarrow \infty}{\frac{\log P(\tau > n)}{n}}$.

Any help is appreciated, thanks!

1 Answers 1

2

Let $S$ denote the state space of the Markov chain and $S_x=S\setminus\{x\}$. Let $P=(p_{yz})_{(y,z)\in S\times S}$ denote the transition matrix of the Markov chain and $P_x=(p_{yz})_{(y,z)\in S_x\times S_x}$ the matrix obtained from $P$ omitting the $x$ line and the $x$ column. Let $U_x=(p_{xy})_{y\in S_x}$ denote the line vector describing the sub-distribution of $X_1$ restricted to $X_1\ne x$, conditionally on $X_0=x$. Finally, let $\mathbf 1_x=(1)_{y\in S_x}$ denote the column vector of ones indexed by $S_x$.

Then, for every $n\geqslant1$, $ \mathbb P_x(\tau_x\gt n)=U_xP_x^{n-1}\mathbf 1_x.\tag{$\ast$} $ Assume first that $p_{xy}\ne0$ for every $y\ne x$. Then $N_x:Q\mapsto N_x(Q)=\sum\limits_{(y,z)\in S_x\times S_x} p_{xy}|Q_{yz}|$ is a norm on the space of square matrices indexed by $S_x$ and $N_x(Q)=U_xQ\mathbf 1_x$ for every matrix $Q$ with nonnegative coefficients, hence $\mathbb P_x(\tau_x\gt n)=N_x(P_x^{n-1})$. A consequence is that $ \mathbb P_x(\tau_x\gt n)^{1/n}\to\varrho(P_x), $ where, for every matrix $Q$, $\varrho(Q)$ denotes the spectral radius of $Q$, which is also the Perron–Frobenius eigenvalue. In other words, $ \color{red}{\frac{\log\mathbb P_x(\tau_x\gt n)}n\to\log\varrho(P_x)}. $ More generally, assume that the Markov chain is irreducible and aperiodic. Then there exists $k\geqslant0$ such that every coefficient of $U_xP_x^k$ is positive, hence, considering $(U_xP_x^k)P_x^{n-k-1}\mathbf 1_x$, one sees that the same result applies.

Note that the result may really depend on $x$. For example, consider the Markov chain with states $0$ and $1$ such that $p_{01}=a$ and $p_{10}=b$. Then, for every $n\geqslant1$, $\mathbb P_0(\tau_0\gt n)=a(1-b)^{n-1},\qquad \mathbb P_1(\tau_1\gt n)=b(1-a)^{n-1}, $ hence the limits above are $\log(1-b)$ for $x=0$ and $\log(1-a)$ for $x=1$ (or, more directly, $P_0$ and $P_1$ are $1\times1$ matrices whose unique coefficients are $1-b$ and $1-a$ respectively).

Edit To prove the key formula $(\ast)$, note that $\mathbb P_x(\tau_x\gt n)$ is the sum of $p(c)=\prod\limits_{k=1}^np_{x_{k-1}x_k}$ over every path $c=(x_k)_{0\leqslant k\leqslant n}$ in $S$ starting from $x_0=x$ such that $x_k\ne x$ for every $k\geqslant1$. Hence, $ \mathbb P_x(\tau_x\gt n)=\sum\limits_{c}p(c)=\sum_{x_1\in S_x}p_{xx_1}\sum_{x_2\in S_x}p_{x_1x_2}\cdots\sum_{x_n\in S_x}p_{x_{n-1}x_n}, $ that is, $ \mathbb P_x(\tau_x\gt n)=\sum_{x_1\in S_x}(U_x)_{x_1}\sum_{x_n\in S_x}(P_x)^{n-1}_{x_1x_n}=\sum_{x_n\in S_x}(U_xP_x^{n-1})_{x_n}=U_xP_x^{n-1}\mathbf 1_x. $