A discrete-time queue Markov Chain problem

[Joe1998]

The following problem is seriously tricky and I urgently need help with it, thanks.

For part a: we have the following transition probability matrix

P = a0 a1 a2 a3

a0 a1 a2 a3

0 a0 a1 b2

0 0 a0 b1

Now, is a0 = a1 = a2 = a3 = 1/4? And is b1 = 1/4 whereas b2 = 1/4 + 1/4 = 1/2?

Note that bk = P(An ≥ 4) = ∑ aj (Where the sum is over all j≥ K) ; and aj = P(An = j) , j = 0,1,2,3.



For part b: is it just (m0j(10) / 11) = (m0j(10) / 11) and (m1j(10) / 11), etc.? Of course we calculate P10, right?



For part c: Does that mean we are dealing with Xn = 4? And to calculate the expected time until the buffer reaches its capacity for the first time, then do we just use the formula (mij(n) / n+1)? If yes, then at what values of i,j and n do we look at? E.g., is it m04(10) / 10+1, or...?



For part d: Since in the question it says that "if arrivals exceed the buffer capacity, then the excess is lost", then I understand that Yn is representing that waste. Now, do we calculate the transition matrix for Yn or what? Because I seriously have no idea how to even solve this question, so any quick help would be really appreciate it because I have very limited time left.

Thanks for your help, I really appreciate it.
Kind regards

 

[nuuskur]

It's virtually unreadable. You have five states, therefore the transition matrix is $5\times 5$. When you have a candidate for the transition matrix, check it's a right stochastic matrix, otherwise your result would be wrong.

I do not have the mental capacity required to decipher the rest of this My condolences to your grader. Please, format it with TeX, it's not implemented without reason.

Your being in a hurry is irrelevant. It is your responsibility to get things done on time.

 

[Joe1998]

It's virtually unreadable. You have five states, therefore the transition matrix is $5\times 5$. When you have a candidate for the transition matrix, check it's a right stochastic matrix, otherwise your result would be wrong.

I do not have the mental capacity required to decipher the rest of this My condolences to your grader. Please, format it with TeX, it's not implemented without reason.

Your being in a hurry is irrelevant. It is your responsibility to get things done on time.

Do you have any idea how to approach part c or d?

 

[pbuk]

Do you have any idea how to approach part c or d?

Yes, start by showing your answer for (a): I'll help by giving you a template to amend:
$$
\begin{bmatrix}
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\end{bmatrix}
$$

 

[Joe1998]

Yeah I know how to do parts a and b, I have already done them.

Part a:
1/4 1/4 1/4 1/4 0

0 1/4 1/4 1/4 1/4

0 0 1/4 1/4 1/2

0 0 0 1/4 3/4

0 0 0 0 1

Part b:
I just calculate the sum of P^m for m = 0,1,2,3,4,5,6,7,8,9,10 and then add up the first row.

Now, I am stuck at parts c and d, so any help would ne appreciate it.

 

[pbuk]

Yes, start by showing your answer for (a): I'll help by giving you a template to amend:
$$
\begin{bmatrix}
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\end{bmatrix}
$$

If you can't work out how to copy and amend that template, copy the code below into your message.

$$
\begin{bmatrix}
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & 0 \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\end{bmatrix}
$$

Only the first row of your answer to (a) is correct.

 

[Joe1998]

If you can't work out how to copy and amend that template, copy the code below into your message.

$$
\begin{bmatrix}
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & 0 \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\
\end{bmatrix}
$$

Only the first row of your answer to (a) is correct.

Wait, why only my first row is correct? I got it checked by my professor and he confirmed that it is correct! So why do you think it is not correct?

 

[pbuk]

Take for instance your last row representing the transitions from the state where the buffer contains 4 items immediately before dispatch (i.e. it is full) at time $n$ . The next thing that happens is that an item is dispatched, so the buffer contains 3 items, and then {0..3} items arrive with equal probability. If 0 items arrive between times $n$ and $n + 1$ (with probability $\frac 1 4$) then there will still be only 3 items at time $n + 1$.

 

[Joe1998]

Take for instance your last row representing the transitions from the state where the buffer contains 4 items immediately before dispatch (i.e. it is full) at time $n$ . The next thing that happens is that an item is dispatched, so the buffer contains 3 items, and then {0..3} items arrive with equal probability. If 0 items arrive between times $n$ and $n + 1$ (with probability $\frac 1 4$) then there will still be only 3 items at time $n + 1$.

Ok so let's not waste time on parts a and b, because I have checked with my professor and said they are correct, so all what I am asking is if you could give me some help, tips and guidance regarding how to do parts c and d, thanks.

 

[PeroK]

Ok so let's not waste time on parts a and b, because I have checked with my professor and said they are correct, so all what I am asking is if you could give me some help, tips and guidance regarding how to do parts c and d, thanks.

For part c), in general, if something happens for the first time in phase $n$, then it didn't happen in phases $1$ to $n -1$ and then did happen. That suggests an interative or inductive approach here.

I think this is now too advanced to avoid Latex. I have a particular inability to read unformatted mathematics.

 

[Joe1998]

For part c), in general, if something happens for the first time in phase $n$, then it didn't happen in phases $1$ to $n -1$ and then did happen. That suggests an interative or inductive approach here.

I think this is now too advanced to avoid Latex. I have a particular inability to read unformatted mathematics.

Ok, what about part d, how to go about it?
Thanks

 

[PeroK]

Ok, what about part d, how to go about it?

What about following the expansive hint in the question?

 

[Joe1998]

What about following the expansive hint in the question?

Yeah cool, thanks.