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?