结构、概率、和存在性

2008-03-17 13:04:33 　　来自: etone
The Probabilistic Method的评论   

　　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)，在我看来，是数学中两个美丽的东西，这本书二者皆具。