Markov chains and production line comprising 3 machines

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

 

[haruspex]

No. Even if you know the exact sequence realized you cannot recover the information

I meant that if you use the a.m. analysis to find the probability distribution at the start of day n then it is easy to find the distribution at the end of day n.

 

[Joe1998]

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.

Thanks for the reply. So if I choose option b, from end to end working day "BEFORE" the repairman begins any over-night repair. Also, there is no way I can know how to draw the Markov Chain before figuring out the transition matrix, because I draw it by deriving the values from the transition matrix entries.

Regarding P[00], that's what I am struggling with. I mean if we start with 0 machines working by the end of the day and then we end up still with 0 working machines in the next working day, then how is that even represented? I mean does that mean we haven't started any machine and therefore the value would just be 0? Or does it mean we end up with 0 working machines by the end of the first day and then with 0 working machines by the end of the next day? If it is the latter, then does it mean q^3 or is that P[30] again? Yeah, so I am struggling with knowing what value does it take when we start with 0 working machine, and even worse ending up in a state of 0 working machines? Any help would be really appreciate it.

Regarding P[10], does that mean it starts with 1 working machine and ends up with zero working machines, thus it is equal to 1-p?

For P[01], again I am not sure at all what value does a "zero machine working by the end of the day" take here? is it just p here or something else?

 

[Joe1998]

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.

Yeah, once I figure out first the transition matrix, then I will post my answer for part c and compare it with yours. However, isn't it just P^2 (where P is the transition matrix here) and then plucking out P[21] from the new matrix? Or do we have to calculate P^3 (again, P is the transition matrix here) because it is 3 nights? thanks for your help by the way, I really appreciate it buddy!

 

[haruspex]

Thanks for the reply. So if I choose option b, from end to end working day "BEFORE" the repairman begins any over-night repair. Also, there is no way I can know how to draw the Markov Chain before figuring out the transition matrix, because I draw it by deriving the values from the transition matrix entries.

Regarding P[00], that's what I am struggling with. I mean if we start with 0 machines working by the end of the day and then we end up still with 0 working machines in the next working day, then how is that even represented? I mean does that mean we haven't started any machine and therefore the value would just be 0? Or does it mean we end up with 0 working machines by the end of the first day and then with 0 working machines by the end of the next day? If it is the latter, then does it mean q^3 or is that P[30] again? Yeah, so I am struggling with knowing what value does it take when we start with 0 working machine, and even worse ending up in a state of 0 working machines? Any help would be really appreciate it.

Regarding P[10], does that mean it starts with 1 working machine and ends up with zero working machines, thus it is equal to 1-p?

For P[01], again I am not sure at all what value does a "zero machine working by the end of the day" take here? is it just p here or something else?

To avoid getting confused, it might be better to start with two matrices, one for the change during the day and one for the change overnight. Assuming the columns represent the prior state, the first matrix has three columns (1, 2, 3) and four rows (0 to 3), while the second has four columns and three rows.
Armed with those, you can multiply them in one order to get the 3x3 a.m. to a.m. transition matrix or in the other order to get the 4x4 p.m. to p.m. matrix.

Wrt your question about P[00], if there are none working at the end of a day, how many will be working in the morning? How many might then be working at the end of that day, and with what probabilities?

 

[Joe1998]

To avoid getting confused, it might be better to start with two matrices, one for the change during the day and one for the change overnight. Assuming the columns represent the prior state, the first matrix has three columns (1, 2, 3) and four rows (0 to 3), while the second has four columns and three rows.
Armed with those, you can multiply them in one order to get the 3x3 a.m. to a.m. transition matrix or in the other order to get the 4x4 p.m. to p.m. matrix.

Wrt your question about P[00], if there are none working at the end of a day, how many will be working in the morning? How many might then be working at the end of that day, and with what probabilities?

Working with two matrices would complete things more for me. I mean it could be just way simpler to help me with P[00], P[10] and P[01] and I can figure out the rest by myself.
In regard to to P[00], if there are non working at the end of a day, then one must be working in the morning because the repairman fixes one overnight with a prob. of p. But then, that machine might break down during the day with prob. of q, so would that mean P[00] = pq?

 

[haruspex]

