0
$\begingroup$

Question: Given an irreducible Markov Chain. Prove you can reach any pair of states in $N$ steps with greater than 0 probability

So essentially given any pair of states a start state and end state in the Markov Chain that's irreducible it's possible to reach the end state from the start state in $N$ steps with probability greater than 0 where $N$ is a number of steps where you can get from any start state in the Markov Chain to the end state in the Markov Chain with probability greater than 0. $N$ should be independent of the states of the chain s.t. the probability of getting from a start state to and end state has a probability > 0 within $N$ steps

The definition of irreducible Markov Chain can be found here.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ $N$ is undefined and therefore meaningless. Please clarify. It would help also to state exactly what "reach any pair of states" means. If you're not sure, then consult with the teacher or author who posed the problem! If I had to guess, I would suppose the chain is defined on a finite number of states and $N$ is related to that number: for instance, it could be the number of states. "Reach any pair of states" might mean that given two states $s_1,s_2$ and arbitrary starting state $s,$ there exists a sequence of $N$ transitions from $s$ having nonzero probability and including $s_1$ and $s_2.$ $\endgroup$
    – whuber ♦
    Commented Mar 29, 2022 at 18:28
  • $\begingroup$ @whuber added more to the question. Let me know if anything else is unclear. Thanks! $\endgroup$
    – Gooby
    Commented Mar 29, 2022 at 18:58
  • $\begingroup$ The assertion is obviously false: there cannot possibly be any universal value. To prove this, suppose there were such a value $N$. Consider a chain on the $2N+3$ states $s_i,$ $i=0, 1, \ldots, 2N+2,$ where $s_i$ makes transitions to $s_{i\pm 1 \operatorname{mod} 2N+3}$ with equal probabilities of $1/2.$ This is irreducible, but starting at $s_i$ you cannot even reach $s_{i+N+1\operatorname{mod} 2N+3}$ in fewer than $N+1$ transitions. $\endgroup$
    – whuber ♦
    Commented Mar 29, 2022 at 19:02
  • $\begingroup$ @whuber is this under the assumption it must be done in exactly $N$ steps? I've concluded that it can be within $N$ steps. That shouldn't be impossible if the Markov Chain is irreducible. $\endgroup$
    – Gooby
    Commented Mar 29, 2022 at 19:07
  • 1
    $\begingroup$ "Universal" means there is a (finite) value of $N$ that works for all irreducible Markov chains. Let's back up: please include a complete, verbatim statement of the question in your post, so that we don't have to wonder whether something has been changed in translation. If your initial paragraph is indeed accurate, this question is unanswerable because $N$ is undefined. $\endgroup$
    – whuber ♦
    Commented Mar 29, 2022 at 19:20

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.