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

## Reviews

There are no reviews yet.