Homework I

General Homework Procedures

CRAN Project

Stage I of the project, consisting of the discrete-time case, will be due Tuesday, January 19.

Here you will develop a CRAN-quality R package for the analysis of Markov chains, as follows:

Math Problem A

This problem is part of Stage 1 of the homework, due January 19.

Items come in that need to be packed in boxes, in order of arrival. The maximum allowable weight per box is wmax; if an item would cause a box to go overweight, a new box must be started.

The weights W1, W2, W3,... of the items are independent and identically distributed (i.i.d.) with some distribution on {1,2,...,wmax}. Let Xn denote the total weight of items in the current box at "time" n, i.e. after the nth item has been packed. Due to the i.i.d. assumption, the Xn obey the Markov property.

Do the following, with π denoting the stationary distribution of the chain:

Math Problem B

(Stage 2)

Recall the Bus Paradox in our book. The quantity of interest was Dt, the time until the next bus arrival, where t is the time we arrive at the bus stop. We wished to determine the long-run distribution of Dt. If we are dealing with continous random variables, that long-run density is

f(w) = (1 - FL(w)) / EL

where L is the time between buses in general (not at the times you arrive). And remarkably, if we look at the time At since the last bus, we get the same distribution.

If L is a discrete random variable, the result is the same, except that instead of a density we have a probability mass function. In this problem, you will derive the above equation for this discrete case, using Markov chains, for the case of the time since the last bus.

It will be easier to think of light bulbs. As soon as one burns out, we replace it. Let Q be the length of time the current bulb has been burning, so Q = 0 at the time of a replacement. If Q = 8, say, the bulb has already lasted 8 units of time, but if it burns out at the next time step, Q immediately becomes 0 again.

Math Problem C

(Stage 2)

Here you will model queuing in a call center, with the following characterisics:

Part A: Set this up as a continuous-time Markov chain, with states (i,j), where i is the number of ordinary calls currently in the system (being served or waiting) and j is the number of complex calls.

Part B: Write R simulation code for this problem, using my DES package. You need not have had any prior background in discrete-event simulation; just read the documentation and the example. Let me know if you have any questions. Write your code to be general, NOT restricted to exponential distributions. But run it with exponential distributions for the parameter values you choose in Part A, so that the two parts serve as checks on each other.