LEADER 04128nam  22007452  450 
001 9910819144403321
005 20151005020622.0
010   $a1-107-20031-8
010   $a1-139-63769-X
010   $a1-282-30277-9
010   $a9786612302770
010   $a0-511-58063-0
010   $a0-511-58095-9
010   $a0-511-57955-1
010   $a0-511-57881-4
010   $a0-511-58127-0
010   $a0-511-58029-0
035   $a(CKB)1000000000784190
035   $a(EBL)451942
035   $a(OCoLC)609842926
035   $a(SSID)ssj0000128137
035   $a(PQKBManifestationID)11936945
035   $a(PQKBTitleCode)TC0000128137
035   $a(PQKBWorkID)10063487
035   $a(PQKB)11141035
035   $a(UkCbUP)CR9780511581274
035   $a(Au-PeEL)EBL451942
035   $a(CaPaEBR)ebr10333193
035   $a(OCoLC)438728734
035   $a(MiAaPQ)EBC451942
035   $a(PPN)150194013
035   $a(EXLCZ)991000000000784190
100   $a20090604d2009||||  uy|         0
101 0 $aeng
135   $aur|||||||||||
181   $ctxt$2rdacontent
182   $cc$2rdamedia
183   $acr$2rdacarrier
200 10$aConcentration of measure for the analysis of randomized algorithms /$fDevdatt Dubhashi, Alessandro Panconesi
205   $a1st ed.
210  1$aCambridge :$cCambridge University Press,$d2009.
215   $a1 online resource (xiv, 196 pages) $cdigital, PDF file(s)
300   $aTitle from publisher's bibliographic system (viewed on 05 Oct 2015).
311   $a1-107-60660-8 
311   $a0-521-88427-6 
320   $aIncludes bibliographical references (p. 189-193) and index.
327   $aChernoff-Hoeffding bounds -- Applications of the Chernoff-Hoeffding bounds -- Chernoff-Hoeffding bounds in dependent settings -- Interlude : probabilistic recurrences -- Martingales and the method of bounded differences -- The simple method of bounded differences in action -- The method of averaged bounded differences -- The method of bounded variances -- Interlude : the infamous upper tail -- Isoperimetric inequalities and concentration -- Talagrand's isoperimetric inequality -- Isoperimetric inequalities and concentration via transportation cost inequalities -- Quadratic transportation cost and Talagrand's inequality -- Log-Sobolev inequalities and concentration -- Appendix A : summary of the most useful bounds.
330   $aRandomized algorithms have become a central part of the algorithms curriculum, based on their increasingly widespread use in modern applications. This book presents a coherent and unified treatment of probabilistic techniques for obtaining high probability estimates on the performance of randomized algorithms. It covers the basic toolkit from the Chernoff-Hoeffding bounds to more sophisticated techniques like martingales and isoperimetric inequalities, as well as some recent developments like Talagrand's inequality, transportation cost inequalities and log-Sobolev inequalities. Along the way, variations on the basic theme are examined, such as Chernoff-Hoeffding bounds in dependent settings. The authors emphasise comparative study of the different methods, highlighting respective strengths and weaknesses in concrete example applications. The exposition is tailored to discrete settings sufficient for the analysis of algorithms, avoiding unnecessary measure-theoretic details, thus making the book accessible to computer scientists as well as probabilists and discrete mathematicians.
606   $aRandom variables
606   $aDistribution (Probability theory)
606   $aLimit theorems (Probability theory)
606   $aAlgorithms
615  0$aRandom variables.
615  0$aDistribution (Probability theory)
615  0$aLimit theorems (Probability theory)
615  0$aAlgorithms.
676   $a518/.1
700   $aDubhashi$b Devdatt$01644134
702   $aPanconesi$b Alessandro
801  0$bUkCbUP
801  1$bUkCbUP
906   $aBOOK
912   $a9910819144403321
996   $aConcentration of measure for the analysis of randomized algorithms$93989811
997   $aUNINA