1

I have a transition matrix $P=(p_{x,y})_{x,y\in S}$ which defines some Markov chain $X$ on some state space $S$. Now, I consider for $A,B\subset S$, $A\cap B=\emptyset$ the probability that $X$ transitions in one step from $A$ to $B$, i.e., $P[X_{t+1} \in B| X_t\in A]$. I want to find a lower bound on this transition probability and I know that I have a uniform bound $p_{x,y}\geq \alpha$ for some constant $\alpha\in (0,1)$ and all $x,y\in S$ with $p_{x,y}>0$ .

Denoting by $E_{A,B}$ the number of possible transitions between $A$ and $B$, i.e., $$E_{A,B}=|\{x\in A, y\in B| p_{x,y}>0\}|$$ intuitively, I only consider each transition probability for each $x\in A$ to $y\in B$, i.e., $\sum_{x\in A,y\in B}p_{x,y}$ and I then find the estimate $$\sum_{x\in A,y\in B}p_{x,y}\geq E_{A,B}\alpha.$$

But, this does not really work, since by rules of conditional probability I have $P[X_{t+1} \in B| X_t\in A]\neq \sum_{x\in A}P[X_{t+1} \in B| X_t = x]$. Is the intuition correct and how can I prove it in this case? Or is it incorrect and what can I do?

PS: Basically, when I calculate it explicitly I am stuck with $$\alpha\sum_{x\in A,y\in B, p_{x,y}>0} P[X_t = x| X_t \in A]$$ as a lower bound.

Jfischer
  • 1,239
  • $\sum_{x\in A,y\in B}p_{x,y}$ is not even necessarily a probability; it may be much bigger than $1$. – Misha Lavrov Oct 31 '21 at 16:20
  • Thank you for reminding me. I got a biy lost. Is there nonetheless something I can do, in particular considering what I wrote in the EDIT? – Jfischer Oct 31 '21 at 16:24

1 Answers1

1

We can always say that the probability is at least $$\min_{x \in A} \sum_{y \in B} p_{xy} \ge \alpha \cdot \min_{x \in A} \#\{y \in B: p_{xy} > 0\}.$$ The logic here is that $\Pr[X_{t+1} \in B \mid X_t \in A]$ can be written as a sum of terms $\Pr[X_{t+1} \in B \mid X_t = x] \Pr[X_t =x \mid X_t \in A]$, which is a weighted average of the conditional probabilities $\Pr[X_{t+1} \in B \mid X_t = x]$. So it should be at least the smallest of those probabilities, which is what we see above.

In general, we should not be able to say more without some understanding of the long-term behavior of this Markov chain. It's possible that out of all the states in $A$, only one state is actually recurrent; so when we condition on $X_t \in A$ for large $t$, we end up conditioning on more or less $X_t = x$. That state $x$ might be the one that achieves the minimum in the expression above.

Even if the Markov chain is ergodic, it's possible to approach the $\min_{x \in A}$ type of behavior if the "worst" state in $A$ has a very high limiting probability, while the "good" states in $A$ have low limiting probabilities. In that case, for large $t$, conditioning on $X_t \in A$ can still be arbitrarily close to conditioning on $X_t = x$.

Misha Lavrov
  • 142,276
  • To add the details, there is a partition $A_1,...,A_k$ of $S$ such that $p_{x,y}>0$ implies for $x\in A_i$ that $y\in A_i\cup A_{i+1}$ for $i=1,...,k-1$ and for $i=k$ even $y\in A_k$. Additionally, any state of $A_k$ is absorbing and I try to analyse the time to absorption. – Jfischer Oct 31 '21 at 16:39
  • 1
    Are the $A$ and $B$ in your question a pair $(A_i, A_{i+1})$? – Misha Lavrov Oct 31 '21 at 16:44
  • Indeed, I want to use $\alpha $ and $E_{A_i,A_{i+1}}$ to estimate the expected time to absorption. – Jfischer Oct 31 '21 at 16:53
  • Nothing better can be said in that case. Once again, it's possible that by the time we end up in $A_i$, we are guaranteed or nearly guaranteed to end up in the worst state of $A_i$. – Misha Lavrov Oct 31 '21 at 16:58