Probabilistic Method——“概率方法”,看名字会以为是关于概率论,实则关于组合数学。是用概率的方法来证明特定组合结构的存在性。
这乍一听似乎有点玄。概率起源于对随机事件的刻画,可是组合对象的存在性却是个确定的数学真相——真相只有一个(对于有穷结构而言),这都是板上钉钉的事实,哪里来的随机和概率呢。
可这probabilistic method背后的思想却其实并不难理解。打个比方:有一间屋子,里面很多人,我们想知道老张在不在里面(存在“老张”于这间屋子中?),probabilistic method的办法就是,如果随机在这屋里抓个人,若此人为老张之概率是大于0的,那老张必然在这屋里。
这几乎是句废话。是一个就算不懂概率的人也会明白的朴素真理。
可是就这么一个显而易见的道理,却直到现代才被广泛的被用于数学证明,并且体现出了非凡的强大。
发现它的就是大名鼎鼎的Paul Erdős。在他之前曾有人不经意的使用过这个方法,但Erdős是第一个把probabilistic method作为一种数学工具发扬光大,推广到整个数学界的。后来的事实证明了,Erdős的数学敏感和审美,不仅为我们贡献了一个强大的数学工具,也发掘了这种重要的数学思想。
我们如果想要知道是否存在具有某种特定结构的组合对象,例如对于任意一个n个节点、m条边的图(graph),必然存在多大的独立集(Turán定理);在此之前,人们普遍做的就是去构造出这样一个结构。可是大伙都知道,作数学证明,最难的就是去“构造”——小时候大伙最愁的就是几何证明引辅助线。并不是每个人都有Ramanujan一般的天才,在睡梦中猜到正确答案。
probabilistic method拯救了非天才们“构造”的梦魇。为了证明一个东西的存在性,我们不必去挖空心思的构造,只要定义一个概率空间,然后用概率工具来分析那个东西的概率测度。
但这一切,又是如何与计算机科学联系起来的呢。
理论计算机科学,关注的一个重要主题之一,就是不同计算模型的能力。而离散的计算模型上之计算(computation)往往受制于模型的特定组合结构,因此理解计算的界限,需得刻画这些结构,尤其是那些可以推导出计算下界(lower bounds)的结构,例如判定树(decision tree)之于基于比较的排序(comparison-based sorting)。在很多更复杂的情况下,这些下界结构的存在性并不明显,但对于刻画计算能力却是至关重要的。
这本"probabilistic method"就是关于这些学问的书。
书的作者Alon和Spencer。在计算机科学家中,他们是数学家;而在数学家当中,他们又算是“非主流”趣味的、“搞计算机”的。对于他们更合适的称号是Combinatorist(组合数学家),这是一个主要由以色列人和匈牙利人组成的小俱乐部。
书分为两部分。第一部分"methods",介绍probabilistic method的基本方法和变换,以及应手的概率工具:deviation bounds, concentrations, correlations, 和那个强大的local lemma。对每个工具的介绍,都会伴以一些组合数学定理的证明,让读者熟悉这个工具的使用。书的第二部分"topics",则介绍probabilistic method在理论计算机科学中的应用,对几个理论计算机科学的主题例如random graphs, circuit complexity等都有所涉及。
此书的语言精练至极。选题考究。这决不是一本可以用来“随便翻翻”的“速成”读物,但却可以在某个阴雨绵绵的午后,让你在专注和愉悦中打发整个下午。
结构(structure)和随机(randomness),在我看来,是数学中两个美丽的东西,这本书二者皆具。