the repairman fixes one overnight with a prob. of p

With a probability of 1.

would that mean P[00] = pq?

No. There is exactly one working at the start of the day. What is the probability there is exactly one working at the end of the day?

Working with two matrices would complete things more for me.

I assume you meant "complicate", but you seem very confused and separating it into the two stages is likely to help with that.
If you are struggling with P[00], wait till you get to some later cases!

 

[Joe1998]

With a probability of 1.

No. There is exactly one working at the start of the day. What is the probability there is exactly one working at the end of the day? But why do we even need to know the prob. there is exactly one working at the end of the day when we are dealing with P[00]? I mean we are transitioning here from 0 machines working to 0 machines working, so if the prob. of a machine being repaired is 1, then in the morning we have 1 machine working but it has a prob. of breaking down of q, so P[00] = q*1 = q, right?

I assume you meant "complicate", but you seem very confused and separating it into the two stages is likely to help with that.

 

[haruspex]

Was there something you meant to add?

 

[Joe1998]

Was there something you meant to add?

Yeah I tried to reply to your message but didn't go through properly, so will type it again here.
You said "No. There is exactly one working at the start of the day. What is the probability there is exactly one working at the end of the day?". But why do we even need to know the prob. there is exactly one working at the end of the day when we are dealing with P[00]? I mean we are transitioning here from 0 machines working to 0 machines working, so if the prob. of a machine being repaired is 1, then in the morning we have 1 machine working but it has a prob. of breaking down of q, so P[00] = q*1 = q, right?

 

[haruspex]

why do we even need to know the prob. there is exactly one working at the end of the day when we are dealing with P[00]?

Yes, I should have asked for the probability it is not working at the end of the day.

P[00] = q*1 = q, right?

Right. Here's a tougher one: P[1,2]
(By which I mean transiting from 2 working to 1. Not sure how you are defining P[xy].)

 

[PeroK]

To avoid getting confused, it might be better to start with two matrices, one for the change during the day and one for the change overnight.

If we are starting at the end of a day with $\{0, 1, 2, 3 \}$ then the first step is start the next day with $\{1, 2, 3, 3 \}$. I didn't use a separate matrix for that.

 

[PeroK]

Yeah I tried to reply to your message but didn't go through properly, so will type it again here.
You said "No. There is exactly one working at the start of the day. What is the probability there is exactly one working at the end of the day?". But why do we even need to know the prob. there is exactly one working at the end of the day when we are dealing with P[00]? I mean we are transitioning here from 0 machines working to 0 machines working, so if the prob. of a machine being repaired is 1, then in the morning we have 1 machine working but it has a prob. of breaking down of q, so P[00] = q*1 = q, right?

Yes. To give you a start and some Latex, the first column of the transition matrix is:
$$T =
\begin{bmatrix}
q& \dots \\
p& \dots \\
0 & \dots \\
0 & \dots
\end{bmatrix}
$$

 

[PeroK]

Yeah, once I figure out first the transition matrix, then I will post my answer for part c and compare it with yours. However, isn't it just P^2 (where P is the transition matrix here) and then plucking out P[21] from the new matrix? Or do we have to calculate P^3 (again, P is the transition matrix here) because it is 3 nights? thanks for your help by the way, I really appreciate it buddy!

Three nights later means computing $P^3$, which gets messy.

 

[Joe1998]

Yes. To give you a start and some Latex, the first column of the transition matrix is:
$$T =
\begin{bmatrix}
q& \dots \\
p& \dots \\
0 & \dots \\
0 & \dots
\end{bmatrix}
$$

Why P[10] = p?
And why P[20] = P[30] = 0? I mean the transition here for P[20] is saying that we have 2 machines today, then a repairman repairs the third machine and so the probability 0 machines are working by the end of the next day is q^3, isn't that right?

 

[Joe1998]

This is what I got for the transition matrix, is there anything wrong with it:

P[00] = q P[01] = p P[02] = p^2 P[03] = p^3

P[10] = q P[11] = p P[12] = p^2 P[13] = P^2

P[20] = q^2 P[21] = (p*q)*2 P[22] = p^2 P[23] = p^3

P[30] = q^3 P[31] = p*q^2 P[32] = q*p^2 P[33] = p^3So the reasoning for the values that I got are as follows:

