Computing assignment 3 Math 504. Spring 2008. CSUF craps and inventory problem

by Nasser Abbasi

Problem description


computing_assignment_number_3_craps_game_and_inventory.png

craps game

Summary of numerical results

The state probability transition matrix was entered and then raised to higher powers. This is the numerical result


matrix_converge_for_craps.png

To answer part (b) below, we need to run the system from different initial state vector (i.e. different MATH) and observe if the system probability state vector after a long time (i.e. MATH) will depend on the initial state vector or not. Here is the result for 3 different initial state vectors. In diagram below we show the MATH and to its right MATH.


pi_converge_craps.png

Analysis of numerical results

(a)

$\,$

Yes.
The powers of $P^{n}$ converges as $n\rightarrow\infty$. This is seen by looking at the above sequence of the $P$ matrix where we see that the matrix $P$ converges to the following limiting matrix at around $n=81$

We can say the following about the limiting matrix: As $n\rightarrow\infty$ the matrix $P$ converges to a fixed value shown above. The entries $P_{ij}^{n}$ where $j$ is a transient state goes to zero as $n$ gets large.

(b)

From the above numerical result, we see that depending on the initial system probability state vector MATH we obtain a different system probability state vector MATH as $n$ gets very large. This is because some states are transient (states MATH). In the inventory problem below, we see that we obtained a different result for this part since the inventory problem has no transient states.

(c)

Let $I$ be the set of all the possible states the system can be in. Hence from definition, we writeMATH

Where MATH means the probability that the system will be in state $j$ after $n$ steps and $P_{ij}^{n}$ is the $n$ steps transition probability. Now take the limit of the above as MATH we haveMATH Assume there are $k$ states, we can expandMATH

But from part(a) we observed that in the limit, entries of each columns are not equal. Hence MATH this means the above sum will produce a different value depending on the initial state probability vector MATH. (Compare this to the inventory problem below, where each entry in a column is the same, and we could factor it out of the sum and we reached a different conclusion than here).

Hence we showed depending on the initial MATH then MATH goes to different value as confirmed by the numerical result shown above in part(a). Hence part(a) results could be used to deduce part(b) conclusion.

Inventory problem

Summary of numerical results

An inventory program was written in Mathematica (please see appendix for full source code) which generated the $P$ matrix for an increasing values of $n$. The specification of the inventory model is described in the question shown above. The value

$s=3$
and
$S=5$
was used.

The following are few results of the $P$ matrix for an increasing values of $n$ and the histogram of the demand distribution used.


p.png

To answer part (b) below, we need to run the system from different initial state vector (i.e. different MATH) and observe if the system probability state after a long time (i.e. MATH) will depend on the initial state vector or not. Since we know thatMATH And since MATH, then all what we have do is pick few MATH vectors, and post multiply them by MATH for large $n$ and see if we obtain the same MATH. Below is the numerical result for this part showing the initial MATH and the final MATH. I used $n=30$ in all cases as this showed it is large enough from the above numerical results. Here are the results. Below we show result of 6 tests. In each one, MATH is shown and to its right MATH.


initial_state_up.png

Analysis of numerical results

(a)

$\,$

Yes.
The powers of $P^{n}$ converges as $n\rightarrow\infty$. This is seen by looking at the above sequence of the $P$ matrix where we see that the matrix $P$ converges to the following limiting matrix at around $n=20$


p_100.png

We can say the following about the limiting matrix: As $n\rightarrow\infty$ the matrix $P$ converges to a fixed value shown above. Each column has the same entries in its rows. In addition, all entries are non-zero. This implies that the chain contains no transient states. And since all the values on the converged $P$ matrix are positive, then we have only one closed set in the chain, which contains all the states.

(b)

$\,$

Yes.
There is a limiting state probability distribution in all cases. This is show by looking at the numerical result above that shows for different initial probability state vector MATH we obtain the same probability state vector MATH when $n$ is large. So the final MATH
does not depend
on which state the system starts from.

(c)

In this part, we need to show given that $P^{\infty}$ converges to limiting fixed value, then the MATH is the same for all states $k$.

Let $I$ be the set of all the possible states the system can be in. Hence from definition, we writeMATH Where MATH means the probability that the system will be in state $j$ after $n$ steps and $P_{ij}^{n}$ is the $n$ steps transition probability. Now take the limit of the above as MATH we haveMATH Assume there are $k$ states, we can expandMATH

But from part(a) we observed that MATH is a fixed value, which is the limit the transition matrix converged to. In other words, MATH since all entries in the $j$ column are the same. Call this entry in $j^{th}$ column as $k$ say. So $k$ is a single number which represents the one step transition probability from state $i$ to state $j$ when the system has run for a long time. So we write the above asMATH now, MATH is the sum of the probabilities of the system being in all its states at time zero, which must be $1$ henceMATH Hence we showed that regardless of the initial MATH then MATH goes to some fixed values. This shows that for any state $j$ the probability that the system will be in that state after a long time converges to a fixed value regardless of the initial state if the system transition matrix converges in the limit. Hence part(a) results could be used to deduce part(b) conclusion.

Appendix

Source code for craps problem

source code for inventory problem