Problem Set 7 Markov Chains with Countably Infinite State Space

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:
1 · · · i i + 1 · · ·
3
4
1
4
1
2
1
2i+2
i−1
2(i−1)+2
1
2
1
2(i+1)+2
i
2i+2
1
2
i+1
2(i+1)+2
1
2
Show that this Markov chain has no stationary distribution.
(b) Consider a Markov chain with state space Z>0 and transition probability graph:
1 · · · i i + 1 · · ·
1 − a
a
b
1 − a − b
a
b
1 − a − b
a
b
a
b
Assume that 0 < a < b and 0 < a + b ≤ 1. Show that the probability distribution given
by
π(i) = a
b
i−1
1 −
a
b

, 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.)
1
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
n exp(−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
p0(m, n) = Xn
j=0
(−1)j

n
j

1 −
j
n
m
.
(Hint: Use the Inclusion-Exclusion Principle.)
(b) Show that
pk(m, n) = 
n
k

1 −
k
n
m
p0(m, n − k). (1)
(c) Show that

n
k

1 −
k
n
m
≤
λ
k
k!
(2)
as m, n → ∞ (such that n exp(−m/n) → λ).
(d) Show that

n
k

1 −
k
n
m
≥
λ
k
k!
(3)
as m, n → ∞ (such that n exp(−m/n) → λ). This is the hard part of the proof. To help
you out, we have outlined a plan of attack:
i. Show that

n
k

1 −
k
n
m
≥

1 −
k
n
k+m n
k
k!
.
ii. Show that
lnn
n
k

1 −
k
n
mo
→ k ln λ
as m, n → ∞ (such that n exp(−m/n) → λ). You may use the inequality ln(1−x) ≥
−x − x
2
for 0 ≤ x ≤ 1/2.
iii. Show that

1 −
k
n
k
→ 1
as m, n → ∞ (such that n exp(−m/n) → λ). Conclude that (3) holds.
(e) Now, show that
p0(m, n) → exp(−λ).
(Try using the results you have already proven.) Conclude that
pk(m, n) →
λ
k
exp(−λ)
k!
.
2
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.
3