Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 2 / 28J (Applied Probability)

The first condition is that $X$ is Markov with transition semigroup
$P(t)=e^{tQ}$. The second is that, for every function
$f:S\to \mathbb{R}$,is a martingale.

The first condition implies the second by conditioning over a short time interval, using
$P(h)f=f+hQf+o(h)$, summing increments, and passing to the limit. This is Dynkin's formula.

Conversely assume the martingale problem for a continuous-time Markov chain. Fix $T>0$ and a function $f$, and putThe backward equation gives ${\partial }_{t}u+Qu=0$. Applying the martingale identity to this time-dependent function shows that $u(t,X_t)$ is a martingale. Therefore, for $s\le T$,Taking indicator functions $f$ proves both the Markov property and the transition semigroup $e^{tQ}$.

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

LetFor every edge $xy$ of $A$,Thus detailed balance holds, so $\pi$ is invariant. Connectedness of $A$ makes the chain irreducible and this invariant distribution unique.