# Multistep Markov Chain Problem

Let's say there is a machine whose condition at the start of every week can be modeled by a Markov Chain and the condition can be categorized as low, medium, high, failed. I will denote the state of the machine as $$X$$ where $$X_n$$ is the state at the start of week $$n$$. The transition matrix $$P$$ is as follows (the order is low, medium, high, failed):

$$\begin{bmatrix}0.9 & 0.05 & 0.03 & 0.02\\0 & 0.85 & 0.09 & 0.06\\0 & 0 & 0.9 & 0.1\\1 & 0 & 0 & 0\end{bmatrix}$$

For instance, a machine in the medium state has a probability of 0.09 and 0.06 of being in the high or failed state, respectively, at the start of the next week (it cannot, by itself, go to the low state).

My questions are

1. What is the probability that a machine has at least one failure three weeks after it is new?
2. On average, how many weeks per year is the machine working?

Just in case you need the multistep transition matrices, I have calculated second-step and third-step matrices in python:

matrix([[0.83  , 0.0875, 0.0585, 0.024 ],
[0.06  , 0.7225, 0.1575, 0.06  ],
[0.1   , 0.    , 0.81  , 0.09  ],
[0.9   , 0.05  , 0.03  , 0.02  ]])

matrix([[0.771   , 0.115875, 0.085425, 0.0277  ],
[0.114   , 0.617125, 0.208575, 0.0603  ],
[0.18    , 0.005   , 0.732   , 0.083   ],
[0.83    , 0.0875  , 0.0585  , 0.024   ]])

• @Stijn Although that's a good characterization of the English statement of the problem, notice that the transition matrix as given has no absorbing state.
– whuber
Commented Nov 5, 2020 at 15:34
• @StijnDeVuyst self-study tag added and I agree with whuber that the machine doesn't get stuck in the failed state and it just gets "fixed" and goes back to the low state. Commented Nov 5, 2020 at 16:59
• @whuber: sorry I was too fast with the comment. You are right, it is NOT an absorbing chain and all states communicate with each other. My mistake. Commented Nov 5, 2020 at 17:09
• @StijnDeVuyst Do you know how I can get started with the first problem? Commented Nov 5, 2020 at 17:44
• For the first question, you will need to compute the so-called first-passage time distribution from state 1 (low) to state 4 (failed). The asked probability is $f_{14}^{(1)}+f_{14}^{(2)}+f_{14}^{(3)}$ where $f_{14}^{(n)}$ is the probability that the machine will be in state 4 in week $n$ for the first time. There is a recursive set of equations that will give you these probabilities. The second question is easier: this is the sum of equilibrium probabilities that the machine is in state 1, 2 or 3. These follow by solving the set of equilibrium equations. Commented Nov 5, 2020 at 18:20

Let us call $$T_{14}$$ the first-passage time from state 1 to state 4. If the chain starts in $$X_0=1$$, then $$T_{14}$$ is the number of steps until the chain reaches state 4 for the first time. That means for $$n>0$$ that $$T_{14}=n$$ if and only if $$X_0=1$$, $$X_1\neq 4$$, ..., $$X_{n-1}\neq 4$$ and finally $$X_n=4$$. Let the distribution of this first-passage time $$T_{14}$$ be given by the probabilities $$f_{14}^{(n)} = \text{Prob}[T_{14}=n]\,, n>0\,,$$ which can be computed recursively by conditioning on the first step $$X_1$$. That is, $$f_{14}^{(n)} = \sum_{k\in\{1,2,3\}} p_{1k} f_{k4}^{(n-1)}$$ where $$p_{ij}$$ are the transition probabilities in the matrix $$\mathbf{P}$$ given in the original post. Particularly note that transitions to the failed state 4 are not counted here because we only consider the event where that happens for the first time at time step $$n$$ and not before. Starting from $$f_{k4}^{(1)}=p_{k4}$$, $$k\in\{1,2,3,4\}$$, these probabilities can be computed up to whatever time step $$n$$ you need. For a full explanation on first-passage times and how their distribution can recursively be computed, see for example here.

