# Markov chains and production line comprising 3 machines

• Joe1998
Joe1998
Homework Statement
A production line comprises three machines working independently of each other. For each machine, the probability of working through the day is p ∈ (0, 1) and may breakdown during a day with probability q = 1 − p, independently of its previous history. There is a single repairman who, if he has to, repairs exactly one machine overnight. If there is a machine not working by the end of the day, then the repairman works during the night. Let Xn denote the number of working machines at the end of day before the repairman begins any over-night repair.

a-) Specify the state space of (Xn : n ≥ 0).

b-) Determine the transition matrix in terms of p.

c-) Given that 2 machines are idle tonight, what is the probability of one idle machine 3 nights later, if p = 0.8 (answer 6 decimal places).
Relevant Equations
Markov chain and probability transition matrix are mainly the two relevant equations required for this question.
I have tried solving this question, but I am not even sure where to start from and how to specify a state space for this question where it has a trick stating that a worker works overnight. However, for part a, is it the case that there are only 2 states to consider which are: {machine working, machine not working}
part b-) I am very unsure, so I don't want to type some gibberish. I mean I am not even sure if the state space is indeed only 2 states or more, so that's why I am unsure about all parts because I am not sure about part (a) in the first place.
Same story with part c, I am not able to solve it unless I get the first two parts correct.
So I would really appreciate any help here, thank you very much.

Last edited:
• Delta2

Staff Emeritus
Homework Helper
Gold Member
Please show us what you have done and what your thoughts are.

Joe1998
So the problem is that I am not even knowing the answer for the questions to show you what I have done. Regarding my thoughts, for part a, is it the case that there are only 2 states to consider which are: {machine working, machine not working}
part b-) I am very unsure, so I don't want to type some gibberish. I mean I am not even sure if the state space is indeed only 2 states or more, so that's why I am unsure about all parts because I am not sure about part (a) in the first place.
Same story with part c, I am not able to solve it unless I get the first two parts correct.
So I would really appreciate any help here, thank you very much.

Mentor
for part a, is it the case that there are only 2 states to consider which are: {machine working, machine not working}
I don't think so. It sounds like anyone of the machines failing takes the whole production line down for the rest of the day. So you have different states for different numbers of failing machines. Can you sketch the Markov Chain diagram for those different states, and indicate what the transition probability is for each transition for one day?

https://en.wikipedia.org/wiki/Markov_chain

Joe1998
Thanks for the reply Berkeman, basically you are asking me if I can do it, when in reality the reason I am asking for help is because I am not even sure how to sketch the diagram and indicate the transition probability for each transition for one day, I am just so confused about it, so any help with that would be appreciate it, thanks.

Staff Emeritus
Homework Helper
Gold Member
Regarding my thoughts, for part a, is it the case that there are only 2 states to consider which are: {machine working, machine not working}
That’s for each machine. What are the possible relevant states for all machines? (Also seeing that all machines are equivalent and independent)

Staff Emeritus
Homework Helper
Gold Member
It sounds like anyone of the machines failing takes the whole production line down for the rest of the day
I don’t think it is that explicit. It could be interpreted that way, but I am not certain it is the intent of the question writer. I see two possible interpretations:

1) if there are broken machines at the beginning of the day then they will all be switched off because the production line is broken. No machines will break on such a day.

2) If a machine is broken at the beginning of a day, the others will still work and may break during the day.

These will of course give different results but the state space should be the same.

• PeroK and berkeman
Mentor
when in reality the reason I am asking for help is because I am not even sure how to sketch the diagram and indicate the transition probability for each transition for one day,

Mentor
I don’t think it is that explicit. It could be interpreted that way, but I am not certain it is the intent of the question writer. I see two possible interpretations:
Hmm, I see your point. When I think of a "production line", I picture a series of operations that rely on each other to build the product. But the problem statement included "working independently", so perhaps the production "line" is actually 3 parallel lines when it gets to the machine area...

Staff Emeritus
Homework Helper
Gold Member
Hmm, I see your point. When I think of a "production line", I picture a series of operations that rely on each other to build the product. But the problem statement included "working independently", so perhaps the production "line" is actually 3 parallel lines when it gets to the machine area...
That is how I read it at first. I did not see the other interpretation until you mentioned it ... it just kind of underlines that the question is a bit vague.

