theorem in markov chains theory, intuition

26 Views Asked by At

There is a theorem which states:

If $(X_n)$ is irreducible, aperiodic markov chain, then there exist $N$ such that for all $i,j$ and $n>N$ $p_{i,j}(n)>0$. So with non zero probability we can go from $i$ to $j$ in exactly $n$ steps.

What is intuition here? Can we formulate general strategy how to move in order to get from $i$ to $j$ in exactly $n$ steps when $N$ is uniformly chosen?

1

There are 1 best solutions below

0
On

You ask for intuition, but I think there is no intuition to be found. This particular example I give illustrates exactly how counterintuitive this problem can be.

Consider the following Markov chain. There is a particular node, $x$. The entire chain is a union of $k$ cycles, where all of the cycles pass through the node $x$; otherwise, the cycles have no nodes in common. There are integers $c_1,\dots,c_k$, such that the $i^\text{th}$ cycle has exactly $c_i$ nodes, including $x$. Starting from the $x$ node, there is an equal probability of moving to the next node in any of the $k$ cycles. Thereafter, assuming the chain enters the $i^\text{th}$ cycle, the chain will always make $c_i-1$ moves which go around the cycle, returning to $x$.

Let's say that you want to answer the question of determining whether or not $p_{x,x}(n)>0$ or not. That is, can you move from $x$ to itself over the course of exactly $n$ steps? In order for this to be possible, we need to be able to express $N$ as a sum of copies of the cycle lengths $c_1,\dots,c_k$. Therefore, determining whether or not $p_{x,x}(n)>0$ is equivalent to the change making problem, asking whether or not you can make change for $n$ using coins with denominations $c_1,\dots,c_k$.

The change-making problem is NP hard. This shows that there is little hope of finding an intuitive solution for determining if $p_{x,x}(n)>0$. Furthermore, determining the smallest number $N$ such that $n>N$ implies $p_{x,x}(n)>0$ is equivalent to finding the Frobenius number of $(c_1,\dots,c_k)$. According to https://mathworld.wolfram.com/CoinProblem.html, there is no formula for the Frobenius number for $k > 4$.