1
$\begingroup$

One can think about a discrete-time Markov chain as a weighted directed graph $D = (V, E)$ where $E \subseteq V \times (0, 1]$, as each vertex represents a state, and an edge $(u, v)$ with weight $w$ would mean that one will change its current state from $u$ to $v$ with the probability $w$. We would no longer be able to get from our current state $x$ to the state $v$, if and only if there is no directed walk from the vertex $x$ to $v$.

Hence, my question is equivalent to the following: if the weight of all the edges of the digraph is rational, is the probability of reaching a vertex $x$ such that there is no directed walk from $x$ to $v$, necessarily a rational number?

For example, if both vertices $u$ and $v$ appear in the same strongly-connected components, the probability of such event being happened is 0, as there is always a walk from our current state to $v$.

$\endgroup$
2
  • $\begingroup$ For a given pair of vertices $(u,v)$, either you can get from $u$ to $v$ or you can't; there's no associated probability. Are you asking about the probability of reaching a vertex from $u$ from which $v$ is unreachable? Do you allow visiting $v$ before this happens? Are you assuming anything about the rationality of the transition weights? $\endgroup$
    – Karl
    Apr 1 at 21:50
  • $\begingroup$ @Karl The question is about "the probability of reaching a vertex $x$ such that there is no directed walk from $x$ to $v$", which is a probability that makes sense, though I agree that the title is a bad summary. $\endgroup$ Apr 2 at 3:50

1 Answer 1

2
$\begingroup$

If the transition probabilities are all rational, and the Markov chain is finite, then essentially all probabilities describing the Markov chain's behavior will also be rational, and that extends to this one.

Let $q(u,v)$ be the desired probability that from vertex $u$ we eventually reach a vertex $x$ from which we cannot get to $v$.

  1. First, set $q(u,v)=1$ for every $u$ from which we already cannot reach $v$. (If there are no such vertices, then in fact $q(u,v)=0$ for all $u$, and we're done.)
  2. Second, set $q(u,v)=0$ for every $u$ from which we cannot reach any $x$ with $q(x,v)=1$. (If there are no such vertices, then in fact $q(u,v)=1$ for all $u$, and we're done.)

Note that if we found any vertices $u$ for which we set $q(u,v)=0$, then in particular $q(v,v)=0$.

Every remaining vertex with an unassigned $q$-value should satisfy the equation $$q(u,v) = \sum_{w} p(u,w) q(w,v).$$ This is a system of linear inequalities we can solve to find the remaining probabilities. It has a unique solution by the maximum principle for harmonic functions, and the solution to a linear system with rational coefficients is itself rational.


If transition probabilities are not rational, then of course there is no reason to expect a rational answer here.

Also, if there are infinitely many states, then we can simulate having irrational probabilities, and so we cannot expect a rational answer. Here's an example. To prepare, pick your favorite irrational number $\alpha \in (0,1)$, and write it in binary as $\alpha = 0.b_1b_2b_3b_4\dots$

Our Markov chain here will have states $\{1,2,3,4,5,\dots\} \cup \{v,w\}$. States $v$ and $w$ are absorbing states. For the rest, we let state $i$ have:

  • A transition to $i+1$ with probability $\frac12$.
  • If $b_i=0$, a transition to $v$ with probability $\frac12$.
  • If $b_i=1$, a transition to $w$ with probability $\frac12$.

This is cooked up so that $q(1,v)$ is exactly $\alpha$. Here's why.

With probability $1$, we eventually arrive at $v$ or $w$ and stay there, so $q(1,v)$ is the probability we arrive at $w$ rather than $v$. For each $i$ such that $b_i = 1$, there is a probability of $(\frac12)^i$ that we'll travel $1 \to 2 \to \dots \to i \to w$, and these describe all the ways to arrive to $w$ from $1$.

We can rephrase this as saying that there is a probability of $\frac{b_i}{2^i}$ of arriving $w$ for every $i$ (which simplifies to $(\frac12)^i$ if $b_i=1$ and to $0$ otherwise). Then the total probability of arriving at $w$ is $$\sum_{i=1}^\infty \frac{b_i}{2^i}$$ which is exactly $\alpha$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .