# Probability-one event for Markov chain

Let $X$ be a Markov chain, with countable state space $I$ and transition probability matrix $P$. $X$ is irreducible, but need not be recurrent. Let $S$ be a fixed subset of $I$.

Define a subset $K$ of $I$ to be "nice" if there exists $\epsilon = \epsilon_K$ such that for all $k \in K$, $P_{kS} \geq \epsilon$. (Here, $P_{kS} = \sum_{s \in S} P_{ks}$.)

Given: with probability 1, there exists a nice set which $X$ visits infinitely often. (Note that the set $K$, and therefore the value of $\epsilon_K$, may be random.)

Want to show: with probability 1, $X$ visits $S$ infinitely often.

It seems like it ought to be either trivially true or trivially false, but I'm failing to determine which...

-
I'm a bit confused by this problem. How can $K$ be random? Any subset of $I$ is either nice or it isn't, and that determination only depends on $I$, $S$, and $P$, all of which are non-random entities. Am I missing something? I can delete this later, as I realize this doesn't qualify as an answer. I would just like some clarification. –  Jeremy Voltz Oct 20 '11 at 21:45
Let me write this in terms of the underlying probability space $\Omega$: I know that for almost all $\omega \in \Omega$, there exists $K = K(\omega)$ such that $X_n(\omega) \in K(\omega)$ for infinitely many $n$. However, it may not be true that there is a single deterministic $K$ which almost all $X_n(\omega)$'s visit. –  Elena Yudovina Oct 20 '11 at 22:18
Thank you, that makes sense. –  Jeremy Voltz Oct 22 '11 at 15:17

If I've understood your problem correctly, an argument along these lines may help:

Let ${\cal F}_n=\sigma(X_0,X_1,\dots,X_n)$ and define $S_n=\left(X_n\in S\right)$, so that $S_n\in {\cal F}_n$. We will use Levy's generalization of the Borel-Cantelli Lemma which states that $$\left( S_n\mbox{ i.o.} \right)=\left(\sum_n \mathbb{P}(S_{n+1} | {\cal F}_{n})=\infty\right).$$

Let's calculate the conditional probability. Letting $E(x)=\{ X_{n}=x_{n},X_{n-1}=x_{n-1},\dots,X_0=x_0\}$ be a generic partition set, we get \begin{eqnarray*} \mathbb{P}(S_{n+1}\,|\,{\cal F}_n)&=&\sum_x\mathbb{P}(X_{n+1}\in S\,|\,E(x))1_{E(x)}\cr &=&\sum_x\mathbb{P}(X_{n+1}\in S\,|\,X_n=x_n)1_{E(x)}\cr &=&\sum_x P(x_n, S)1_{E(x)}\cr &=&P(X_n, S), \end{eqnarray*} where $P$ is the transition kernel for the Markov chain.

The definition of nice" set gives $P(X_n,S)\geq \varepsilon_K 1_K(X_{n}),$ and since $(X_n)$ visits $K$ infinitely often, we have $$\sum_n P(X_n,S)\geq \varepsilon_K \sum_n 1_K(X_{n})=\infty$$ almost surely.

-
I think this misses the point that $K(\omega)$ was meant to be a random set depending on $\omega$. –  Anthony Quas Oct 21 '11 at 4:56
In my solution $\varepsilon_K(\omega)>0$ and $K(\omega)$ can be random. Only $S$ must be a non-random set. –  Byron Schmuland Oct 21 '11 at 15:17