南京大学：《概率论与数理统计 Probability and Statistics》课程教学资源（PPT课件讲稿）Lecture 06 概率化方法（主讲：唐斌）

1 概率化方法

概率化方法 1

概率化方法(Probabilistic Method) 2 WILEY 口一种用概率证明存在性的方法。 口先驱者：Paul Erd6s THE PROBABILISTIC METHOD Third Edition Noga Alon Joel H.Spencer WWw. wiley-laterscleace Series in Discrete Hathemutics an Optimization

概率化方法(Probabilistic Method)  一种用概率证明存在性的方法。  先驱者：Paul Erdős 2

概率化方法(Probabilistic Method) 3 口从盒子中随机选一个球 P(该球是蓝色的)>0 →盒中有蓝球 概率化方法： 定义一样本空间2及性质P:2→{0,1}： P(P=1)>0→x∈2.P(x)=1

概率化方法(Probabilistic Method)  从盒子中随机选一个球 𝑷 该球是蓝色的 > 𝟎 ⇒ 盒中有蓝球 3 概率化方法： 定义一样本空间𝛀及性质𝓟: 𝛀 → {𝟎, 𝟏}： 𝑷 𝓟 = 𝟏 > 𝟎 ⇒ ∃𝒙 ∈ 𝛀.𝓟(𝒙) = 𝟏

Ramsey数 4 Ramsey定理： 任意6个人中，必有3个人互相认识或互不认识。 图论语言：对K62-边着色， 则存在同色的K3 0 Ramsey数R(k,k):最小 的n,使得对Kn的任意2- 边着色中，均存在同色的 Kk

Ramsey数  图论语言：对𝑲𝟔2-边着色， 则存在同色的𝑲𝟑  Ramsey数𝑹(𝒌, 𝒌)：最小 的𝒏，使得对𝑲𝒏的任意2- 边着色中，均存在同色的 𝑲𝒌 4 Ramsey定理： 任意6个人中，必有3个人互相认识或互不认识

R(k,)的一个下界 5 定理(Erd6s1947) 如果()21-（⑤）0， →从而存在对Kn的某种2-边着色，其不含同色的Kk子图 推论：对所有k≥3，R(k,k)>l2k/2」

𝑹(𝒌, 𝒌)的一个下界  证：对每一条边𝒆 ∈ 𝑲𝒏独立随机着色，即以1/2的概率 着红色，1/2的概率着蓝色。 给定一𝑲𝒌子图， 𝑷 该𝑲𝒌同色 = 𝟐 𝟏− 𝒌 𝟐 ⟹ 𝑷 存在同色𝑲𝒌子图 ≤ 𝒏 𝒌 𝟐 𝟏− 𝒌 𝟐 𝟎, ⟹从而存在对𝑲𝒏的某种2-边着色，其不含同色的𝑲𝒌子图 5 定理(Erdős 1947) 如果 𝒏 𝒌 𝟐 𝟏− 𝒌 𝟐 ⌊𝟐 𝒌/𝟐 ⌋

竞赛图 6 o有向图T(V,E) 口n个玩家，每一对玩家有一场比赛 口u指向v当且仅当u打败v 1 口k矛盾： 口对于任意k子集ScV,存在一个不属 于S的玩家打败了所有S中的玩家 3 口问题：对于每一个有穷的k,是否 总存在一个k矛盾的竞赛图？

竞赛图  有向图𝑻 𝑽,𝑬  𝒏个玩家，每一对玩家有一场比赛  𝒖指向𝒗当且仅当𝒖打败𝒗  𝒌矛盾:  对于任意𝒌子集𝑺 ⊂ 𝑽,存在一个不属 于𝑺的玩家打败了所有𝑺中的玩家  问题：对于每一个有穷的𝒌，是否 总存在一个𝒌矛盾的竞赛图？ 6

飞矛盾的竞赛图的存在性 问：对任意有穷的k,是否总存在一个k矛盾的竞赛图？ 定理(Erd6s1947) 若()(1-2-k)”-k 0 即存在一个k矛盾的竞赛图

𝒌矛盾的竞赛图的存在性 问：对任意有穷的𝒌，是否总存在一个𝒌矛盾的竞赛图？ 7 定理(Erdős 1947) 若 𝒏 𝒌 𝟏 − 𝟐 −𝒌 𝒏−𝒌 𝟎 即存在一个𝒌矛盾的竞赛图

期望论证 8 若班级学生的平均身高为L,则存在一个同学其 身高≥I(≤). max avg min 市 口对随机变量X,设E[X]= ▣P(X≥)>0 ▣P(X≤)>0

期望论证  若班级学生的平均身高为𝒍，则存在一个同学其 身高≥ 𝒍 (≤ 𝒍).  对随机变量𝑿，设𝑬 𝑿 = 𝝁  𝑷 𝑿 ≥ 𝝁 > 𝟎  𝑷 𝑿 ≤ 𝝁 > 𝟎 8

竞赛图中的哈密尔顿路径 9 口哈密尔顿路径： 口恰好访问每一个节点一次的路径 口哈密尔顿路径的数目能达到多少？ 定理(Szele1943) 存在包含至少n!2(n-1D条哈密尔顿路径的n个玩家的竞赛图

竞赛图中的哈密尔顿路径  哈密尔顿路径：  恰好访问每一个节点一次的路径  哈密尔顿路径的数目能达到多少？ 9 定理(Szele 1943) 存在包含至少𝒏! 𝟐 − 𝒏−𝟏 条哈密尔顿路径的𝒏个玩家的竞赛图

竞赛图中的哈密尔顿路径 10 定理(Szele1943) 存在包含至少n!2(n-1D条哈密尔顿路径的n个玩家的竞赛图。 口随机选取定义在n个玩家上的竞赛图T([n],E) 令X表示T中包含的哈密尔顿路径数目 ▣考虑[n]的置换π，定义 1 X元= π是哈密尔顿路径 π不是哈密尔顿路径 E[X元]=P(Xm=1)=2-(n-1) Ex=∑Exxl=2-m-)

竞赛图中的哈密尔顿路径  随机选取定义在𝒏个玩家上的竞赛图𝑻 [𝒏],𝑬  令𝑿表示𝑻中包含的哈密尔顿路径数目  考虑[𝒏]的置换𝝅,定义 𝑿𝝅 = ቊ 𝟏 𝝅是哈密尔顿路径 𝟎 𝝅不是哈密尔顿路径 𝑬 𝑿𝝅 = 𝑷 𝑿𝝅 = 𝟏 = 𝟐 − 𝒏−𝟏 𝑬 𝑿 = ෍ 𝝅 𝑬 𝑿𝝅 = 𝒏! 𝟐 − 𝒏−𝟏 10 定理(Szele 1943) 存在包含至少𝒏! 𝟐 − 𝒏−𝟏 条哈密尔顿路径的𝒏个玩家的竞赛图