de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Stochastic majorisation: exploding some myths

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45258

Ranjan,  Desh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

MPI-I-94-144.pdf
(beliebiger Volltext), 5MB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Dubhashi, D. P., & Ranjan, D.(1994). Stochastic majorisation: exploding some myths (MPI-I-94-144). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-B79D-E
Zusammenfassung
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.