MAT 135 B - Problem Set 7

Due 11:59pm on June 1st. You must submit electronically through Gradescope in Canvas.    Every student must write his or her own solution; looking for solutions from external sources (books, the web, material from previous years, etc.) is prohibited.

1 Solve and turn in the following problems:

1. Consider the Markov chain associated to the random walk in the following undirected graph (the random walk starts at a node and at every step picks at random a node adjacent to the current node and moves to it):

Is this Markov chain reversible?

Determine the invariant distribution.

2. Consider the Markov chain X0, X1, . . . where Xi is the number of individuals of a branching process with offspring distribution p0, p1, p2, . . . (that is, pi = P(X1 = i | X0 = 1)).

Determine all sequences p0, p1, p2, . . . such that the Markov chain is reversible. For every sequence p0, p1, p2, . . . that makes the chain reversible, determine all distributions that satisfy the reversibility equation (that is, p.m.f. π so that πiPij = πjPji for all i, j).

(Optional hint: Start with special cases, then study the general case. For example: Determine whether the chain with p0 = p1 = 1/2 is reversible, then with any sequence such that p0 > 0, then all sequences)

3. Consider two independent Poisson processes N1(t) and N2(t) representing the arrival of two types of customers at a store, with rates λ1 and λ2 per hour, respectively.

Find the probability of no arrivals in (3, 5].

Find the probability of the following event: there is exactly one arrival in each of the following intervals (0, 1],(1, 2],(2, 3] and (3, 4].

Find the probability of the following event: there are two arrivals in (0, 2] and three arrivals in (1, 4].

Determine Pr(N1(1) | N1(1) + N2(1) = 1).

Find the probability that the second arrival of type 1 occurs before the third arrival of type 2.

2 Solve but do not turn in the following problems:

        Problems at the end of chapters 16 and 18 in “Lecture Notes for Introductory Probability” by Janko Gravner. Find it in Canvas’ “Files” section.