[Math] How to create a transition matrix that will guarantee an outcome after infinite transitions

markov chainsmatricesprobability

Let's assume we have the a transition matrix like:

0   0   0
1   2   0
2   4   0
3   6   0
4   7   2
5   9   3
6   6   6
7   7   7
8   8   8
9   9   9

First column is the current state, second and third are possible outcomes with 50% chance each.

As you can see there are "stop states" where you cannot escape once you hit them.

You start at a specific point, so the distribution vector will be like:

u = {0, 0, 1, 0, 0, 0, 0, 0, 0, 0} i.e. start at 2

My question is; is there a way to create a matrix like this that guarantees a specific state after an infinite number of transitions.

For example given that the starting state is 3, which transition matrix will guarantee that the end state will be 4 after an infinite number of transitions?

Or better, guarantee a specific ending state whatever your starting state is. Obviously I can just make all starting state go to the wanted outcome directly, but that's not what I want. I want the probabilities to get closer and closer to the outcome over time i.e. guarantee the outcome after infinite transitions.

All I can think of is that I need to create a matrix that will have each row converging to all zeroes except one column, when that matrix is infinitely multiplied by itself m^inf

Edit: I tried to make my question clearer, sorry I'm just a monkey after all.

Best Answer

This should happen if and only if there is exactly one sink (a state that goes only to itself), and there is a path from any state to the sink.

It's clear that if your state transition graph is not of this form that the graph doesn't have the property you seek.

When it does have this form, there is an easy to see the limiting probabilities are a distribution guaranteeing you're in the sink: choose N and p so that every state has a path of length less than N to the sink with probability greater than p. Then after kN iterations, you've had at least k chances to follow a path leading to the sink; so the odds that you aren't in the sink is less than $(1-p)^k$; this probability converges to zero as $k \to \infty$.

Related Question