機率方法（probabilistic method）

假設你想證明某個具有所需性質的物件存在——比如一種座位安排，使得沒有兩個敵人相鄰而坐——但你完全不知道怎麼造出一個。機率方法提供一種側面的證明：與其建構那個物件，不如想像造一個隨機的，並證明那性質以正機率成立。若隨機選擇哪怕只有極小一部分的時間成功，那麼至少必有一個成功的物件存在，即使你從未指出它是哪一個。

精確地說，核心想法有兩種常見形式。第一種：若你隨機挑一個物件、而它具有所需性質的機率大於 0，則具有該性質的物件存在（因為若不存在任何這樣的物件，就需要一個機率為零的事件）。第二種，往往更銳利，使用期望：若一個隨機物件對某量 X 的期望為 E[X]，則某個物件有 X 至少為 E[X]，且某個物件有 X 至多為 E[X]——因為沒有一個集合能讓它所有成員都嚴格低於自己的平均。一個著名例子：在任何圖中，用獨立的公正硬幣把每個頂點塗成紅或藍；一條邊被「割開」（其端點不同色）的機率為二分之一，因此由線性，被割邊數的期望是所有邊的一半，這意味著存在某種塗色割開至少一半的邊。這立刻證明了存在一個大小至少為 m/2 的最大割，而不需任何建構。

機率方法之所以重要，是因為它能在直接建構困難或未知時證明存在性，而且它常常暗藏一個演算法：若一個隨機物件以不錯的機率有效，就不斷產生隨機物件直到一個有效為止（一個拉斯維加斯演算法），而集中界或巧妙的條件化有時能讓搜尋變得高效、甚至確定性（條件期望法）。它是卡格最小割與許多隨機建構的概念根源。誠實的提醒：它證明某物存在卻不告訴你是哪一個——這是純粹的存在性證明。把它變成高效演算法需要額外工夫，而當成功機率指數般小時，樸素的隨機搜尋慢到不切實際。