《离散概率方法》研究生课程参考资料（书籍文献）The Probabilistic Method（Lecture Notes，Jiří Matoušek、Jan Vondrák）

The Probabilistic Method Lecture Notes JIRi MATOUSEK JAN VONDRAK ied Mathematics 1.25 Czech Republic If you find errors,please let us kn (e-mail:matousek@kam.mff.cuni.cz) Rev.March 2008

The Probabilistic Method Lecture Notes Jiří Matoušek Jan Vondrák Department of Applied Mathematics Charles University Malostranské nám. 25 118 00 Praha 1 Czech Republic If you find errors, please let us know! (e-mail: matousek@kam.mff.cuni.cz) Rev. March 2008

Table of Contents 1 Preliminaries 6 1.1 Probability Theory..........................6 1.2 Useful Estimates 9 2 The Probabilistic Method 11 2.1 Ramsey Numbers.... 11 2.2 Hypergraph Coloring. 2.3 The Erdos-Ko-Rado Theorem.......... 15 2.4 Pairs of Sets... 16 3 Linearity of Expectation 18 3.1 Computing Expectation Using Indicators............. 18 3.2 Hamiltonian Paths........................l9 3.3 Splitting Graphs 。。。 4 Alterations 21 4.1 Independent Sets 4.2 High Girth and High Chromatic Number.............22 5 The Second Mo ent 24 . Variance and the Chebyshev Inequality 5.2 Estimating the Middle Binomial Coefficient··,,,··,·,,·25 5.3 Threshold Functions...·...··.·.:······。····· 26 5.4 The Clique Number......................,.. 29 6 The Lovasz Local Lemma 33 0.1 Statement and Proof 33 6.2 ypergraph Coloring Again···...··.·...·.··..··36 6.3 Directed Cycles,...,...,......,,,.,,..,.., 36 6.4 Ridiculous Iniections......................... 37 6.5 Coloring of Real Numbers...................... 7 Strong Concentration Around the Expectation 7.1 Sum of Independent Uniform+1 Variables. 7.2 Sums of Bounded Independent Random Variables.,··,··.. 42 7.3 A Lower Bound For the Binomial Distribution····.·.···45 7.4 Sums of Moderately Dependent Indicator Variables........48

Table of Contents 1 Preliminaries 6 1.1 Probability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Useful Estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 The Probabilistic Method 11 2.1 Ramsey Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Hypergraph Coloring . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 The Erd˝os–Ko–Rado Theorem . . . . . . . . . . . . . . . . . . . 15 2.4 Pairs of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 Linearity of Expectation 18 3.1 Computing Expectation Using Indicators . . . . . . . . . . . . . 18 3.2 Hamiltonian Paths . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3 Splitting Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4 Alterations 21 4.1 Independent Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 High Girth and High Chromatic Number . . . . . . . . . . . . . 22 5 The Second Moment 24 5.1 Variance and the Chebyshev Inequality . . . . . . . . . . . . . . 24 5.2 Estimating the Middle Binomial Coefficient . . . . . . . . . . . . 25 5.3 Threshold Functions . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.4 The Clique Number . . . . . . . . . . . . . . . . . . . . . . . . . 29 6 The Lovász Local Lemma 33 6.1 Statement and Proof . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.2 Hypergraph Coloring Again . . . . . . . . . . . . . . . . . . . . . 36 6.3 Directed Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.4 Ridiculous Injections . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.5 Coloring of Real Numbers . . . . . . . . . . . . . . . . . . . . . . 38 7 Strong Concentration Around the Expectation 40 7.1 Sum of Independent Uniform ±1 Variables . . . . . . . . . . . . . 41 7.2 Sums of Bounded Independent Random Variables . . . . . . . . . 42 7.3 A Lower Bound For the Binomial Distribution . . . . . . . . . . 45 7.4 Sums of Moderately Dependent Indicator Variables . . . . . . . . 48

8 Concentration of Lipschitz Functions 51 8.1 Concentration on Product Spaces.. .......51 8.2 Concentration of Lipschitz Functions,With a Proof.. ...54 8.3 Martingales,Azuma's Inequality,and Concentration on Permu- tations 8.4 Isoperimetric Inequalities and Concentration on the Sphere...61 9 Concentration:Beyond the Lipschitz Condition 9.1 Talagrand's Inequality·.,,,,·.···.··,,,··,·,64 9.2Theu-Kim Inequality.....··.。..。..········68

8 Concentration of Lipschitz Functions 51 8.1 Concentration on Product Spaces . . . . . . . . . . . . . . . . . . 51 8.2 Concentration of Lipschitz Functions, With a Proof . . . . . . . . 54 8.3 Martingales, Azuma’s Inequality, and Concentration on Permu￾tations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 8.4 Isoperimetric Inequalities and Concentration on the Sphere . . . 61 9 Concentration: Beyond the Lipschitz Condition 64 9.1 Talagrand’s Inequality . . . . . . . . . . . . . . . . . . . . . . . . 64 9.2 The Vu–Kim Inequality . . . . . . . . . . . . . . . . . . . . . . . 68

