Description

Department of Electrical Engineering and Computer Sciences
EECS 126: Probability and Random Processes
Problem Set 7
1. Markov Chains with Countably Infinite State Space
(a) Consider a Markov chain with state space Z>0 and transition probability graph:

Show that this Markov chain has no stationary distribution.
(b) Consider a Markov chain with state space Z>0 and transition probability graph:

Assume that 0 < a < b and 0 < a + b ≤ 1. Show that the probability distribution given by
, for i ∈ Z>0,
is a stationary distribution of this Markov chain.
2. Poisson Branching
Consider a branching process such that at generation n, each individual in the population survives until generation n + 1 with probability 0 < p < 1, independently, and a Poisson number (with parameter λ) of immigrants enters the population. Let Xn denote the number of people in the population at generation n.
(a) Suppose that at generation 0, the number of people in the population is a Poisson random variable with parameter λ0. What is the distribution at generation 1? What is the distribution at generation n?
(b) What is the distribution of Xn as n → ∞? What if at generation 0, the number of individuals is an arbitrary probability distribution over the non-negative integers; does the distribution still converge? (Justify the convergence rigorously.)
3. Balls and Bins: Poisson Convergence
Consider throwing m balls into n bins uniformly at random. In this question, we will show that the number of empty bins converges to a Poisson limit, under the condition that nexp(−m/n) → λ ∈ (0,∞).
(a) Let pk(m,n) denote the probability that exactly k bins are empty after throwing m balls into n bins uniformly at random. Show that
.
(Hint: Use the Inclusion-Exclusion Principle.)
(b) Show that
. (1)
(c) Show that
(2)
as m,n → ∞ (such that nexp(−m/n) → λ).
(d) Show that
(3)
as m,n → ∞ (such that nexp(−m/n) → λ). This is the hard part of the proof. To help you out, we have outlined a plan of attack:
i. Show that
.
ii. Show that

iii. Show that

as m,n → ∞ (such that nexp(−m/n) → λ). Conclude that (3) holds. (e) Now, show that
p0(m,n) → exp(−λ).
(Try using the results you have already proven.) Conclude that
.
4. Poisson Practice
Let (N(t),t ≥ 0) be a Poisson process with rate λ. Let Tk denote the time of k-th arrival, for k ∈ N, and given 0 ≤ s < t, we write N(s,t) = N(t) − N(s). Compute:
(a) P(N(1) + N(2,4) + N(3,5) = 0).
(b) E(N(1,3) | N(1,2) = 3).
(c) E(T2 | N(2) = 1).
5. Basketball II
Team A and Team B are playing an untimed basketball game in which the two teams score points according to independent Poisson processes. Team A scores points according to a Poisson process with rate λA and Team B scores points according to a Poisson process with rate λB. The game is over when one of the teams has scored k more points than the other team.
(a) Suppose λA = λB, and Team A has a head start of m < k points. Find the probability that Team A wins.
(b) Keeping the assumptions from part (b), find the expected time E[T] it will take for the game to end.