P[00] = q: It means that no working machine exists by the end of one day, then a repairman repairs one machine and then it fails by the end of the next day. Thus, the probability that the one working machine at the start of the day will fail by the end of the day is q.

P[01] = p: It means that no working machine exists by the end of one day, then a repairman repairs one machine and then it remains working by the end of the next day. Thus, the probability that the one working machine remains working is p.

P[02] = p^2: It means that no working machine exists by the end of one day, then a repairman repairs one machine and then it remains working by the end of the next day, but also an extra working machine is added to the production line. Thus, the probability that both machines remain working during the day is p^2.

P[03] = p^3: It means that no working machine exists by the end of one day, then a repairman repairs one machine and then it remains working by the end of the next day, but also 2 extra working machines are added to the production line. Thus, the probability that both machines remain working during the day is p^3.

P[10] = q: It means that one working machine exists by the end of one day. Thus, the probability that the machine breaks down by the end of the day is q (Sorry I typed p, when it should be q, right?).

P[11] = p: It means that one working machine exists by the end of one day. Thus, the probability that the machine remains working by the end of the day is p (sorry I thought it is p*q but now I think it is just p).

P[12] = p^2: It means that one working machine exists by the end of one day. Thus, the probability that the machine remains working by the end of the day plus an extra working machine is added, is p^2 (or is it just 0, because the probability of adding an extra machine is not specified in the question which means it is zero?)

P[13] = p^2: It means that one working machine exists by the end of one day. Thus, the probability that the machine remains working by the end of the day plus 2 extra working machines are added, is p^2 (or is it just 0, because the probability of adding an extra machine is not specified in the question which means it is zero?)

P[20] = q^2: It means two working machines exist by the end of one day. Thus, the probability that both of the machines break down by the end of the next day is q^2

P[21] = (p*q)*2: It means two working machines exist by the end of one day. Thus, the probability that one of the machines breaks down by the end of the next day while the other remains working is (p*q)*2 (the reason it is multiplied by 2 is because it could be machine 1 or machine 2 that breaks down or remains work).

P[22] = p^2: It means two working machines exist by the end of one day. Thus, the probability that both remain working by the end of the next day is p^2

P[23] = p^3: It means two working machines exist by the end of one day. Thus, the probability that both remain working by the end of the next day plus an extra machine is added, is p^3 (or is it just 0, because the probability of adding an extra machine is not specified in the question which means it is zero?)

P[30] = q^3: It means 3 working machines exist by the end of one day. Thus, the probability that all 3 machines will be broken down by the end of the next day is q^3

P[31] = p*q^2: It means 3 working machines exist by the end of one day. Thus, the probability that 2 machines will be broken down by the end of the next day and 1 machine remains working by the end of the next day, is p*q^2

P[32] = q*p^2: It means 3 working machines exist by the end of one day. Thus, the probability that 1 machine will be broken down by the end of the next day and 2 machines remain working by the end of the next day, is q*p^2

P[33] = p^3: It means 3 working machines exist by the end of one day. Thus, the probability that all 3 machines remain working by the end of the next day, is p^3.

Please correct me as soon as you can and let me know what mistakes did I make?

Thanks for your help, I truly appreciate it everyone!

 

[PeroK]

Why P[10] = p?
And why P[20] = P[30] = 0? I mean the transition here for P[20] is saying that we have 2 machines today, then a repairman repairs the third machine and so the probability 0 machines are working by the end of the next day is q^3, isn't that right?

Let's take the state $X_0$ where no machines are active at the end of the day. This is represented by the vector $(1, 0, 0, 0)$ (where I've put this in a row to save some Latex). It will be a column vector below.

One machine is repaired overnight. This breaks down the next day with probability $q$, so this is the probability of being back in state $X_0$ the following night. The machine lasts the next day with probability $p$, which is the the probability of having state $X_1$ at the end of the next day. The other states have probability $0$ at the end of the following day. Applying $T$ to $X_0$ gives:
$$
\begin{bmatrix}
q& \dots \\
p& \dots \\
0 & \dots \\
0 & \dots
\end{bmatrix}
\begin{bmatrix}
1 \\
0 \\
0 \\
0
\end{bmatrix} =
\begin{bmatrix}
q \\
p \\
0 \\
0
\end{bmatrix}
$$As required.

 