Preface These are notes to a lecture taught by J.Matousek at Charles University in Prague fors rs The ere students of mathe ter science,u Generally speaking.an introductory text on the probabilistic method is rather ous,since at least two excellent sources are available:the be J.Spencer:Ten lectures on the probabilistic method,CBMS-NSF, SIAM,Philadelphia,PA,1987 and the more modern and more extensive but no less readable N.Alon and J.Spencer:The Probabilistic Method,J.Wiley and Sons,New York,NY,2nd edition,2000. The lecture was indeed based on these.However,these books were not generally available to students in Prague,and this was the main reason for starting with the present notes.For students,the notes may have another advantage too: they cover the material usually presented in the course relatively concisely. Chapters 8 and 9 go beyond the usual scope of the course and present,mostly without proofs,more recent and more advanced results on strong concentration Our presentation is slightly more formal in some cases and includes a brief review of the relevant probability theory notions.This keeps with the Prague mathematical tradition and should be closer to the presentation the students are used to from other math courses.Teaching experience also shows that the students'proficiency in application of the notions learned in probability theory is limited and that it is useful to demonstrate concrete applications of abstract probabilistic notions in some detail. The techniques are usually illustrated with combinatorial examples.The notation and definitions not introduced here can be found in the book J.Matousek and J.Nesetril:Invitation to Discrete Mathematics, Oxford University Press,Oxford 1998 (Czech version:Kapitoly z diskretni matematiky,Nakladatelstvi Karolinum 2000). A large part of the material is taken directly from the Alon-Spencer book cited above,sometimes with a little different presentation.Readers wishing to pursue the subject in greater depth are certainly advised to consult that book. A more advanced source is

Preface These are notes to a lecture taught by J. Matoušek at Charles University in Prague for several years. The audience were students of mathematics or compu￾ter science, usually with interest in combinatorics and/or theoretical computer science. Generally speaking, an introductory text on the probabilistic method is rather superfluous, since at least two excellent sources are available: the beau￾tiful thin book J. Spencer: Ten lectures on the probabilistic method, CBMS-NSF, SIAM, Philadelphia, PA, 1987 and the more modern and more extensive but no less readable N. Alon and J. Spencer: The Probabilistic Method, J. Wiley and Sons, New York, NY, 2nd edition, 2000. The lecture was indeed based on these. However, these books were not generally available to students in Prague, and this was the main reason for starting with the present notes. For students, the notes may have another advantage too: they cover the material usually presented in the course relatively concisely. Chapters 8 and 9 go beyond the usual scope of the course and present, mostly without proofs, more recent and more advanced results on strong concentration. Our presentation is slightly more formal in some cases and includes a brief review of the relevant probability theory notions. This keeps with the Prague mathematical tradition and should be closer to the presentation the students are used to from other math courses. Teaching experience also shows that the students’ proficiency in application of the notions learned in probability theory is limited and that it is useful to demonstrate concrete applications of abstract probabilistic notions in some detail. The techniques are usually illustrated with combinatorial examples. The notation and definitions not introduced here can be found in the book J. Matoušek and J. Nešetřil: Invitation to Discrete Mathematics, Oxford University Press, Oxford 1998 (Czech version: Kapitoly z diskrétní matematiky, Nakladatelství Karolinum 2000). A large part of the material is taken directly from the Alon–Spencer book cited above, sometimes with a little different presentation. Readers wishing to pursue the subject in greater depth are certainly advised to consult that book. A more advanced source is

5 S.Janson,T.Luczak,A.Rucirski:Topics in random graphs,J. Wiley and Sons,New York,NY,2000. very nice book on probabilistic algorithms,also including a chapter on the method per se,is R.Motwani and P.Raghavan:Randomized Algorithms,Cambridge University Press,Cambridge.1995. Two journals in whose scope the probabilistic method occupies a central place are Random Structures Algorithms and Combinatorics,Probability Com- puting.Papers with applications of the probabilistic method are abundant and can be found in many other journals too. A note for Czech students.Teorie pravdepodobnosti,podobne jako jine matematicke discipliny,ma ustalenou zakladni ceskou terminologii,ktera se v mnoha pripadech neshoduje s doslovnym prekladem terminologie anglicke.Do textu jsme zahrnuli nektere ceske terminy jako poznamky pod carou,abychom nepodporovali bujeni obratu typu "ocekavana hodnota",cozje doslovny preklad anglickeho "expectation",misto spravneho stredni hodnota

5 S. Janson, T. Luczak, A. Ruci´nski: Topics in random graphs, J. Wiley and Sons, New York, NY, 2000. A very nice book on probabilistic algorithms, also including a chapter on the probabilistic method per se, is R. Motwani and P. Raghavan: Randomized Algorithms, Cambridge University Press, Cambridge, 1995. Two journals in whose scope the probabilistic method occupies a central place are Random Structures & Algorithms and Combinatorics, Probability & Com￾puting. Papers with applications of the probabilistic method are abundant and can be found in many other journals too. A note for Czech students. Teorie pravděpodobnosti, podobně jako jiné matematické disciplíny, má ustálenou základní českou terminologii, která se v mnoha případech neshoduje s doslovným překladem terminologie anglické. Do textu jsme zahrnuli některé české termíny jako poznámky pod čarou, abychom nepodporovali bujení obratů typu “očekávaná hodnota”, což je doslovný překlad anglického “expectation”, místo správného střední hodnota