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

  • $\begingroup$ 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. $\endgroup$ Oct 20, 2011 at 21:45
  • $\begingroup$ 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. $\endgroup$ Oct 20, 2011 at 22:18

1 Answer 1


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.

  • $\begingroup$ I think this misses the point that $K(\omega)$ was meant to be a random set depending on $\omega$. $\endgroup$ Oct 21, 2011 at 4:56
  • $\begingroup$ In my solution $\varepsilon_K(\omega)>0$ and $K(\omega)$ can be random. Only $S$ must be a non-random set. $\endgroup$
    – user6096
    Oct 21, 2011 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.