Markov chains and production line comprising 3 machines

In summary: Regarding my thoughts, for part b), is it the case that there are only 2 states to consider which are: {machine working, machine not working}I am not sure. What are the other states?It sounds like you are unsure about the answer to this question. Can you explain more about why you are unsure?I am not sure because I am not even sure if the state space is indeed only 2 states or more. I am just unsure about all parts because I am not sure about part (a) in the first place. Regarding your thoughts for part c), is it the case that if a machine is not working, then the
  • #36
Orodruin said:
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.
 
Physics news on Phys.org
  • #37
Steve4Physics said:
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?
 
  • #38
PeroK said:
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!
 
Last edited:
  • #39
Joe1998 said:
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?
 
  • #40
haruspex said:
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?
 
  • #41
Joe1998 said:
the repairman fixes one overnight with a prob. of p
With a probability of 1.
Joe1998 said:
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?
Joe1998 said:
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!
 
  • #42
haruspex said:
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.
 
  • #43
Was there something you meant to add?
 
  • #44
haruspex said:
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?
 
  • #45
Joe1998 said:
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.
Joe1998 said:
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].)
 
  • #46
haruspex said:
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.
 
  • #47
Joe1998 said:
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}
$$
 
  • #48
Joe1998 said:
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.
 
  • #49
PeroK said:
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?
 
  • #50
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!
 
Last edited:
  • #51
Joe1998 said:
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.
 
  • #52
Joe1998 said:
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##.

Joe1998 said:
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.
Joe1998 said:
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.
Joe1998 said:
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.
 
  • #53
Let me add a few words. I suspect you haven't fully understood the problem, E.g. you wrote:
Joe1998 said:
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.
 
Last edited:
  • Like
Likes PeroK
  • #54
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 ##.
 
Last edited:
  • Informative
Likes berkeman
  • #55
And with that excellent summary, this thread is now tied off. Thanks all. :smile:
 

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
  • Mechanical Engineering
2
Replies
43
Views
621
  • Engineering and Comp Sci Homework Help
Replies
1
Views
869
  • Precalculus Mathematics Homework Help
Replies
24
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
11
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
6
Views
1K
  • Mechanical Engineering
Replies
12
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
3K
  • Computing and Technology
Replies
1
Views
828
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Back
Top