Markov chains and production line comprising 3 machines

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

 

[Orodruin]

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.

 

[berkeman]

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.

 

[Orodruin]

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)

 

[Orodruin]

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.

 

[berkeman]

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,

Please read the Wikipedia link that I provided. Also, please review your study materials about how to sketch and use Markov chains.

 

[berkeman]

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

 

[Orodruin]

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.

 

[Joe1998]

Please read the Wikipedia link that I provided. Also, please review your study materials about how to sketch and use Markov chains.

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.

 

[PeroK]

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!

 

[Orodruin]

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

 

[PeroK]

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.

 

[Orodruin]

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.

 

[haruspex]

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.

 

[PeroK]

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.

 

[Orodruin]

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.

 

[Orodruin]

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.

 

[PeroK]

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?

 

[Steve4Physics]

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

Post your answer to part a) so we can see it.

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.

 

[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[00] to P[33], where P[00] = q^3 (if I am not wrong) and P[33] = p^3 (again ,if I am not wrong. But given we have 3 machines, how can I determine, for example, P[10], P[01] and P[13]?

 

[PeroK]

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[00] to P[33], where P[00] = q^3 (if I am not wrong) and P[33] = p^3 (again ,if I am not wrong. But given we have 3 machines, how can I determine, for example, P[10], P[01] and P[13]?

By $P[10]$ 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?

 

[PeroK]

By $P[10]$ 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.

 

[PeroK]

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.

 

[PeroK]

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.

 

[Orodruin]

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

 

[Steve4Physics]

P[00] = 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.

 

[haruspex]

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.

 

[Orodruin]

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

 

[haruspex]

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?

 

[Orodruin]

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.

 

[Orodruin]

But the lost info is easily recovered after solving, no?

No. Even if you know the exact sequence realized you cannot recover the information. Let's say you have the following sequence of broken machines in the morning: 100210. You cannot know whether the repair man had to work the night between day 2 and 3 as you have the transition 0->0. Either one machine broke on the second day or none did, but we have no way of knowing which based on only that information.

Edit: However, you can probably still figure out how much to pay the repair man on average (if you know the probabilities - if you have to figure out the probabilities you must estimate them from data and you can only do that without error if you have an infinite realization).