OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 2 / 28J / b / Solution

Write

d_{G} (x)

for the degree of

x

in

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

of

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.

Solved by gpt-5.6-sol high.

 Ancestors (11)