A generalisation of Ville’s inequality to monotonic lower bounds and thresholds

Essentially all anytime-valid methods hinge on Ville’s inequality to gain validity across time without incurring a union bound. Ville’s inequality is a proper generalisation of Markov’s inequality. It states that a non-negative supermartingale will only ever reach a multiple of its initial value with small probability. In the classic rendering both the lower bound (of zero) and the threshold are constant in time. We generalise both to monotonic curves. That is, we bound the probability that a supermartingale which remains above a given decreasing curve exceeds a given increasing threshold curve. We show our bound is tight by exhibiting a supermartingale for which the bound is an equality. Using our generalisation, we derive a cleaner finite-time version of the law of the iterated logarithm. • We extend the celebrated inequality by Ville from non-negativity and fixed thresholds to arbitrary monotonic lower bounds and thresholds. • We apply our extended Ville’s inequality to an improper-mixture supermartingale to derive finite-time versions of the law of the iterated logarithm. We argue that this proof strategy gives a slightly cleaner result than available with classic proper mixtures.