MATH10007 Stochastic Modelling (BSc) 1
(1) Poppy is playing a game with infinitely many levels. When she is at level i ∈
{0, 1, 2, 3, . . . }, she either moves to level i + 1 with non-zero probability pi, or she
fails and goes back to level 0.
(a) Write down the one step transition probabilities. [2 marks]
(b) Determine the communicating classes. [2 marks]
(c) Give a condition on pi for level 77 being recurrent. [2 marks]
(d) Give a condition on pi for level 0 being positive recurrent. [2 marks]
(e) Calculate the stationary probabilities when they exist. [2 marks]
Hint: you may use that the mean of non-negative discrete random variables can be
written as ET =
∑
n P (T > n).
[Please turn over]
MATH10007 Stochastic Modelling (BSc) 2
Solution:
(a) pi,i+1 = pi, pi,0 = 1− pi for i ≥ 0 and all other transition rates are zero.
(b) Each state is accessible from each state, since from each state you can reach
zero and from there any other state in finite steps with finite probability. Hence
there is a single communicating class. (A pathological case is pi = 1 for i > i0
for some i0, but that’s not required to notice.)
(c) State 77 is recurrent if and only if state 0 is recurrent since recurrency is a class
property. State 0 is recurrent if the probability of escape is zero, that is if
1− ρ00 =
∏
i≥0
pi = 0
(d) The probability of not returning by time n is P (T0 > n|X0 = 0) = p0...pn−1,
where the empty product is considered to be one. By using the hint, the main
return time to level zero is ET0 = 1 + p0 + p0p1 + . . . , and state 0 is positive
recurrent if this expression is finite.
(e) From the global balance equations we get pij = pij−1pj−1 for j ≥ 1 and hence
pij = p0p1 . . . pj−1pi0, and from the normalization
∑
pii = 1 we get
pi0 = (1 + p0 + p0p1 + . . . )
−1
when the sum exists, that is when the chain is positive recurrent.
[Please turn over]
MATH10007 Stochastic Modelling (BSc) 3
(2) Consider a random walk on a clock, that is on the integers 1, 2, . . . , 12, where 1 and
12 are also considered adjacent. A random walk can jump to one of the two adjacent
numbers with the same probability 1/2. Justify all your answers.
(a) What are the communicating classes? [1 mark]
(b) Classify each state (transient, null or positive recurrent). [1 mark]
(c) What is the stationary distribution? [1 mark]
(d) Is this also the limiting distribution? [1 mark]
(e) Starting from 12, what is the mean return time to 12? [2 marks]
(f) Starting from 12, what is the probability that you visit all numbers before
returning to 12? [4 marks]
[Please turn over]
MATH10007 Stochastic Modelling (BSc) 4
Solution:
(a) Each state is accessible from any state by at most 11 steps, hence the there is
only a single communicating class.
(b) Each state is positive recurrent in a finite closed class.
(c) Solve the global or the detailed balance conditions, or recall that for random
walks on graphs the stationary probabilities are proportional to the degrees.
Hence pii = 1/12 for all i.
(d) No, since the system is periodic, since it always moves from even to odd state
and vice versa.
(e) This is just m12,12 = 1/pi12 = 12.
(f) From symmetry, it doesn’t matter where you step first, so let’s assume you
step to 1. Alternatively, condition on the first step. Now the question is the
probability to get to 11 before back to 12. Let hi = P (Tˆ11 < Tˆ12|X0 = i), then
h11 = 1 and h12 = 0, otherwise hi = (hi−1 +hi+1)/2, which is solved by hi = i/11
for i ≥ 1, hence the answer is h1 = 1/11.
[Please turn over]
MATH10007 Stochastic Modelling (BSc) 5
(3) Team A and B are playing football. Time is measured in hours from the beginning
of the game, and the game is two hours long. Team A scores a goal at rate 1 but
team B continuously gets better with time, and scores a goal at rate t. Justify all
your answers to the following questions.
(a) What is the mean number of goals by each team during the game? [2 marks]
(b) What is the probability that none of the teams scored a goal during the game?
[2 marks]
(c) What is the probability that the first goal of the game was scored during the
second hour? [2 marks]
(d) If there was precisely one goal during the game, what is the density function of
the time it happened? [2 marks]
(e) Each team has 11 players and one of them is the captain. A goal scored by
a team is equally likely scored by any of the team’s 11 players. What is the
probability that none of the captains scored a goal during the game?
[2 marks]
[Please turn over]
MATH10007 Stochastic Modelling (BSc) 6
Solution: We’ll use the notation At and Bt for the scores by each team, λi(s) for
the rate of scoring and Λi(t) =
∫ t
0
λi(s)ds for the total rate by each team i = A or B.
(a) Let At and Bt be the scores by the teams until time t. The number of scores
are Poisson random variables with mean ΛA(2) = 2 and ΛB(2) = 2.
(b) Since teams score independently, P (A2 = B2 = 0) = P (A2 = 0)P (B2 = 0) =
e−2e−2 = e−4.
(c) From superpositioning the scores from the teams, write Nt = At +Bt, so scores
from any team arrive at rate λ(t) = 1 + t, with integral Λ(t). We need the
probability of no score during the first hour and at least one score during the
second hour, that is
P (N1 = 0, N
(1)
1 ≥ 1) = P (N1 = 0)P (N (1)1 ≥ 1) = e−Λ(1)(1− e−(Λ(2)−Λ(1)))
= e−Λ(1) − e−Λ(2) = e−3/2 − e−4 = 0.204815 . . .
where we used superpositioning and the independent increments property.
(d) Conditioning on one score, from Cambell’s theorem, the density is proportional
to λ(t), that is f(t) = (1 + t)/4 on [0, 2] and zero otherwise.
(e) Due to the splitting property, the captain from each team scores goals at rate
λA(t)/11 and λB(t)/11 respectively, and due to superpositioning both captains
together score at rate (λA(t) + λB(t))/11. Hence none of them scored with
probability
e−
∫ 2
0 (λA(t)+λB(t))/11dt = e−4/11 = 0.695144 . . .
[Please turn over]
MATH10007 Stochastic Modelling (BSc) 7
(4) There are N water lily buds in a lake, and each blossoms independently into a flower
at rate 1. Initially none of the buds have blossomed.
(a) Let Xt be the number of flowers at time t. Model the system as a CTMC, by
specifying the state space and the generator. [2 marks]
(b) For N = 1 write down and solve the forward Kolmogorov equation with the
given initial condition. [2 marks]
(c) For general N , what is the mean number of flowers at time t? [2 marks]
(d) What is the probability of having j flowers at time t? [2 marks]
(e) How long do we have to wait on average until the first flower? [2 marks]
[Please turn over]
MATH10007 Stochastic Modelling (BSc) 8
Solution:
(a) The state space is S = {0, 1, . . . , N} and the qi,i+1 = N − i, qii = −(N − i) for
i < N and all other rates are zero.
(b) For N = 1 the p′00(t) = −p00(t) with p00(0) = 1, hence p00(t) = e−t, and
p01(t) = 1− e−t.
(c) Let us define X
(i)
t as one if the i-th bud flowered by time t, which define
independent processes. Their sum is the number of flowers Xt =
∑
iX
(i)
t . Since
E(X
(i)
t |X(i)0 = 0) = P (X(i)t = 1|X(i)0 = 0) = p01(t) = 1− e−t
for any i from the previous subquestion, we have
E(Xt|X0 = 0) = NE(X(1)t |X(1)0 = 0) = N(1− e−t)
(d) Buds turn to flowers independently, and at time t each of them has flowered
with probability 1 − e−λt. Hence the probability of having j flowers at time t
follows a binomial distribution
P (Xt = j|X0 = 0) =
(
N
j
)
(1− e−t)j(e−t)N−j
(e) Initially blooming happens at rate N , and hence q0 = N , so we wait a mean
1/N time for the first flower.
[Please turn over]
MATH10007 Stochastic Modelling (BSc) 9
(5) Consider a husband and wife. Each of them independently starts using their phone
after an exponential time with parameter λi, and then use it for an exponential time
with parameter µi, with i = 1 for the wife, and i = 2 for the husband.
(a) Model the system on a state space with four states, describing who is on the
phone at a given time. Give the generator. [2 marks]
(b) Draw the state diagram. [1 mark]
(c) Calculate the stationary probability that both of them are on the phone
simultaneously. [2 marks]
(d) If they are not on the phone, they talk to each other. How long is such a
conversation on average? [1 mark]
(e) Currently no one is on the phone. What is the probability that the woman gets
on the phone first? [1 mark]
(f) Currently no one is on the phone. What is the probability that at the next time
when the woman gets on the phone, the man is on the phone? [3 marks]
[Please turn over]
MATH10007 Stochastic Modelling (BSc) 10
Solution:
(a) Denote the states as S = {0, 1, 2, 3}, where 3 refers to both of them being on
the phone simultaneously. q01 = q2,3 = λ1, q02 = q1,3 = λ2, q10 = q3,2 = µ1 and
q20 = q3,1 = µ2, and all other rates are zero.
(b) The state diagram is
0 1
2 3
λ1
λ2 λ2
µ1
λ1
µ2
µ1
µ2
(c) We can solve the global balance equations or try to solve the detailed balance
equations. The latter are
pi2µ2 = pi0λ2, pi0λ1 = pi1µ1, pi2λ1 = pi3µ1, pi1λ2 = pi3µ2
and
∑
pii = 1. The solution is
pi1 =
λ1
µ1
pi0, pi2 =
λ2
µ2
pi0, pi3 =
λ1
µ1
λ2
µ2
pi0
and from the last equation we get pi0, and all other probabilities explicitly
pi0 =
µ1µ2
(µ1 + λ1)(µ2 + λ2)
, . . . , pi3 =
λ1λ2
(µ1 + λ1)(µ2 + λ2)
,
A simpler way for full marks is to consider two independent processes to describe
husband and wife, X
(1)
t , X
(2)
t , and obtain the joint stationary probability as
a product of the corresponding stationary probabilities of the independent
processes.
(d) They talk to each other when in state 0, which state is left at rate λ1 +λ2, hence
after an average chat time 1/(λ1 + λ2).
(e) Each of them start talking after an exponential waiting time Ti ∼ expo(λi). The
woman starts talking first if her waiting time is shorter, that is P (T1 < T2) =
λ1/(λ1 + λ2).
(f) The question can be reformulated as from state 0 what is the probability to
enter state 3 before state 1. If Tˆi is the first passage time to state i, then we
need hi = E(Tˆ3 < Tˆ1|X0 = i), for which h1 = 0, h3 = 1 and
(λ1 + λ2)h0 = λ1h1 + λ2h2, (λ1 + µ2)h2 = λ1h3 + µ2h0
which leads to
h0 =
λ1λ2
λ1λ2 + λ21 + λ1µ2
[End of Paper]