Abstract
Suppose that one observes independent random variables (X1, Y1), (X2, Y2), …, (Xn, Yn) in R2 with unknown distributions, except that Median(Yi | Xi = M(x) for some unknown isotonic function M. We describe an explicit algorithm for the computation of confidence bands for the median function M whose running time is of order O(n2). The bands rely on multiscale sign tests and are shown to have desirable asymptotic properties.