Now, your first question asks: what is the probability that the machine fails in the first three weeks if it starts as new? This happens if and only if $$T_{14}\leqslant 3$$, so $$\text{Prob}[T_{14}\leqslant 3] = f_{14}^{(1)} + f_{14}^{(2)} + f_{14}^{(3)}$$ My R-code for doing this gives 0.0713:

P <- matrix(c(0.9,0.05,0.03,0.02,
0,  0.85,0.09,0.06,
0,  0,   0.9, 0.1,
1,  0,   0,   0    ),4,4,byrow=TRUE)
N <- 3          # number of weeks
fto4 <- matrix(rep(0,9),3,N)
fto4[,1] <- P[1:3,4]
for (n in 2:N) {
for (i in 1:3) {
fto4[i,n] <- P[i,1:3] %*% fto4[1:3,n-1]
}
}
sum(fto4[1,])   ## 0.0713


The following does a Monte Carlo estimation of that probability using $$10^7$$ replications and gives a 95%-confidence interval:

R <- 10000000   # number of replications in MC simulation
count <- 0
for (r in 1:R) {
X <- c(1,rep(0,N))   # state of machine in subsequent weeks
for (n in 1:N) { X[n+1] <- sample(1:4,1,prob=P[X[n],]) }
if (max(X)==4) {count <- count+1}   # count if there was a failure in N weeks
}
fail.MC <- count/R
CI <- fail.MC + qnorm(0.975)*sqrt(fail.MC*(1-fail.MC)/R)*c(-1,+1); CI
## CI is [0.07119456,0.07151364]


The following is how this is computed in the answer of user295357:

p0 <- matrix(c(1,0,0,0),1,4)
p1 <- p0 %*% P
p2 <- p1 %*% P
p3 <- p2 %*% P
1-(1-p1[1,4])*(1-p2[1,4])*(1-p3[1,4])  ## 0.0700145


This is admittedly close but not the same. This value is also far outside the confidence interval given by the simulation.

I do however agree with the solution of the second question if you interpret that question as asking for the expected number of weeks of the first year in which the machine is working. In my opinion however, the question does not mention any particular year so it would be safe to assume it concerns a year during the steady-state (equilibrium) operation of the machine. That would be $$52(1-\pi_4)=49.44262$$.

For the second question: Define a row vector $$s$$ = [1 0 0 0] for the initial status. Calculate $$z_{i}=s\times P^i$$, where $$i$$ = 1, 2, ... up to 52 (since a year has 52 weeks), and $$P$$ is the transition matrix. Each of $$z_{i}$$ is a row vector of 4 elements. Denote the fourth element of $$z_{i}$$ as $$z_{i}(4)$$. The average number of weeks in a year the machine works is $$n = 52-\sum_{i=1}^{52} z_i(4)$$.

• Thanks for the answer! I agree with you in regard to the first question but for the second one, don't you think we actually need to calculate the steady-state behavior of the system? Commented Nov 6, 2020 at 4:59
• Since this Markov Chain is an irreducible and recurrent set, I will have a vector $m$ and set it to $mP = m$ where $P$ is the transition matrix and solve the set of equilibrium equations. What do you think about this way? Commented Nov 6, 2020 at 5:11
• @Jasonli1997: You can easily find the probabilities of steady state, denoted as $m$, such that $mP=m$. However, I cannot see how is this steady state related to your second question. Among the 52 weeks of a year, the probabilities in the first multiple weeks are quite different from those of the steady state. To get the average number of working weeks, I think we should "average" them over all 52 weeks. Commented Nov 6, 2020 at 20:36
• @Jasonli1997: Let me explain a little bit more. It can be verified that the probabilities of stead state is $m$ = [0.4918 0.1639 0.2951 0.0492]. So the failure probability of steady state is 0.0492. If this is true for all of the 52 weeks in a year, then the average number of weeks that the machine fails to work is 52*0.0492. However, in most of the 52 weeks, the failure probability is less then 0.0492. For instance, $z_{1}(4)$ = 0.02; $z_{2}(4)$ = 0.024; .... Thus, what we should do is to add $z_{i}(4)$ together for $i$ from 1 up to 52 to get the average number of weeks of failure. Commented Nov 7, 2020 at 1:41
• Yeah that makes sense @user295357 thank you Commented Nov 7, 2020 at 5:19