STATS217: Introduction to Stochastic Processes 1 Homework 5

Instructor: Tselil Schramm Due: March 16, 2023

Homework 5: Poisson Processes & Continuous-Time Markov

This homework assignment is due on March 16, 2023 at 10:00AM on gradescope. It is worth 20% of
your total homework grade. You may work in groups, but you must write up your own answers. Try to
keep your answers clear and concise.

1. Poisson Meets Marguerite (28 points). You’re at the Palo Alto Caltrain station waiting for the
Marguerite bus. You can take one of two lines to Sequoia hall, the 𝑃 line and the 𝑋 line. Unfortu-
nately, the Marguerite schedule is very poorly synchronized with the Caltrain schedule, so much so
that the arrival of buses on the 𝑃 line follows a Poisson Process with rate 𝜆, and the arrival of buses
on the 𝑋 line follows a Poisson Process with rate 𝜇.

(a) Suppose you arrive at the bus stop at time 0.99 ⋅ 𝜆. What is your expected wait time until the
next 𝑃 bus?
(b) You wait at the bus stop for the 𝑃 bus for a time period of length 𝑡. During this time, what is
the expected number of 𝑋 line buses that stop at the stop?
(c) Each 𝑃 bus that shows up is full independently with probability (1 − 𝑝), so the arrival of the
next (non-full) 𝑃 bus you can take is distributed like 𝑇 = ∑𝑁𝑖=1 𝜏𝑖 where each 𝜏𝑖 ∼ Exp(𝜆) and
𝑁 ∼ Geo(𝑝). Show that 𝑇 ∼ Exp(𝑝𝜆).
Hint: There is a conceptual solution which does not require any calculations.

(d) As above, each 𝑃 bus that shows up is full independently with probability 1 − 𝑝. The 𝑋 bus
usually takes a long time, but luckily each 𝑋 bus that shows up is an express bus independently
with probability 𝑞. If you show up to the stop at time 0, what is the expected amount of time
you need to wait until either a non-full 𝑃 line bus or an express 𝑋 line bus arrives?
(e) You arrive at the Marguerite stop at time 𝑡, ask a fellow student and discover that n P line buses
have arrived at the stop. You know that your friend was on the 𝑃 line, and that they got off the
bus a while ago at time 𝑠 < 𝑡; what is the probability that your friend got off the 𝑚th bus of the
day, for 𝑚 < 𝑛?

2. Poisson vs. Binomial. (28 points) In class, we saw that the Poisson distribution with mean 𝜆 is
an approximation to Binom(𝑛, 𝜆𝑛 ) when 𝑛 is large. In this problem you’ll make this statement more
precise and also more robust: you’ll prove an upper bound on the total variation distance between
Pois(𝜆) and Binom(𝑛, 𝜆𝑛 ), and then you’ll extend your argument beyond Binom(𝑛, 𝜆𝑛 ) to the case
where each “coinflip” has a different probability.

(a) Argue that if 𝑋 = ∑𝑛𝑖=1 𝑋𝑖 and 𝑌 = ∑𝑛𝑖=1 𝑌𝑖 for 𝑋1 , … , 𝑋𝑛 and 𝑌1 , … , 𝑌𝑛 independent random
variables, then dTV (𝑋 , 𝑌 ) ⩽ ∑𝑛𝑖=1 dTV (𝑋𝑖 , 𝑌𝑖 ).
Hint: It may be useful to apply the coupling characterization of the total variation distance.

1
 (b) Argue that if 𝑋1 , … , 𝑋𝑛 are independent with 𝑋𝑖 ∼ Pois(𝜆/𝑛), then 𝑋 = ∑𝑛𝑖=1 𝑋𝑖 has distribution
Pois(𝜆).
(c) Argue that dTV (Pois(𝑝), Ber(𝑝)) = 𝑝(1 − 𝑒 −𝑝 ).
𝜆2
(d) Now argue that dTV (Pois(𝜆), Binom(𝑛, 𝜆𝑛 )) ⩽ 𝑛.
(e) Now, explain how to modify your argument above to prove that if 𝑍 = ∑𝑛𝑖=1 𝑍𝑖 where each 𝑍𝑖 ∼
Ber(𝜆𝑖 /𝑛) is independent but the 𝜆𝑖 ’s are not necessarily equal, then 𝑍 is also approximately
Poisson in the sense that for 𝜆 = ∑𝑛𝑖=1 𝜆𝑛𝑖 , dTV (Pois(𝜆), 𝑍) ⩽ 𝑛12 (∑𝑛𝑖=1 𝜆𝑖2 ) ⩽ 𝑛1 max𝑖∈[𝑛] 𝜆𝑖2 . No-
tice that this greatly extends the modeling power of the Poisson distribution; you have proven
that Pois(𝜆) not only captures the number of occurrences of independent rare events with pre-
cisely the same probability, but allows some variation in the individual event probabilities.

