How can bootstrap be used to establish confidence intervals for Theil regression parameters?

In References for methods for calculating the confidence interval for Theil-Sen Estimator, we note that Wilcox (1998, 2009?) proposed the use of bootstrap as a method for finding confidence intervals for Theil regression of heteroscedastic conditions. There is a practical problem doing this and that is the treatment of ties. That is, since bootstrap is sampling with replacement, it is probable to eventually sample the same point twice leading to an indeterminate slope pair. Thus, we need to either discard indeterminate results or use something else, for example a variant of leave n/2 out.

Q1: How do we resolve the indeterminate bootstrap problem for Theil regression?

Possible answers: Heretofore unspecified correction for ties. Incomplete Jackknife of n/2 samples (e.g., I have 412 samples, leave out 206 cannot be completely re-sampled as the combination of 412 samples taken 206 at a time is a geological time to completion answer competitive with the age of the universe on my pc. Moreover, leave one out would not be very useful for establishing confidence intervals).

BTW, leave half out appears to work +/- circa 7% on Monte-Carlo simulation of my data. However, that is a far cry from proving that the leave half out approach is valid.

Any clarification would be welcome.

• I am not familiar with the basic Theil-Sen estimator algorithm in practice, but Wikipedia says essentially "Theil = median slope $\Delta y/\Delta x$ over all pairs of sample points", while "Sen = median over all pairs of sample points with $\Delta x \neq 0$". So the bootstrap part of the question seems un-needed to encounter the basic problem (actually, since neither description says distinct points, the Sen version could still have this difficulty). Generalizing Sen would just assign 0 weight to point-pairs with the same point. – GeoMatt22 Sep 17 '16 at 17:53
• @GeoMatt Sen makes undesirable assumptions concerning the distribution of slopes that I believe to be not useful in the majority of cases, including mine. Sen uses all distinct pairs of sample points, but bootstrap has to have replacement of points without uniqueness to be usable. – Carl Sep 17 '16 at 18:41
• @GeoMatt Indeed, it would seem that the problems with the Sen estimator is what led Wilcox to propose bootstrap in 1998. – Carl Sep 17 '16 at 18:57
• If you have whatever procedure that allows you to compute a single realization of the estimator, then that procedure will take a median over some empirical distribution of pairs of points. So why not just do bootstrap resampling on that point-pairs PDF? (vs. drawing each point of a pair independently). In other words you bootstrap the PDF of slopes. – GeoMatt22 Sep 17 '16 at 21:22
• Anyway, I am not clear on what the underlying "model" for Theil-Sen regression is. For what it's worth, if I care about robustness, I will typically just use a robust residual norm (e.g. an M-estimator). If I care about "errors in variables", I will typically use TLS. For both, I'd probably do RANSAC, but if I needed a well-defined parametric model, I'd probably do a combo, using "TLS" with a robust norm. – GeoMatt22 Sep 17 '16 at 21:48