Assignment Details:

Case 1: There are 2 white balls and 2 red balls in a box. At each time, you pick one ball in the box uniformly at random. If the picked ball is white, remove that ball and put a new red ball into the box. If the picked ball is red, then return that ball to the box with probability 1/2, or remove that ball and put a new white ball into the box with probability 1/2. Repeat this process for time t = 1,2,3,….

(a) Model this as a discrete-time Markov chain and find its transition probability matrix.

(b) Suppose you take note of the color of the balls in the box at the first moment when all balls in the box have the same color. Find the probability that all balls are red at that moment. (Hint: optional stopping theorem)

(c) Is this Markov chain a time-reversible Markov chain? Prove your assertion. (Refer to lecture notes 5 for the definition.)

(d) We modify the rules as follows: If the picked ball is white, remove all balls in the box (and the ball you picked) and put 4 red balls in the box. (No change to the case where the picked ball is red.) Is this Markov chain a time-reversible Markov chain? Prove your assertion.

Case 2: Customers arrive at a shop according to a Poisson process with rate 1. For a customer who arrives at time t ≥ 0, he/she either stays for 1 hour and leave the shop at time t + 1 with probability 1/2, or stays for t hours and leave the shop at time 2t with probability 1/2. Assume the choices of each customer are independent.

(a) Consider the departure process of customers (i.e., N(t) is the number of customers who left at time ≤ t). Is it a (homogeneous or nonhomogeneous) Poisson process? If yes, find its intensity function.

(b) Let X(t) be the number of customers in the shop at time t. Is X(t) a continuous-time time-homogeneous Markov chain? Prove your assertion.

(c) Find E[X(t)] in terms of t.

Case 3: Suppose there are two queues in a shop, one for buying gifts, and another for gift wrap. There is 1 server at the gift queue, and 3 servers at the gift wrap queue. The service time of each server is distributed as Exp(2). Customers arrive at the gift queue according to a Poisson process with rate λ = 1 (no external arrival at the gift wrap queue). After a customer finishes buying a gift, he/she joins the gift wrap queue.

After a customer obtains the gift wrap, he/she leaves the shop.

(a) Model this as a continuous-time time-homogeneous Markov chain. Find its infinitesimal rates qi,j. No proof is needed.

(b) Find the stationary distribution of the Markov chain (hint: Burke’s theorem).

(c) In steady-state, find the average amount of time a customer spends waiting in the gift wrap queue (not counting service time).

(d) Suppose λ = 3 instead of 1. What can we say about the long-term distribution of the Markov chain (the distribution of the state as time tends to ∞)? No proof is needed.

Case 4: A postman delivers letters between two cities A and B located 1km apart from each other, along a road that extends infinitely at both sides. The postman starts at city A, with a letter for city B. The postman moves randomly according to a standard Brownian motion (i.e., with no drift and with variance parameter 1km2/h) along the road. If the postman arrives at city B when he has a letter for city B, the postman delivers the letter, obtain a new letter for city A, and continue moving according to a standard Brownian motion along the road. If the postman arrives at city A when he has a letter for city A, the postman delivers the letter, obtain a new letter for city B, and continue moving according to a standard Brownian motion along the road. Let X(t) be the number of letters the postman has successfully delivered by time t (note that X(0) = 0).

(a) Is X(t) a continuous-time time-homogeneous Markov chain? If yes, find its infinitesimal rates qi,j. Prove your assertions.

(b) Find P(X(t) ≥ 2) in terms of t (you may leave your answer as an integral).

(c) (Warning: difficult) Find the average rate at which the postman delivers the letter, i.e.,

lim t→∞ E[X(t)]/t.

(d) Suppose the postman does not move according to Brownian motion but instead decides to travel by train. Trains depart from city A towards city B according to a Poisson process with rate 1 per hour. Trains depart from city B towards city A according to a Poisson process with rate 2 per hour (independent of the previous Poisson process). If the postman is in city A and has a letter for city B, he will wait for a train from city A to city B, and travel by train when it arrives. Similar to the case if the postman is at city B and has a letter for city A. Assume the train is so fast that the time it takes to travel between city A and city B is negligible (assumed to be 0). Repeat parts (a), (b) and (c).

Examples

(a) Give an example of a continuous-time time-homogeneous Markov chain X(t), where there exists a function g such that Y (t) = g(X(t)) is not a continuous time-homogeneous Markov chain. If such an example does not exist, prove that it does not exist.

(b) Give an example of a continuous-time time-homogeneous Markov chain X(t) ∈ {0, 1, 2, . . .},  such that Y (t) = X (t) + N (t) is not a continuous-time time-homogeneous Markov chain, where N(t) ∈ {0,1,2,…} is a Poisson process with rate 1 (as a counting process) independent of the process X(t). If such an example does not exist, prove that it does not exist.

(c) Give an example of a continuous-time time-homogeneous Markov chain X(t) ∈ {0,1,2,…}, such that X(0) = 0, E[T1] = 1 and Var[T1] = 0.1 (where T1 is the hitting time of the state 1). If such an example does not exist, prove that it does not exist.

(d) Give an example of a continuous-time time-homogeneous Markov chain X(t) ∈ {0, 1, 2, . . .}, such that X (0) = 0, and T1 follows the uniform distribution over the interval [0,1] (where T1 is the hitting time of the state 1). If such an example does not exist, prove that it does not exist.

(e) Give an example of a renewal counting process N(t) (refer to lecture notes 4 for the definition) satisfying E[N(1)] ≥ 5 and lim t→∞ E[N(t)]/t = 1. If such an example does not exist, prove that it does not exist.

(f) Give an example of a stochastic process X(t) with independent increments and stationary increments (stationary increments means the distribution of X(t+s)−X(t) only depends on s and does not depend on t), such that P(X(t) = 1)< 1/2 (P(X(t) = 0) + P(X(t) = 2)) for all t ≥ 0. If such an example does not exist, prove that it does not exist.

(g) Give an example of an open queueing network with M ≥ 3 queueing systems, such that γM = 0 (i.e., no arrival from outside to the M-th system), and this queueing network has no stationary distribution, and if we remove the M-th system (together with all edges to or from the M -th system), then the resultant network with M − 1 queueing systems has a stationary distribution. (Note that the τi,j for i, j ≤ M − 1 in the new network are the same as the τi,j in the original network. Refer to lecture notes 6 for the definitions of these quantities.) If such an example does not exist, prove that it does not exist.