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.

  • $\begingroup$ I am confused about the setup: If you partition an interval, the dart will always be a part of any partition. A partition is just an ordered sequence on $[a,b]$. What does it mean for the dart to be be "eventually" covered? $\endgroup$
    – yoshi
    Mar 29 '18 at 2:54
  • $\begingroup$ The dart is an element of $\mathbb{R}^2$. The vertical columns corresponding to some partition cover some area of $\mathbb{R}^2$. Eventually these columns will cover the dart. $\endgroup$ Mar 29 '18 at 3:04

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$.

  • $\begingroup$ Wow, this came out quite elegantly. The way you bounded the difference between the integral and the Riemann sums was I think a key step. Is this an argument that you have seen used elsewhere before? $\endgroup$ Mar 29 '18 at 4:27
  • $\begingroup$ Sorry, I don't have any specific references. I think some version of "find an easy bound, then work out what happens to it as you subdivide" is present in most calculations involving Riemann sums (at least, most of the ones I'm capable of coming up with...) $\endgroup$
    – Micah
    Mar 29 '18 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.