3. Distance between Poisson Processes (14 points) For 𝜆 ⩾ 𝛿 > 0, let (𝐴𝑡 )𝑡⩾0 be a Poisson Pro-
cess with rate 𝜆 and let (𝐵𝑡 )𝑡⩾0 be a Poisson Process with rate 𝛿. Let 𝑇 be the distribution of the
process 𝐴𝑡 from time 0 to 𝑇 , that is, of (𝐴𝑡 )𝑇𝑡=0 , and let 𝑇 be the distribution of (𝐵𝑡 )𝑇𝑡=0 . Show that
dTV (𝑇 , 𝑇 ) ⩽ 𝑇 (𝜆 − 𝛿).
Hint: Though we only proved it for distributions with finite support, you may use the characterization of the total variation
distance which states that dTV (𝑇 , 𝑇 ) = mincouplings of (𝑋 ,𝑌 )∼(𝑇 ,𝑇 ) 𝐏𝐫[𝑋 ≠ 𝑌 ].

4. Poisson Process Pairs as CTMC (7 points) Suppose that (𝑋𝑡 )𝑡⩾0 is a Poisson Process with rate 𝜆1
and (𝑌𝑡 )𝑡⩾0 is an independent Poisson Process with rate 𝜆2 , and 𝑍𝑡 = 𝑌𝑡 + 𝑋𝑡 . Consider the process
𝑊𝑡 = (𝑋𝑡 , 𝑌𝑡 , 𝑍𝑡 ). Explain how to encode 𝑊𝑡 as a continuous-time Markov chain, and give its jump
rates.

5. Long lines. (14 points) You have just arrived at the airport, and you brace yourself to stand in line.

(a) In the security screening, there are two stages: an ID check and a metal detector. Passengers
arrive according to a Poisson Process of rate 𝜆, the ID check processes passengers at a rate of
𝛼, and the metal detector processes passengers at a rate of 𝛽. Express the number of people
in line as a continuous-time Markov chain (specify jump rates) over the state space (𝑥, 𝑦) for
𝑥, 𝑦 ∈ Z+ , where 𝑥 is the number of people in line for the ID check stage and 𝑦 is the number of
people in line for the metal detector stage. Draw a picture representing the rates of transition
between the states (𝑥, 𝑦) for 𝑥 + 𝑦 ⩽ 2.
(b) You’ve gotten through security, and now you want to buy something to eat on the flight. There
are two food kiosks side-by-side, one of which sells sandwiches and serves customers at a rate
of 𝛼 (not the same rates as previous part), and the other of which sells burritos and serves
customers at a rate of 𝛽. Customers arrive according to a Poisson Process with rate 𝜆, and each
customer upon arrival chooses to buy food at the shorter of the two lines (breaking ties with a
fair coinflip). Express the number of people in line as a continuous-time Markov chain (specify
jump rates) over the state space (𝑥, 𝑦) for 𝑥, 𝑦 ∈ Z+ , where 𝑥 is the number of people in line for
the sandwich kiosk and 𝑦 is the number of people in line for the burrito kiosk. Draw a picture
representing the rates of transition between the states (𝑥, 𝑦) for 𝑥, 𝑦 ⩽ 2 (the 2 × 2 grid this
time, not the triangle 𝑥 + 𝑦 ⩽ 2).

2
 (c) (7 point bonus) In fact, there are a finite number of people in the airport, so both of the
scenarios above make sense if we take the state space to be (𝑥, 𝑦) with 0 ⩽ 𝑥 + 𝑦 ⩽ 𝑛. For
the case 𝑛 = 5, use a computer to find the stationary distributions of these processes in the
following settings:
i. Security screening, 𝜆 = 𝛼 = 𝛽 = 1.
ii. Security screening, 𝜆 = 𝛼 = 1, 𝛽 = 21 .
iii. Food kiosks, 𝛼 = 𝛽 = 1, 𝜆 = 3.
iv. Food kiosks, 𝛼 = 32 , 𝛽 = 12 , 𝜆 = 2.
Suggestion: before you program this, first try to guess what the stationary distributions will be like in each
of these cases.

6. Endemic Disease (14 points) A disease is present in an 𝑛-person population The more sick people
in the population, the more rapidly people get infected. Suppose that when there are 𝑘 sick people
in the population the disease dynamics are such that a new person is infected at a rate of (𝑘 + 1)𝛼
(unless 𝑘 = 𝑛, in which case the rate of infection is 0), and someone recovers from the illness at a
rate of 𝑘𝛽.

(a) Suppose that this process goes on for a very long time (i.e. it reaches stationarity). What is the
stationary distribution of the number of infected people?
Hint: Solve for a distribution which satisfies the detailed balance conditions.

(b) Suppose now that instead of the infection rate being (𝑘 + 1)𝛼 when 𝑘 people are sick, it is only
𝑘𝛼 (so that when 0 people are sick, it stays that way). For each 𝑚 ⩽ 𝑛, let 𝑔𝑚 be the amount of
time on average until the disease dies out completely if 𝑚 people are sick at time 0. Write down
a system of equations (for arbitrary values of 𝑛) to solve for 𝑔0 , 𝑔1 , … , 𝑔𝑛 (no need to actually
solve the system of equations).