[PeroK]

This is what I got for the transition matrix, is there anything wrong with it:

P[00] = q P[01] = p P[02] = p^2 P[03] = p^3

P[10] = q P[11] = p P[12] = p^2 P[13] = P^2

P[20] = q^2 P[21] = (p*q)*2 P[22] = p^2 P[23] = p^3

P[30] = q^3 P[31] = p*q^2 P[32] = q*p^2 P[33] = p^3

You've got the rows and columns mixed up. See my example above. That said I don't agree with many of your entries. For example: if there is $1$ working machine at the end of the day, then there are $2$ working machines at the beginning of next day, and the probability there is $1$ working machine at the end of that day is $2pq$. So $P_{11} = 2pq$.

So the reasoning for the values that I got are as follows:

P[00] = q: It means that no working machine exists by the end of one day, then a repairman repairs one machine and then it fails by the end of the next day. Thus, the probability that the one working machine at the start of the day will fail by the end of the day is q.

Okay.

P[01] = p: It means that no working machine exists by the end of one day, then a repairman repairs one machine and then it remains working by the end of the next day. Thus, the probability that the one working machine remains working is p.

Okay, but this is entry $P_{10}$ in the matrix.

P[02] = p^2: It means that no working machine exists by the end of one day, then a repairman repairs one machine and then it remains working by the end of the next day, but also an extra working machine is added to the production line. Thus, the probability that both machines remain working during the day is p^2.

There is nothing in the problem about machines being repaired during the day.

 

[Steve4Physics]

Let me add a few words. I suspect you haven't fully understood the problem, E.g. you wrote:

P[03] = p^3: It means that no working machine exists by the end of one day

No it doesn't. P[03] is the probability of
- changing from the state with 0 machines working at the end of a day to
- the state with 3 machines working at the end of the next day.

According to the rules, only 1 machine can be repaired overnight (and implicitly, additional machines cannot be added). The transition 0→3 is therefore impossible over a full day. So P[03]=0

Edit - reworded to (hopefully) make explanation clearer.

 

[pbuk]

There have been a few diversions in this thread due at least in part to ambiguous wording in the question. For anyone looking for a well-written introduction to Markov chains I can recommend the freely available notes and (unambiguously worded) exercises from this Cambridge University course.

Otherwise please note the solutions to the unambiguous parts below. Please start a new thread for any further discussion.

a-) Specify the state space of (Xn : n ≥ 0).
We are told that $X_n$ denotes the number of working machines at the end of day before the repairman begins any over-night repair. As there are 3 machines we can immediately write down the answer $S = \{0, 1, 2, 3\}$.

b-) Determine the transition matrix in terms of p.
If there are no machines are working at the end of day $t$ then the first thing that happens is exactly 1 machine is repaired overnight, then by the end of the next day either:

• exactly one machine breaks down (the one that was repaired) with probability $q = 1 - p$ and so there are no machines working at the end of day $t + 1$. We can now make the first entry in the transition matrix $a_{0, 0} = 1-p$.
• no machines break down with probability $p$ and so there is exactly 1 machine working at the end of day $t + 1$ (the one that was repaired overnight). We can now make the second entry in the transition matrix $a_{0, 1} = p$.

Because we started the day with only one machine working there are no other possibilities and so we can complete the first row of the transition matrix with zeros.

For the second row we start with exactly 1 machine working at the end of day $t$ so after another machine is repaired overnight there are more possibilities for what can happen during the next day and the second row looks like $\left [(1-p)^2, 2p(1-p), p^2, 0 \dots \right ]$ (note that the sum of each row is always 1: the matrix is said to be a right stochastic matrix and has a number of useful properties).

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

The answer to this question depends on the meaning of the word "idle" and whether we seek the probability of at least one or exactly one "idle" machine. Once we have determined these we can establish the initial state (row) vector $\tau_0$ and calculate the probabilities using $\tau_3 = ((\tau_0 P)P)P = \tau_0 P^3$.

 

[berkeman]

And with that excellent summary, this thread is now tied off. Thanks all.