MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 5 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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