# Discrete time Markov chain, help needed!

A machine consists of $K$ components in series, i.e., all the components must be in working condition for the machine to be functional. When the machine is functional at the beginning of the $n$th day, each component has a probability $p$ of failing at the beginning of the next day, independent of other components. (More than one component can fail at the same time).

When the machine fails, a single repair person repairs the failed components one by one. It takes exactly one day to repair one failed component. When all the failed components are repaired the machine is functional again, and behaves as before. When the machine is down, the working components do not fail.

Let $X_n$ be the number of failed components at the beginning of the $n$th day, after all the failure and repair events at that time are accounted for. Show that $\{X_n, n>0\}$ is a Discrete time Markov chain. Display the transition matrix or the transition diagram.

I don't know how to start this problem. I didn't understand the problem.

• Assuming $n$ components work on a given day, what is the distribution of the number that fail that day? This will give you most of the information about the transition matrix. – Ian Aug 12 '16 at 3:37
• Is the number n<K here ? – papabiceps Aug 12 '16 at 3:39
• I intend $n \leq K$, yes. – Ian Aug 12 '16 at 3:48
• @Ian, I have been trying this problem, but failed to understand it. Can you elaborate it? – papabiceps Aug 12 '16 at 12:41
• So there are $K+1$ states depending on how many components are functional. When $K$ components function, Binomial($K,p$) components fail. In other words you go from $X_n=K$ to $X_{n+1}=K-B$ where $B \sim$ Binomial($K,p$). Otherwise one component is repaired, so you go from $X_n=a$ to $X_{n+1}=a+1$. (Sorry about my first comment, I missed the "components do not fail when the machine is down" statement.) – Ian Aug 13 '16 at 0:58

Here we have $$X_{n+1} = \begin{cases} X_n + 1,& 1\leqslant X_n< K\\ V_{n+1}, & X_n = K, \end{cases}$$ where the sequence $\{V_n:n=1,2,\ldots\}$ is independent with $\operatorname{Bin}(K,1-p)$ distribution. Since $X_{n+1} = f(X_n, V_{n+1})$ where $V_{n+1}$ is independent of the $X_n$, we readily see that $\{X_n:n=0,1,\ldots\}$ satisfies the Markov property. The transition probabilities are given by $$p_{ij} = \begin{cases} 1,& j=i+1,\ 0<i<K\\ \binom K {j-1} (1-p)^{j-1} p^{K-j+1},& i=K,\ 0<j<i\\ (1-p)^K + K(1-p)^{K-1}p,& i=j=K. \end{cases}$$ The subtlety here is that there are two ways the system can transition from $i$ to $j$ - either there are no failures, or there is exactly one failure (in which case it is repaired in that same period).