I encountered the following excercise in a book:

Exercise: Given a Lipschitz continuous function $f$ on $[0,1]$, with Lipschitz constant $c$.

Show that $|B_{n,f}(p) - f(p)|\le \frac{c}{2\sqrt{n}}$ for all $p\in[0,1]$, where $B_{n,f}$ is the Bernstein polynomial of order $n$ constructed from $f$.

The exercise also gives the following hint:

$B_{n,f}(p) = \mathbf{E}[f(X/n)]$, where $X$ is a random variable with binomial distribution for $n$ trials with success probability $p$.

I got this far:

$$ \begin{align} \left\lvert B_{n,f}(p) - f(p)\right\rvert = \left\lvert \mathbf{E}\left[f\left(\frac{X}{n}\right)\right] - f(p)\right\rvert &= \left\lvert \mathbf{E}\left[f\left(\frac{X}{n}\right) - f(p)\right]\right\rvert \label{1} \\ &\le \mathbf{E}\left[\left\lvert f\left(\frac{X}{n}\right) - f(p)\right\rvert\right] & (|\cdot|\,\text{ is convex}) \\ &\le \mathbf{E}\left[c\left\lvert \frac{X}{n} - p\right\rvert\right] & (\text{Lipschitz continuity}) \\ &=c\cdot \mathbf{E}\left[\left\lvert \frac{X}{n} - p\right\rvert\right] \end{align} $$

So it remains to show that $\mathbf{E}\left[\left\lvert \frac{X}{n} - p\right\rvert\right] \le \frac{1}{2\sqrt{n}}$. I could not figure out how to proceed from this point. Any help will be appreciated.


The variance of $X$ is $np(1-p) \le n/4$. And since the variance is $E[|X-np|^2]$, it follows that $$E[|X/n -p|^2] =\frac1{n^2}E[|X-np|^2] \le \frac{1}{4n}$$ Then apply the Cauchy-Schwarz inequality.


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.