Probability-one event for Markov chain - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T18:34:10Z http://mathoverflow.net/feeds/question/78706 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/78706/probability-one-event-for-markov-chain Probability-one event for Markov chain Elena Yudovina 2011-10-20T21:11:21Z 2011-10-24T15:12:16Z <p>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$.</p> <p>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}$.)</p> <p>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.)</p> <p>Want to show: with probability 1, $X$ visits $S$ infinitely often.</p> <p>It seems like it ought to be either trivially true or trivially false, but I'm failing to determine which...</p> http://mathoverflow.net/questions/78706/probability-one-event-for-markov-chain/78708#78708 Answer by Jeremy Voltz for Probability-one event for Markov chain Jeremy Voltz 2011-10-20T21:45:38Z 2011-10-20T21:45:38Z <p>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?</p> <p>I can delete this later, as I realize this doesn't qualify as an answer. I would just like some clarification. </p> http://mathoverflow.net/questions/78706/probability-one-event-for-markov-chain/78721#78721 Answer by Byron Schmuland for Probability-one event for Markov chain Byron Schmuland 2011-10-20T23:49:14Z 2011-10-24T15:12:16Z <p>If I've understood your problem correctly, an argument along these lines may help:</p> <hr> <p>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).$$</p> <p>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)&amp;=&amp;\sum_x\mathbb{P}(X_{n+1}\in S\,|\,E(x))1_{E(x)}\cr &amp;=&amp;\sum_x\mathbb{P}(X_{n+1}\in S\,|\,X_n=x_n)1_{E(x)}\cr &amp;=&amp;\sum_x P(x_n, S)1_{E(x)}\cr &amp;=&amp;P(X_n, S), \end{eqnarray*} where $P$ is the transition kernel for the Markov chain.</p> <p>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.</p>