Problem Set 9 Reversibility of CTMCs

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