Probability-one event for Markov chain - MathOverflow

Probability-one event for Markov chain

2011-10-20T21:11:21Z

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...

Answer by Jeremy Voltz for Probability-one event for Markov chain

2011-10-20T21:45:38Z

I'm a bit confused by this problem, but I don't have enough reputation to write a comment. 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.

Answer by Byron Schmuland for Probability-one event for Markov chain

2011-10-20T23:49:14Z

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.