Past exam of the algorithmic foundations of learning course of the University of Oxford / 2025 / 2 / c

Let ${\mathcal{G}}_t=\sigma (X_1,\dots ,X_t)$. Under $P_{{\theta }_{\star }}$, the true probability density function is positive and finite at every observation almost surely. Define the sequential likelihood ratioA zero numerator sets the product to zero thereafter. Thus $M_t$ is a well-defined nonnegative process, and $L_t({\theta }_{\star })=\log M_t$, with $\log 0=-\infty$.

The next observation is independent of ${\mathcal{G}}_{s-1}$, while ${\hat{\theta }}_{s-1}$ is measurable with respect to that sigma-algebra. Its conditional expectation is thereforeConsequently $\mathbb{E}(M_s\mid {\mathcal{G}}_{s-1})\le M_{s-1}$; induction also gives $\mathbb{E}{M}_s\le 1$. Thus $(M_t)$ is a nonnegative supermartingale for the filtration $({\mathcal{G}}_t)$. It need not be a martingale: an alternative distribution can put mass outside the support of the true distribution.

The maximal inequality for a nonnegative supermartingale, the corresponding form of the Ville inequality, givesThe strict inequality in the definition of the confidence set correctly becomes a non-strict crossing event.

There is a minor definitional omission in the source: for false candidates $\theta$, the printed sum of log-likelihood ratios can involve $0/0$ or both infinite signs. To define the entire confidence set without a positivity assumption, use the logarithm of the ratio of the two full products, ${\prod }_s{p}_{{\hat{\theta }}_{s-1}}(X_s)$ and ${\prod }_s{p}_{\theta }(X_s)$, taking $0/a=0$ for $a>0$, $a/0=+\infty$ for $a>0$, and, for example, $0/0=1$. This is a measurable extension of the printed formula wherever that formula is defined. The choice at $0/0$ cannot affect coverage of the truth, since its full denominator is positive almost surely. Alternatively, strict positivity of every density on the common support removes the omission.