For your first question, Rigollet has a series of notes(with minor typos) that dicusses basics of this kind of tail bounds. The result you mentioned in the "introduction" is actually the classic Hoeffding bound that mentioned by Rigollet in this set of notes. > High Dimensional Statistics, Philippe Rigollet (2015) > http://www-math.mit.edu/~rigollet/PDFs/RigNotes15.pdf If you are concerned with the order statistics, you usually want to restrict yourself to a narrower class of distributions, say the classic paper [2]. For a general distribution family, it is almost impossible to obtain a tail-bound on the order statistics due to the concentration of measures phenomenon. Another keyword you may want to look into is "U-statistics" because the (full) order statistic is an example of U-statistics, the following quote from [1] is the best description of the power of U-statistics > Theoretically, for these U-statistics we can study the whole spectrum > of asymptotic problems which were investigated for independent > variables. As a matter of fact, it is necessary to control the nature > of dependence in order to obtain meaningful results. We restrict > ourselves to exchangeable and weakly exchangeable variables, rank > statistics, samplings from finite populations, weakly dependent random > variables, bootstrap-variables, and to order statistics.[1]p.15 Concentration bounds on U-statistics is a research subject that involves many false claims and hardcore techniques, so I think it is not too hard to find one but never too careful to use one. **Reference** [1]Korolyuk, Vladimir S., and Yu V. Borovskich. Theory of U-statistics. Vol. 273. Springer Science & Business Media, 2013. [2] Gupta, S. Das, et al. "Inequalities on the probability content of convex regions for elliptically contoured distributions." Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971). Vol. 2.1972.