hide
Free keywords:
-
Abstract:
The analysis of many randomised algorithms involves random variables
that are not independent, and hence many of the standard tools from
classical probability theory that would be useful in the analysis,
such as the Chernoff--Hoeffding bounds are rendered
inapplicable. However, in many instances, the random variables
involved are, nevertheless {\em negatively related\/} in
the intuitive sense that when one of the variables is ``large'',
another is likely to be ``small''. (this notion is made precise and
analysed in [1].) In such situations, one is tempted to
conjecture that these variables are in some sense {\em stochastically
dominated\/} by a set of {\em independent\/} random variables with the
same marginals. Thereby, one hopes to salvage tools such as the
Chernoff--Hoeffding bound also for analysis involving the dependent
set of variables. The analysis in [6, 7, 8] seems to strongly
hint in this direction. In this note, we explode myths of this kind, and
argue that stochastic majorisation in conjunction with an independent
set of variables is actually much less useful a notion than it might
have appeared.