• berkeman
Joe1998
The Wikipedia and lecture materials are helpful, but I still can't solve the problem. I mean if my lecture material were helpful enough for me to solve the question then I would have done so without posting it here, but I simply am not knowing to solve even after reviewing my lecture notes very well, so if anyone knows how to answer the question then that would be appreciated.

Homework Helper
Gold Member
2022 Award
The Wikipedia and lecture materials are helpful, but I still can't solve the problem. I mean if my lecture material were helpful enough for me to solve the question then I would have done so without posting it here, but I simply am not knowing to solve even after reviewing my lecture notes very well, so if anyone knows how to answer the question then that would be appreciated.
I can't really see the problem in getting started. At the end of each day there are clearly four possible states:

All three machines kaput; two machines kaput; one machine kaput; and, all machines working.

Given the repairman fixes precisely one machine overnight, then there is one fewer machine not working the next morning.

I can't see what's conceptually problematic about that.

I have no idea what a transition marix is, but I'm sure (with the resources of the Internet at my disposal) I could find out quickly enough.

For part c) you can just plough through the probabilities a day at a time (*). Although, I suspect the transition matrix gives you a quick way to do this.

(*) E.g. start with two machines out which means one the next morning. At the end of day one:

Probability that all three machines are out = ##p^2##

Probability that two machines are out is ##2p(1-p)##

Probability that one machine is out is ##(1-p)^2##

Get yourself an sheet of A4 paper and do two more days of that!

Staff Emeritus
Homework Helper
Gold Member
Get yourself an sheet of A4 paper and do two more days of that!
The entire point of the transition matrix is to not have to do that but do matrix multiplication instead ...

• Klystron and PeroK
Homework Helper
Gold Member
2022 Award
The entire point of the transition matrix is to not have to do that but do matrix multiplication instead ...
Yeah, I think I can guess what it is and how it works.

Staff Emeritus
Homework Helper
Gold Member
Yeah, I think I can guess what it is and how it works.
I would think that you can, yes. It is a rather nice construction though and you can get a lot of information about the Markov chain out of analysing it.

Homework Helper
Gold Member
2022 Award
These will of course give different results but the state space should be the same.
If one stopped machine will protects all others from failure, Xn would only be 2 or 3. If it would only protect the downstream ones, the state space would care about which machine failed.
So I think we have to suppose that the others keep running and so may still fail the same day. That makes it immaterial, for the purpose of the question, whether they are in series or parallel.
I have no idea what a transition marix is
As you probably guessed, it is the matrix of probabilities, ##M=(p_{ij})##, of changing from state j to state i (the prior states being the columns). If the probabilities of the current state are given by the vector X then those for the next state are given by MX.
Typically we care about long term behaviour, so individual multiplications by M become tedious. Instead, we diagonalise M. But here we only go up to three iterations.

Homework Helper
Gold Member
2022 Award
If one stopped machine will protects all others from failure, Xn would only be 2 or 3.
That assumption is not in the question. I would assume three independent production lines.

Staff Emeritus
Homework Helper
Gold Member
If one stopped machine will protects all others from failure, Xn would only be 2 or 3.
Well, that assumes that no two machines can break on the same day. In the scenario I was envisioning, the machines would still break independently, but the entire production line would not be started if any machine is broken in the morning, thus only protecting the other machines from breaking if there is a machine that is not working at the beginning of the day - not if it breaks during the day's operation. Otherwise the breaking of the machines would not be independent. Hence, the state space would be {0, 1, 2, 3} because all machines could break on the same day. However, this situation is definitely different from the situation when the machines are always started in the morning if not broken, regardless of whether any other machine is broken.

Staff Emeritus
Homework Helper
Gold Member
That assumption is not in the question. I would assume three independent production lines.
That was my assumption too but, as @berkeman pointed out, the question does say "A production line comprises three machines", implying a single production line with three machines.

