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.

  • $\begingroup$ 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? $\endgroup$ – Ian Jan 10 at 21:06
  • $\begingroup$ (Also, I guess the domain and range of $f$ are both $[0,1]$? This isn't clear from what you wrote.) $\endgroup$ – Ian Jan 10 at 21:09
  • $\begingroup$ @Ian Thank you very much. I already changed the problem. $f$ is monotonic. $\endgroup$ – XYZ Jan 10 at 22:00
  • $\begingroup$ 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$). $\endgroup$ – Ian Jan 10 at 22:15
  • $\begingroup$ @Ian. Yes, thank you very much for your suggestion. Also, I changed the statement that I want to prove. $\endgroup$ – XYZ Jan 10 at 22:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.