## Description

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