# Markov Chain with heterogeneous transitions

I have a Markov chain as follows:

• $G+1$ finite states, it begins from $s=G$ and completes at $s=0$
• A transition ($s\to s-1$) occurs in case if event $A$ happens. No other form of transition is possible. Denote the transition probabilities by $P_{ij}^{A}$

We want to improve this system to complete faster. So I devised a set of operations denoted by $B$. If $B$ is successful with probability $\beta$, it is just like $A$ is repeated $k$ times, where $k$ is a random variable with known probability. Otherwise, another [real] $A$ should happen to change the state (with probability 1-$\alpha$). Any advise on how to model the Markov chain of the improved system using on $P_{ij}^A$ is appreciated.

If I understand you correctly, you can just compute the transition probability for $k$-step, like in the case $k=2$ replace the transition probability:

$\mbox{Pr}(s \to s) = \alpha$

$\mbox{Pr}(s \to s-1) = 1-\alpha$

into

$\mbox{Pr}(s \to s) = \alpha^2$

$\mbox{Pr}(s \to s-1) = 2 \alpha (1-\alpha)$

$\mbox{Pr}(s \to s-2) = (1-\alpha)^2$

for $s \neq 0,1$.

Consider the case for $k=2$,

Your original transition matrix should look like:

$P^A = \begin{bmatrix} \alpha & 1 - \alpha & 0 & \cdots & 0 \\ 0 & a & 1 - \alpha & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \alpha & 1 - \alpha \\ 0 & 0 & 0 & \cdots & 1 \end{bmatrix}$

and will become:

$\begin{bmatrix} \alpha^2 & 2(1 - \alpha)\alpha & {(1-\alpha)}^2 & 0 & \cdots & 0 \\ 0 & \alpha^2 & 2(1 - \alpha)\alpha & {(1-\alpha)}^2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \alpha^2 & 2(1 - \alpha)\alpha & (1 - \alpha)^2 \\ 0 & 0 & 0 & 0 & \alpha & 1 - \alpha \\ 0 & 0 & 0 & 0 & \cdots & 1 \end{bmatrix}$

But what is the point of doing this?

• Is it correct to write $P^B=\sum_{k=1}^{K}{P(k).(P^A)^k}$? Then we have a new transition matrix that is $\beta P^B+(1-\beta)P^A$. The justification is that still $B$ may fail and we need an extra $A$. – fred Feb 10 '15 at 16:10