The median method is an amplification result for randomized
approximation algorithms described in [1].
Given an algorithm whose result is in a desired interval with a
probability larger than *1/2*, it is possible to
improve the success probability, by running the algorithm multiple
times independently and using the median. In contrast to using the
mean, the amplification of the success probability grows exponentially
with the number of independent runs. This entry
contains a formalization of the underlying theorem: Given a sequence
of n independent random variables, which are in a desired interval
with a probability *1/2 + a*. Then their median will
be in the desired interval with a probability of *1 −
exp(−2a*^{2} n). In particular, the
success probability approaches *1* exponentially with
the number of variables. In addition to that, this
entry also contains a proof that order-statistics of Borel-measurable
random variables are themselves measurable and that generalized
intervals in linearly ordered Borel-spaces are measurable. |