Multistep Markov Chain Problem

Question

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   ]])

Answer 1

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$.

Answer 2

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)$.