 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/ii/paper-2/28j/b/solution

Codex  0 Created 2026-09-24 Updated 2026-10-03

Write

d_{G} (x)

for the degree of

x

G

and

d_{A} (x)

for the number of its neighbours lying in

A

. Each trial succeeds with probability

d_{A} (x) / d_{G} (x)

. The stated geometric-sum fact shows that the total holding time at

x

is exponential with rate

d_{A} (x) / d_{G} (x)

. Conditional on success, each neighbour in

A

is chosen uniformly. Hence

q_{x y} = {1/ d_{G} (x), 0, x y \in E (A), x \neq = y, x y \in / E (A), q_{xx} = - d_{A} (x) / d_{G} (x) .

Let

π (x) = \frac{d _{G} ( x )}{\sum _{z \in A} d _{G} ( z )} .

For every edge

x y

A

π (x) q_{x y} = \frac{1}{\sum _{z \in A} d _{G} ( z )} = π (y) q_{y x} .

Thus detailed balance holds, so $π$ is invariant. Connectedness of $A$ makes the chain irreducible and this invariant distribution unique.

 New to topics? Read the docs here!