Confidence Bands for Convex Median Curves using Sign-Tests

Suppose that one observes pairs (x1,Y1), (x2,Y2), ..., (xn,Yn), where x1 < x2 < ... < xn are fixed numbers while Y1, Y2, ..., Yn are independent random variables with unknown distributions. The only assumption is that Median(Yi) = f(xi) for some unknown convex or concave function f. We present a confidence band for this regression function f using suitable multiscale sign tests. While the exact computation of this band seems to require O(n4) steps, good approximations can be obtained in O(n2) steps. In addition the confidence band is shown to have desirable asymptotic properties as the sample size n tends to infinity.