How fast do Riemann sums converge for Lipschitz-continuous functions?

Question

I'm in the following situation: Let's say I've got a non-negative function $f$ that's globally Lipschitz-continuous on some interval $[a,b]$ for some constant $K$. I'm throwing a dart uniformly on the area below $f$ on that interval. Now consider the sequence of lower Riemann sums that results from bisecting all the intervals in the previous partition at each step. The dart will eventually be covered by the area corresponding to one of these lower Riemann sums (and all the following). Then define the random variable $X$ to be the index of the first such sum. My question is: Can the expected value of $X$ somehow be bounded using $K$?
Intuitively, since $f$ is Lipschitz, the Riemann sums exhaust the area below $f$ very quickly, so this expectation should be quite small. But I'm having a lot of trouble quantifying this intuition.

Answer 1

Let $m,M$ be the points in $[a,b]$ where $f$ attains its minimum and maximum. Since $f$ is $K$-Lipschitz, $$ f(M)-f(m) \leq K|M-m| \leq K(b-a) $$ But $\int_a^b f(x) \,dx \leq (b-a)f(M)$ and so this yields $$ \int_a^b f(x) \,dx - (b-a)f(m) \leq K(b-a)^2 \tag{*} $$

If we subdivide $[a,b]$ into $2^n$ equal-length subintervals, apply this inequality to each of them, and then sum, we get

$$\int_a^b f(x)\, dx - L_{2^n}(f) \leq \frac{K}{2^n}(b-a)^2$$ where $L_{2^n}(f)$ is the lower Riemann sum corresponding to this subdivision. So $$ 1 - \frac{L_{2^n}(f)}{\int_a^b f(x) \,dx} \leq \frac{K(b-a)^2}{2^n\int_a^b f(x) \, dx} $$ That is, the probability that the dart remains uncovered after the $n$th subdivision is at most $\frac{K(b-a)^2}{2^n\int_a^b f(x) \, dx}$.

So, if $P_n$ is the probability that the dart is uncovered after $n$ subdivisions, we have $$E[X]=\sum_{n=0}^\infty n(P_{n-1} - P_n) =\sum_{n=0}^\infty P_n \leq \frac{K(b-a)^2}{\int_a^b f(x) \, dx}\sum_{n=0}^\infty \frac{1}{2^n}=\frac{2K(b-a)^2}{\int_a^b f(x) \, dx}$$

---

In fact we can improve on the key inequality $(*)$ with a little more work. We have $$ f(x) - f(m) \leq K |x-m| $$ for all $x \in [a, b]$. Integrating over $[a,b]$ gives \begin{align} \int_a^b [f(x) - f(m)]\, dx &\leq K \int_a^b |x-m|\, dx \\ &= \frac{K}{2}[(m-a)^2 + (b-m)^2] \\ &= \frac{K}{2}[(a-b)^2-2(m-a)(b-m)] \\ &\leq \frac{K}{2}(a-b)^2 \end{align} and so we have $$ \int_a^b f(x) \, dx - (b-a)f(m) \leq \frac{K}{2} (a-b)^2 \tag{**} $$ a factor-of-$2$ improvement over $(*)$. Moreover, if $f$ is linear with slope $\pm K$, then equality is attained, so this bound is tight.

Carrying this through the rest of the argument we end up with $$ E[X] \leq \frac{K(b-a)^2}{\int_a^b f(x) \, dx} $$ with equality when $f$ is linear with slope $\pm K$.