# Nonlinear approximation by piecewise constants and the expectation of the error

Suppose $$\Omega=[0,1]$$ and $$f$$ is continuous, monotonic, and of bounded variation on $$\Omega$$ with $$M:= \text{Var}_\Omega(f).$$

Let $$\| \cdot\|:=\| \cdot\|_{L_\infty(\Omega)}.$$ Let $$T=\{0=t_0,...,t_n=1\}$$ be the uniform partition of the range of $$f,a_k$$ is the average of the function values at the endpoints on $$[f^{-1}(t_{k-1}),f^{-1}(t_k)],$$ and $$S_n(x):=a_k,x\in[f^{-1}(t_{k-1}),f^{-1}(t_k)),k=1,...,n.$$ Then there is a theorem says that$$\|f-S_n\|\le M/2n.$$

The above theorem uses the uniform partition of the range. Now if we use a random partition of the range of $$f$$ and assume the partition points $$t_i \sim U(0,1),$$ where $$i=1,..,n-1.$$ Can we get the result $$E(\| f-S_n\|)\le C/n$$ for some constant $$C$$? How to prove or disprove it? I have trouble expressing the expectation explicitly.

I showed that the expectation of the length of each subinterval is $$1/n.$$ But I am not sure if the result is useful.

• I don't entirely understand how $S_n$ is constructed when $f$ isn't injective. Is it that wherever $t_{k-1}<f(x)<t_k$, $S_n(x)=\frac{t_{k-1}+t_k}{2}$? Or do you take the median operation in the domain instead, so that the partition of the range induces a partition of the domain and then you approximate $f$ on that partition of the domain using the midpoint rule? – Ian Jan 10 at 21:06
• (Also, I guess the domain and range of $f$ are both $[0,1]$? This isn't clear from what you wrote.) – Ian Jan 10 at 21:09
• @Ian Thank you very much. I already changed the problem. $f$ is monotonic. – XYZ Jan 10 at 22:00
• OK. So is "the median value" $f$ at the median, or the average of the function values at the endpoints? It seems like it must be the latter because the former would not give your result (consider $n=1$ and $f(x)=x^N$ for some large $N$). – Ian Jan 10 at 22:15
• @Ian. Yes, thank you very much for your suggestion. Also, I changed the statement that I want to prove. – XYZ Jan 10 at 22:32