1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – fred Feb 10 '15 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.