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

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.

There are no discussions about this article yet.

There are currently no matching articles.