Recursive estimation

A methodology for estimating parameters from data that arrive sequentially (and thus constitute a stochastic process, cf. also Sequential analysis). The motivation stems from real-time measurement systems in electrical engineering, and medical recording instruments. Whereas the arithmetic average and extreme values can be easily computed by updating mechanisms, the estimation of population quantiles (cf. Quantile) is a non-trivial problem. For this purpose, L. Tierney [a1] and U. Holst [a2] apply the stochastic approximation theory of H. Robbins and S. Monro [a3] (cf. also Stochastic approximation). Another approach uses quantiles of successive subsets [a4], in which case the asymptotic distribution is determined by recursive application of polynomials. A tree-based method with alternating minima and maxima is described in [a5].

References

[a1]	L. Tierney, "A space-efficient recursive procedure for estimating a quantile of an unknown distribution" SIAM J. Scient. Statist. Comp. , 4 (1983) pp. 706–711
[a2]	U. Holst, "Recursive estimation of quantiles using kernel density estimators" Sequential Anal. , 6 (1987) pp. 219–237
[a3]	H. Robbins, S. Monro, "A stochastic approximation method" Ann. Math. Stat. , 22 (1951) pp. 400–427
[a4]	P.J. Rousseeuw, G.W. Bassett, "The remedian: a robust averaging method for large data sets" J. Amer. Statist. Assoc. , 85 (1990) pp. 97–104
[a5]	J. Pearl, "A space-efficient on-line method of computing quantile estimators" J. Algorithms , 2 (1981) pp. 164–177