【干货书】概率方法，第三版，373页pdf

概率论方法是组合数学中应用最广泛、最有力的工具之一。其快速发展的主要原因之一是随机性在理论计算机科学和统计物理中的重要作用。离散数学和计算机科学之间的相互作用，让我们从算法的角度来研究组合数学中的概率方法，这也是我们在本书中尝试采用的方法。因此，本书包括了对算法技术的讨论，以及对经典方法和应用于其中的现代工具的研究。本书的第一部分描述了应用于概率论证的工具，包括使用期望和方差的基本技术，以及鞅和相关不等式的最新应用。第二部分包括对概率技术已取得成功的各种主题的研究。这一部分包含关于差异和随机图的章节，以及理论计算机科学的几个领域:电路复杂性、计算几何和随机算法的去随机化。本书各章中都有概率透镜(Probabilistic lenses)这一标题下的精彩描述。这些都是优雅的证明，不一定与后面的章节有关，通常可以单独阅读。基本的概率方法可以描述为:为了证明具有某些性质的组合结构的存在性，我们构造一个适当的概率空间，并证明在该空间中随机选择的元素以正概率具有所期望的性质。这种方法是由保罗·厄多斯(Paul Erdos)发起的，他在50多年的时间里对这种方法的发展做出了巨大贡献，因此将其称为“厄多斯方法”似乎很合适。他的贡献不仅可以从他在该领域取得的大量深入成果来衡量，还可以从他提出的许多有趣的问题和猜想来衡量，这些问题和猜想刺激了该领域的很大一部分研究。