Past exam of the Probability, statistics and options II course of the University of Oxford / 2008 / S (Simulation)

Assume the fixed margins are compatible, so the finite state space is nonempty. At state $X$, draw an index table $Y$ from the stipulated uniform proposal law. If $X+Y$ has any negative entry, reject and stay at $X$; otherwise accept and set the next state to $X+Y$. The margins stay fixed because the proposal has zero row and column sums.

The proposal set is invariant under $Y\mapsto -Y$. Hence proposals between two feasible distinct states are symmetric. The target density is constant, so the Metropolis–Hastings acceptance probability for a feasible proposal is one. The explicit rejection of infeasible proposals is essential: fixed margins by themselves do not guarantee nonnegative entries.

Let $L$ be the number of index tables, including the zero table. If distinct feasible states $A,B$ differ by an index table, then $P(A,B)=1/L=P(B,A)$, using the sign-reversal bijection for the reverse move. If they do not differ by an index table, both probabilities are zero. Since $\pi$ is uniform,For equal states detailed balance is tautological. Thus the chain is reversible and its uniform distribution is stationary.

A finite irreducible aperiodic Markov chain converges to its unique stationary distribution from every initial state. Finiteness holds because nonnegative entries with fixed finite row sums are bounded. The given connecting-sequence property makes the chain irreducible: each feasible step in such a sequence has positive proposal probability and is accepted. The all-zero index table occurs with probability $1/L>0$ and gives a self-loop at every state, establishing aperiodicity. Reversibility supplied the stationary uniform law in (b). ConsequentlyThe conclusion also holds when the feasible state space is a singleton.