Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 216 / 2

For the planar uniform distribution with a Lebesgue measure density, assume that the compact convex set $\mathcal{C}$ has nonempty interior, equivalently positive area. This assumption is missing from the wording: a line segment or singleton would not have such a planar uniform density.

The hit-and-run sampler at a current point $x$ chooses $u=(\cos \Theta ,\sin \Theta )$ with $\Theta$ uniform on $[0,2\pi )$, finds the intervaland samples $T$ uniformly on that interval, setting $x^{\prime }=x+Tu$. Convexity makes the intersection an interval and compactness makes it bounded.

If $x$ is in the interior, every direction has positive chord length, and the next point is in the interior almost surely. For a definition valid at every boundary point as well, redraw the direction whenever the chord has zero length. We use this convention in the following parts. Positive-length directions have positive angular probability at every $x$, since an interior ball is visible from $x$, so the redraw terminates almost surely.

The Markov kernel has the uniform distribution on $\mathcal{C}$ as its invariant law, as follows from the density symmetry proved next. Repeating the step therefore produces approximate uniform samples after convergence. The boundary convention matters: if singleton chords were instead treated as holding moves, a square's corner would have a positive atom at its starting point, contradicting part (b)'s claim of an everywhere absolutely continuous kernel.

Write $\ell (x,u)=t_{+}(x,u)-t_{-}(x,u)$ and letThis is the accepted fraction of directions when zero-length chords are redrawn; it equals one in the interior. The Markov kernel integrates a test function $h$ asThe signed polar representation has Jacobian determinant $|t|$. Each point $y\ne x$ is represented twice, once with positive $t$ and once with negative $t$ and the opposite direction. Since the chord is the same in either representation, the hit-and-run kernel density isfor almost every $y\in \mathcal{C}$, and it is zero outside the body. Thus the transition is absolutely continuous with respect to planar Lebesgue measure. Redrawing removes the only potential zero-chord atoms.

Let $D=\mathrm{diam}(\mathcal{C})>0$. For distinct $x,y\in \mathcal{C}$, the chord contains their segment, so it has positive length, andHence $p(x,y)\ge 1/(\pi D^2)$. Values on the diagonal, and on other null sets where a density is only specified almost everywhere, can be assigned this same lower bound. This gives a version satisfyingFor interior $x,y$, $a(x)=a(y)=1$ and the chord length is unchanged on interchanging its endpoints, so $p(x,y)=p(y,x)$. A convex body's boundary has area zero; for example contractions about an interior point fill the interior and their areas tend to the body's area. Thus this symmetry holds almost everywhere for two uniform points, proving detailed balance and stationarity of the uniform distribution. Without positive area or the boundary convention in part (a), the literal assertion need not hold.

The geometric drift condition requires a measurable $V:\mathcal{X}\to [1,\infty )$, a small set $C$, constants $\lambda \in (0,1)$ and $b<\infty$, andSmallness means that for some $m\ge 1$, $\epsilon >0$, and probability measure $\nu$, $P^m(x,\cdot )\ge \epsilon \nu (\cdot )$ for every $x\in C$. With irreducibility and aperiodicity, this drift-minorisation condition implies geometric ergodicity. The function $V$ controls the chain away from the small set; inside that set the additive constant allows unrestricted bounded drift.

Let $A=\mathrm{Leb}(\mathcal{C})>0$ and let $\mu$ be the uniform distribution on the body. The hit-and-run kernel density lower bound impliesFor the last range, $\mathcal{C}$ lies in a radius-$D$ disc about any of its points, so $A\le \pi D^2$ and $\epsilon \le 1/2$. This global Doeblin condition proves irreducibility with respect to $\mu$ and aperiodicity. The entire state space is a small set; $V=1$, $\lambda =1/2$, and $b=1/2$ satisfy the geometric drift condition.

In fact the conclusion is stronger. Write $P=\epsilon \Pi +(1-\epsilon )R$, where $\Pi (x,\cdot )=\mu$ and $R$ is the residual Markov kernel. Since $\mu P=\mu$, also $\mu R=\mu$. Each transition has a probability $\epsilon$ of resetting to stationarity, and after such a reset every subsequent distribution remains stationary. Equivalently,Thus the algorithm has uniform geometric ergodicity, using the full-dimensional and boundary conventions stated in part (a).