Description

Department of Electrical Engineering and Computer Sciences
EECS 126: Probability and Random Processes
Problem Set 9
1. Reversibility of CTMCs
We say a CTMC with rate matrix Q is reversible if there is a distribution p satisfying the detailed balance equations: piqij = pjqji ∀i,j.
Show that if a CTMC is reversible w.r.t. p, then p is a stationary distribution for the chain. Furthermore, show that in this case the embedded chain is also reversible. Remark. The converse is true too, i.e. the CTMC is reversible given that the embedded chain is reversible.
2. Particles Moving on a Checkerboard
There are 1278 particles on a 100 × 100 checkerboard. Each location on the checkerboard can have at most one particle. Each particle, at rate 1, independently over the particles, attempts to jump, and when it does it tries to move in one of the four directions, up, down, left, and right, equiprobably. However, if this movement would either take it out of the checkerboard or onto a location that is already occupied by another particle then the jump is suppressed, and nothing happens.
What is the stationary distribution of the configuration of the particles on the checkerboard?
3. Poisson Queues
A continuous-time queue has Poisson arrivals with rate λ, and it is equipped with infinitely many servers. The servers can work in parallel on multiple customers, but they are noncooperative in the sense that a single customer can only be served by one server. Thus, when there are k customers in the queue (k ∈N), k servers are active. Suppose that the service time of each customer is exponentially distributed with rate µ and they are i.i.d.
(a) Argue that the queue-length is a Markov chain. Draw the transition diagram of the Markov chain.
(b) Prove that for all finite values of λ and µ the Markov chain is positive-recurrent and find the invariant distribution.
4. Poisson Process MAP
Customers arrive to a store according to a Poisson process of rate 1. The store manager learns of a rumor that one of the employees is sending 1/2 of the customers to the rival store. Refer to hypothesis X = 1 as the rumor being true, that one of the employees is sending every other customer arrival to the rival store and hypothesis X = 0 as the rumor being false, where each hypothesis is equally likely. Assume that at time 0, there is a successful sale. After that, the manager observes S1,S2,…,Sn where n is a positive integer and Si is the time of the ith subsequent sale for i = 1,…,n. Derive the MAP rule to determine whether the rumor was true or not.
1
5. Statistical Estimation
Given X ∈{0,1}, the random variable Y is exponentially distributed with rate 3X + 1.
(a) Assume P(X = 1) = p ∈ (0,1) and P(X = 0) = 1 − p. Find the MAP estimate of X given Y .
(b) Find the MLE of X given Y .
2