Homework Helper
Gold Member
2022 Award
That was my assumption too but, as @berkeman pointed out, the question does say "A production line comprises three machines", implying a single production line with three machines.
Yes, it's not clear. If ##p= 0.8## then that looks like a fairly disastrous manufacturing operation. Perhaps it's based on British industry in the 1970's?

• Klystron, berkeman, Steve4Physics and 1 other person
Homework Helper
Gold Member
2022 Award
@Joe1998, maybe this will get you started without (I hope) telling you too much.

a) As has already noted by @PeroK, there are four (not two) possible states of the system, corresponding to the four possible values of ##X_n##.

E.g. one of the states, which we can call ##X_2##, corresponds to n=2, i.e. two machines working.

The ‘state space’ is simply a list all the possible states. If some particular format is required (e.g. set notation), you will need to check your notes to find the required format.

b) A Markov chain (diagram) will show the four states with arrows and associated probabilities.

I would draw two Markov chains. The first is to show the possible changes during the daytime (i.e. fault conditions arising). You will need to work out the probability for each arrow in terms of ‘p’s.

The second Markov chain will show any overnight repair.

You should then be able to construct a transition matrix for each chain. Their matrix product (which matrix comes first?) gives the overall transition matrix, which is what you need for part c).

If you post your work here I’m sure you will get further help.

• WWGD and PeroK
Joe1998
I can't really see the problem in getting started. At the end of each day there are clearly four possible states:

All three machines kaput; two machines kaput; one machine kaput; and, all machines working.

Given the repairman fixes precisely one machine overnight, then there is one fewer machine not working the next morning.

I can't see what's conceptually problematic about that.

I have no idea what a transition marix is, but I'm sure (with the resources of the Internet at my disposal) I could find out quickly enough.

For part c) you can just plough through the probabilities a day at a time (*). Although, I suspect the transition matrix gives you a quick way to do this.

(*) E.g. start with two machines out which means one the next morning. At the end of day one:

Probability that all three machines are out = ##p^2##

Probability that two machines are out is ##2p(1-p)##

Probability that one machine is out is ##(1-p)^2##

What do you mean by "Given the repairman fixes precisely..."? If the repairman fixes it overnight, then shouldn't the machine be ready the next morning?

Get yourself an sheet of A4 paper and do two more days of that!

Joe1998
I can't really see the problem in getting started. At the end of each day there are clearly four possible states:

All three machines kaput; two machines kaput; one machine kaput; and, all machines working.

Given the repairman fixes precisely one machine overnight, then there is one fewer machine not working the next morning.

I can't see what's conceptually problematic about that.

I have no idea what a transition marix is, but I'm sure (with the resources of the Internet at my disposal) I could find out quickly enough.

For part c) you can just plough through the probabilities a day at a time (*). Although, I suspect the transition matrix gives you a quick way to do this.

(*) E.g. start with two machines out which means one the next morning. At the end of day one:

Probability that all three machines are out = ##p^2##

Probability that two machines are out is ##2p(1-p)##

Probability that one machine is out is ##(1-p)^2##

Get yourself an sheet of A4 paper and do two more days of that!

