Homework III

Due in stages; Problem 1 due Wednesday, October 27, and the remainder due on Monday, November 1.

Problem 1:

Consider a producer/consumer setting:

• Time is slotted, as in our ALOHA model.
• Items (work tasks, network messages, etc.) arrive and are stored in a buffer with a capacity of b items.
• In the middle, i.e. the 0.5 point, of any time slot, an item arrives or not, with probabilities p and 1-p. If the buffer is full when an item arrives, the item is discarded.
• Near the end, at the 0.9 point, of any time slot, the consumer either removes an item from the buffer or not, with probabilities q and 1-q. If the buffer is empty, of course nothing is removed.

We will model this as a discrete-time Markov chain, with the state at time n being the number of items in the buffer at the beginning of time slot n.

Actually, this is a birth/death chain as in Section 10.3.6, except here we are in discrete time. Thus there is a closed-form solution. You can either look the formula up on the Web, or ignore that and simply use findpi1() to find the π.

1. Find the long-run proportion of items that are discarded, as a function of π.
2. Find the long-run mean residence time, i.e. the long-run average number of time slots that an item spends in the buffer, expressed in terms of π. Do not count the time slot in which the item arrives, but do count the time slot in which it is removed.
3. Write R simulation code to verify your answers above.

Problem 2:

Problem 3, ECS 132 Homework III (YouTube data analysis).

Problem 3:

In a Markov chain, the distribution of X_n+1, given X_n and X_n-k, k = 1,2,... depends only on X_n. The notion of second-order Markov chain (SOMC) generalizes that: The distribution of X_n+1, given X_n and X_n-k, k = 1,2 depends only on X_n and X_n-1.

In an SOMC, let Y_n = (X_n-1, X_n). Then the Y_n form a Markov chain. The transition probabilities now are triple-subscripted, with P(X_n+1 = k | X_n-1 = i and X_n = j) being denoted by p_ijk. Similarly, stationary probabilities are double-subscripted:

lim_{n → ∞} P(X_n-1 = i and X_n = j) = π_ij

(assuming nonperiodicity etc.).

The X_n form an "un-Markov chain," but

q_ij = lim_{n → ∞} P(X_n+1 = j | X_n = i)

will still exist in typical situations.

Find the q_ij in terms of the p_ijk and the π_ij. Hint: You can assume that Y₁ has the distribution π.