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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.