Joe1998
So after thinking about it. The state space is {0,1,2,3} where 0 indicates that 0 machine is working, 1 indicates that 1 machine is working and so on. Now, the struggle is with part b, we have a transition matrix that contains all the entries from P to P, where P = q^3 (if I am not wrong) and P = p^3 (again ,if I am not wrong. But given we have 3 machines, how can I determine, for example, P, P and P?

Homework Helper
Gold Member
2022 Award
So after thinking about it. The state space is {0,1,2,3} where 0 indicates that 0 machine is working, 1 indicates that 1 machine is working and so on. Now, the struggle is with part b, we have a transition matrix that contains all the entries from P to P, where P = q^3 (if I am not wrong) and P = p^3 (again ,if I am not wrong. But given we have 3 machines, how can I determine, for example, P, P and P?
By ##P## do you mean the probability of going from 1 machine working at the start of the day to zero machines working at the end of the day?

Homework Helper
Gold Member
2022 Award
By ##P## do you mean the probability of going from 1 machine working at the start of the day to zero machines working at the end of the day?
I just re-read the question. I guess that's going from 1 machine working at the end of the day to zero machines working at the end of the next day.

Homework Helper
Gold Member
2022 Award
Just a thought. Given that one machine is definitely repaired every night (if needed), then analysing the problem from morning to morning would seem simpler and more logical. We would have only three states, as there would be no option to have zero machines working.

I guess you have to do the problem as stated. From a practical point of view, it's the number of machines working at the start of the day that is of most operational interest, I would say.

• Klystron
Homework Helper
Gold Member
2022 Award
I wrote a Python script to do the matrix multiplication. So, I have an answer for part c) if you want to post what you get.

Staff Emeritus
Homework Helper
Gold Member
then analysing the problem from morning to morning would seem simpler and more logical.
Not if you want to know how much to pay the repair man. While it may be simpler to analyse, it does throw away information (if there are zero machines broken two mornings in a row, you will not know if the repair man has worked through the night in between).

Homework Helper
Gold Member
2022 Award
P = q^3
q³ is the probability of all three machines breaking down during a day, i.e. a state change of 3→0, not 0→0.

Your first task is to decide (and clearly state) over what time-period (T) your Markov chain (and its associated transition matrix) applies. The start and end times must be unambiguous or things will get confused. E.g. you could choose:
a) start of working day to start of next working day, or
b) end of working day to end of next working day.

Or you might want to consider using two time-periods: working-period (daytime) and repair-period (nightime) and having a Markov chain/transition matrix for each, as suggested in Post #21.

Also, your should draw the Markov chain before the matrix.

• Klystron
Homework Helper
Gold Member
2022 Award
While it may be simpler to analyse, it does throw away information (if there are zero machines broken two mornings in a row, you will not know if the repair man has worked through the night in between).
The analysis and the resulting matrix are exactly the same. The difference is the state space. In one case the number working is 0, 1 or 2, while in the other it is 1, 2 or 3.
@Joe1998, a useful check is that each column of the matrix should add to 1.
Please post the matrix you get. It will be easier to write using both p and q rather than all in terms of p.

Staff Emeritus
Homework Helper
Gold Member
The analysis and the resulting matrix are exactly the same. The difference is the state space. In one case the number working is 0, 1 or 2, while in the other it is 1, 2 or 3.
This is not correct. In the case of checking how many machines are broken in the evening, it can be 0, 1, 2, or 3. If checking in the morning, it can be 0, 1, or 2. In the first case, the repair man needs to work through the night if the state is not zero. In the second, we do not know if the repair man had to work through the night if the state is zero.

Edit: Effectively, the night work is a deterministic process that just changes the state space by merging two states (0 and 1 broken -> 0) and relabeling the other two (2->1 and 3->2).

Homework Helper
Gold Member
2022 Award
This is not correct. In the case of checking how many machines are broken in the evening, it can be 0, 1, 2, or 3. If checking in the morning, it can be 0, 1, or 2. In the first case, the repair man needs to work through the night if the state is not zero. In the second, we do not know if the repair man had to work through the night if the state is zero.
Whoops - thanks. The last two columns are identical for p.m., so I guess I am agreeing with @PeroK that a.m. is simpler to analyse and with you about lost info. But the lost info is easily recovered after solving, no?

Last edited:
Staff Emeritus
Homework Helper
Gold Member
Typically we care about long term behaviour, so individual multiplications by M become tedious. Instead, we diagonalise M. But here we only go up to three iterations.
Just to mention for the OP, a typical such question would be how often the repair man would have to work through the night on average in the long term. This may be worth thinking about later, but solve the present problem first.
As you probably guessed, it is the matrix of probabilities, M=(pij), of changing from state j to state i (the prior states being the columns). If the probabilities of the current state are given by the vector X then those for the next state are given by MX.
I think it is also worth noting that some texts will use the transposed definition of the above one (i.e., the element pij being the probabilty of going from state i to state j). With that definition, the state vector X is instead a row vector and is multiplied from the right by the transition matrix. I believe this notation is more common among mathematicians, but I may be wrong. Both notations work and are just each other's transpose of course, but it may be relevant to iron out some confusions.

Staff Emeritus