概率化方法.

Presentation on theme: "概率化方法."— Presentation transcript:

1 概率化方法

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

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

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

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

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

7 𝒌矛盾的竞赛图的存在性 问：对任意有穷的𝒌，是否总存在一个𝒌矛盾的竞赛图？ 证：随机取一个包含𝒏个节点的竞赛图𝑻 𝑽,𝑬
定理(Erdős 1947) 若 𝒏 𝒌 𝟏− 𝟐 −𝒌 𝒏−𝒌 <𝟏，则存在𝒏个节点的𝒌矛盾的竞赛图. 证：随机取一个包含𝒏个节点的竞赛图𝑻 𝑽,𝑬 对𝒌子集𝑺,令 𝑨 𝑺 :不存在𝑽\𝐒中玩家打败了𝑺的所有玩家 𝑷 𝑨 𝑺 = 𝟏− 𝟐 −𝒌 𝒏−𝒌 ⟹𝑷 𝑺 𝑨 𝑺 ≤ 𝑺 𝑷 𝑨 𝑺 = 𝒏 𝒌 𝟏− 𝟐 −𝒌 𝒏−𝒌 <𝟏 ⟹𝑷 𝑺 𝑨 𝒔 >𝟎 即存在一个𝒌矛盾的竞赛图.

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

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

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

11 独立集 给定图𝑮(𝑽,𝑬)，对于𝑺⊆𝑽， 若𝑺中节点互不相连，则称𝑺 为独立集(independent set) 定理
设𝑮节点数为𝒏，边数为𝒎，则𝑮有至少包含 𝒏 𝟐 𝟒𝒎 个节点的独立集。 随机选取一些节点？ 若节点数多，则很有可能不是独立集

12 采样+修改 采样：以概率𝒑独立选取每个节点，构成𝑺 修改：∀𝒖𝒗∈𝑬，若𝒖,𝒗∈𝑺则从𝑺中删除𝒖或者 𝒗中的一个，得到 𝑺 ∗
定理 设𝑮节点数为𝒏，边数为𝒎，则𝑮有至少包含 𝒏 𝟐 𝟒𝒎 个节点的独立集。 采样：以概率𝒑独立选取每个节点，构成𝑺 修改：∀𝒖𝒗∈𝑬，若𝒖,𝒗∈𝑺则从𝑺中删除𝒖或者 𝒗中的一个，得到 𝑺 ∗ 𝑺 ∗ 为独立集

13 采样+修改 采样：以概率𝒑独立选取每个节点，构成𝑺 修改：∀𝒖𝒗∈𝑬，若𝒖,𝒗∈𝑺则从𝑺中删除𝒖或者 𝒗中的一个，得到 𝑺 ∗
𝑺 ∗ 为独立集 𝑬 |𝑺| =𝒏𝒑 令𝒀表示𝑺中节点间边的数目,𝑬 𝒀 =𝒎 𝒑 𝟐 |𝑺 ∗ |≥ 𝑺 −𝒀⇒𝑬 𝑺 ∗ ≥𝒏𝒑−𝒎 𝒑 𝟐 = 𝒏 𝟐 𝟒𝒎 其中取𝒑= 𝒏 𝟐𝒎

14 腰长较大的图 腰长(girth):图中最小圈的长度 事实上，存在密集的图腰长相对较大。 直觉上，密集的图腰长较小。 定理
对于任意整数𝒌≥𝟑，存在一个具有𝒏个节点的图，其拥有至少 𝟏 𝟒 𝒏 𝟏+ 𝟏 𝒌 条边，且腰长至少为𝒌。

15 随机图(Random Graphs) 记为𝑮 𝒏,𝒑 𝑽 =𝒏 ∀𝒖,𝒗∈𝑽, 𝑷 𝒖,𝒗 ∈𝑬 =𝒑 且独立

16 腰长较大的图 采样：任选一随机图𝑮∼𝑮(𝒏,𝒑),其中𝒑= 𝒏 𝟏 𝒌 −𝟏 修改: 对𝑮中每一个长度小于𝒌的圈，删除其中 一条边(破圈)
定理 对于任意整数𝒌≥𝟑，存在一个具有𝒏个节点的图，其拥有至少 𝟏 𝟒 𝒏 𝟏+ 𝟏 𝒌 条边，且腰长至少为𝒌。 采样：任选一随机图𝑮∼𝑮(𝒏,𝒑),其中𝒑= 𝒏 𝟏 𝒌 −𝟏 修改: 对𝑮中每一个长度小于𝒌的圈，删除其中 一条边(破圈)

17 腰长较大的图 采样：任选一随机图𝑮∼𝑮(𝒏,𝒑),其中𝒑= 𝒏 𝟏 𝒌 −𝟏
采样：任选一随机图𝑮∼𝑮(𝒏,𝒑),其中𝒑= 𝒏 𝟏 𝒌 −𝟏 修改: 对𝑮中每一个长度小于𝒌的圈，删除其中 一条边(破圈),得到图 𝑮 ∗ ，其腰长至少为𝒌 分析 𝑮 ∗ 的边数𝒁: 𝑿: 𝑮中的边数，𝑬 𝑿 = 𝒏 𝟐 𝒑 𝒀：𝑮中长度小于𝒌的圈数，𝑬 𝒀 = 𝒊=𝟑 𝒌−𝟏 𝒏 𝒊 𝒊−𝟏 ! 𝟐 𝒑 𝒊 𝒁≥𝑿−𝒀 ⇒𝑬 𝒁 ≥𝑬 𝑿 −𝑬 𝒀 ≥ 𝟏 𝟒 𝒏 𝟏 𝒌 +𝟏 (当𝒏充分大)

18 随机图的单调性 耦合(coupling)：欲比较两个不关联的变量，通过某种 方式强制让它们关联 设 𝒙 𝒖𝒗 均匀分布在[0,1]之间
定理 如果𝟎≤ 𝒑 𝟏 ≤ 𝒑 𝟐 ≤𝟏，则 𝑷 𝑮 𝒏, 𝒑 𝟏 是连通图 ≤𝑷(𝑮 𝒏, 𝒑 𝟐 是连通图） 耦合(coupling)：欲比较两个不关联的变量，通过某种 方式强制让它们关联 设 𝒙 𝒖𝒗 均匀分布在[0,1]之间 𝒙 𝒖𝒗 ≤ 𝒑 𝟏 ⇔𝒖𝒗∈𝑮 𝒏, 𝒑 𝟏 𝒙 𝒖𝒗 ≤ 𝒑 𝟐 ⇔𝒖𝒗∈𝑮 𝒏, 𝒑 𝟐 𝑮 𝒏, 𝒑 𝟏 ⊆𝑮 𝒏, 𝒑 𝟐 ⇒𝑷 𝑮 𝒏, 𝒑 𝟏 是连通图 ≤𝑷(𝑮 𝒏, 𝒑 𝟐 是连通图）

19 随机图的单调性 对图 𝑮 𝟏 𝑽, 𝑬 𝟏 和 𝑮 𝟐 𝑽, 𝑬 𝟐 ，若性质𝓟: 𝓖 𝒏 → {𝟎,𝟏}满足
对图 𝑮 𝟏 𝑽, 𝑬 𝟏 和 𝑮 𝟐 𝑽, 𝑬 𝟐 ，若性质𝓟: 𝓖 𝒏 → {𝟎,𝟏}满足 𝑮 𝟏 ⊆ 𝑮 𝟐 ⟹𝓟 𝑮 𝟏 ≤𝓟 𝑮 𝟐 则称𝓟为单调图性质。 定理 设𝓟为单调图性质， 𝑮 𝟏 ∼𝑮 𝒏, 𝒑 𝟏 , 𝑮 𝟐 ∼𝑮 𝒏, 𝒑 𝟐 且𝟎≤ 𝒑 𝟏 ≤ 𝒑 𝟐 ≤𝟏，则 𝑷 𝓟 𝑮 𝟏 =𝟏 ≤𝑷 𝓟 𝑮 𝟐 =𝟏

20 阈值(Threshold)

21 阈值(Threshold) 给定单调图性质𝓟和𝒑(𝒏)， 𝒑=𝒐 𝒑 𝒏 ⇒𝑷 𝑮 𝒏,𝒑 具有性质𝓟 ＝𝒐(𝟏)
𝒑=𝒐 𝒑 𝒏 ⇒𝑷 𝑮 𝒏,𝒑 具有性质𝓟 ＝𝒐(𝟏) 𝒑=𝝎 𝒑 𝒏 ⇒𝑷 𝑮 𝒏,𝒑 具有性质𝓟 ＝𝟏−𝒐(𝟏) 则称𝒑(𝒏)是性质𝓟的阈值。

22 𝑲 𝟒 的阈值 性质 𝑲 𝟒 ：含有 𝑲 𝟒 子图 𝒑=𝒐 𝒏 − 𝟐 𝟑 ⇒𝑷 𝑮 𝒏,𝑷 含有 𝑲 𝟒 子图 →𝟎，𝒏→∞
定理 𝑲 𝟒 的阈值为𝑝 𝑛 = 𝑛 − 𝒑=𝒐 𝒏 − 𝟐 𝟑 ⇒𝑷 𝑮 𝒏,𝑷 含有 𝑲 𝟒 子图 →𝟎，𝒏→∞ 𝒑=𝝎 𝒏 − 𝟐 𝟑 ⇒𝑷 𝑮 𝒏,𝑷 含有 𝑲 𝟒 子图 →𝟏，𝒏→∞

23 𝑲 𝟒 的阈值： 𝒑=𝒐( 𝒏 − 𝟐 𝟑 ) ∀𝑺∈ [𝒏] 𝟒 , 𝑿 𝑺 = 𝟏 𝑺是团 𝟎 𝑺不是团
𝑲 𝟒 的阈值： 𝒑=𝒐( 𝒏 − 𝟐 𝟑 ) ∀𝑺∈ [𝒏] 𝟒 , 𝑿 𝑺 = 𝟏 𝑺是团 𝟎 𝑺不是团 𝑲 𝟒 子图的个数：𝑿= 𝑺 𝑿 𝑺 𝑬 𝑿 𝑺 =𝑷 𝑺是团 = 𝒑 𝟔 𝑬 𝑿 = 𝑺 𝑬 𝑿 𝑺 = 𝒏 𝟒 𝒑 𝟔 =𝐨(𝟏) 根据马尔可夫不等式， 𝑷 𝑿≥𝟏 ≤𝑬 𝑿 =𝒐 𝟏

24 方差论证 设𝑿是非负整数型随机变量，则 𝑷 𝑿=𝟎 ≤ 𝑫 𝑿 𝑬 𝑿 𝟐 证明：根据切比雪夫不等式，
𝑷 𝑿=𝟎 ≤ 𝑫 𝑿 𝑬 𝑿 𝟐 证明：根据切比雪夫不等式， 𝑷 𝑿=𝟎 ≤𝑷 𝑿−𝑬 𝑿 ≥𝑬 𝑿 ≤ 𝑫 𝑿 𝑬 𝑿 𝟐

25 𝑲 𝟒 的阈值： 𝒑=𝝎( 𝒏 − 𝟐 𝟑 ) 𝑫 𝑿 = 𝑺 𝑫 𝑿 𝑺 + 𝑺≠𝑻 𝒄𝒐𝒗( 𝑿 𝑺 , 𝑿 𝑻 )
𝑲 𝟒 的阈值： 𝒑=𝝎( 𝒏 − 𝟐 𝟑 ) 只需证明𝑷 𝑿=𝟎 ≤ 𝑫 𝑿 𝑬 𝑿 𝟐 =𝒐(𝟏) 𝑫 𝑿 = 𝑺 𝑫 𝑿 𝑺 + 𝑺≠𝑻 𝒄𝒐𝒗( 𝑿 𝑺 , 𝑿 𝑻 ) 𝑫 𝑿 𝑺 =𝑬 𝑿 𝑺 𝟐 − 𝑬 𝑿 𝑺 𝟐 ≤𝑬 𝑿 𝑺 𝟐 =𝑬 𝑿 𝑺 = 𝒑 𝟔 ⇒ 𝑺 𝑫 𝑿 𝑺 =𝑶 𝒏 𝟒 𝒑 𝟔

26 𝒄𝒐𝒗 𝑿 𝑺 , 𝑿 𝑻 , 𝑺≠𝑻 𝑺∩𝑻 ≤𝟏，则 𝑿 𝑺 , 𝑿 𝑻 独立 𝒄𝒐𝒗 𝑿 𝑺 , 𝑿 𝑻 =𝟎 𝑺∩𝑻 =𝟐
𝒄𝒐𝒗 𝑿 𝑺 , 𝑿 𝑻 , 𝑺≠𝑻 𝒄𝒐𝒗 𝑿 𝑺 , 𝑿 𝑻 =𝑬 𝑿 𝑺 𝑿 𝑻 −𝑬 𝑿 𝑺 𝑬 𝑿 𝑻 ≤ 𝑬 𝑿 𝑺 𝑿 𝑻 𝑺∩𝑻 ≤𝟏，则 𝑿 𝑺 , 𝑿 𝑻 独立 𝒄𝒐𝒗 𝑿 𝑺 , 𝑿 𝑻 =𝟎 𝑺∩𝑻 =𝟐 𝑬 𝑿 𝑺 𝑿 𝑻 ≤ 𝒑 𝟏𝟏 𝑺∩𝑻 =𝟑 𝑬 𝑿 𝑺 𝑿 𝑻 ≤ 𝒑 𝟗

27 𝑲 𝟒 的阈值：𝒑=𝝎( 𝒏 − 𝟐 𝟑 ) 只需证明𝑷 𝑿=𝟎 ≤ 𝑫 𝑿 𝑬 𝑿 𝟐 =𝒐(𝟏) 𝑫 𝑿 = 𝑺 𝑫 𝑿 𝑺 + 𝑺≠𝑻 𝒄𝒐𝒗( 𝑿 𝑺 , 𝑿 𝑻 ) 𝑺 𝑫 𝑿 𝑺 =𝑶 𝒏 𝟒 𝒑 𝟔 𝑺≠𝑻 𝒄𝒐𝒗( 𝑿 𝑺 , 𝑿 𝑻 ) =𝑶 𝒏 𝟔 𝒑 𝟏𝟏 + 𝒏 𝟓 𝒑 𝟗 𝑷 𝑿=𝟎 ≤ 𝑫 𝑿 𝑬 𝑿 𝟐 =𝑶 𝒏 −𝟒 𝒑 −𝟔 + 𝒏 −𝟐 𝒑 −𝟏 + 𝒏 −𝟑 𝒑 −𝟑 =𝒐(𝟏)

28 条件期望不等式 对于0-1分布随机变量的和，可以选择使用如下 方法来替代方差论证。 定理
令𝑿= 𝒊=𝟏 𝒏 𝑿 𝒊 ，其中 𝑿 𝒊 为0-1分布随机变量。则 𝑷 𝑿>𝟎 ≥ 𝒊=𝟏 𝒏 𝑷( 𝑿 𝒊 =𝟏) 𝑬[𝑿| 𝑿 𝒊 =𝟏] 注意：该公式无须假设 𝑿 𝒊 间的独立性。

29 条件期望不等式 令𝑿= 𝒊=𝟏 𝒏 𝑿 𝒊 ，其中 𝑿 𝒊 为0-1分布随机变量。则
令𝑿= 𝒊=𝟏 𝒏 𝑿 𝒊 ，其中 𝑿 𝒊 为0-1分布随机变量。则 𝑷 𝑿>𝟎 ≥ 𝒊=𝟏 𝒏 𝑷( 𝑿 𝒊 =𝟏) 𝑬[𝑿| 𝑿 𝒊 =𝟏] 证：令𝒀= 𝟏 𝑿 , 𝑿>𝟎 &𝟎, 𝑿=𝟎 ,则𝑷 𝑿>𝟎 =𝑬[𝑿𝒀]. 𝑬 𝑿𝒀 = 𝒊=𝟏 𝒏 𝑬 𝑿 𝒊 𝒀 = 𝒊=𝟏 𝒏 (𝑬 𝑿 𝒊 𝒀| 𝑿 𝒊 =𝟏 𝑷 𝑿 𝒊 =𝟏 +𝑬 𝑿 𝒊 𝒀 𝑿 𝒊 =𝟎 𝑷 𝑿 𝒊 =𝟎 ) = 𝒊=𝟏 𝒏 𝑬 𝟏 𝑿 𝑿 𝒊 =𝟏 𝑷 𝑿 𝒊 =𝟏 ≥ 𝒊=𝟏 𝒏 𝑷( 𝑿 𝒊 =𝟏) 𝑬[𝑿| 𝑿 𝒊 =𝟏] 其中最后一步利用了Jensen不等式.

30 2nd方法： 𝑲 𝟒 的阈值—𝒑=𝝎( 𝒏 − 𝟐 𝟑 ) ∀𝑺∈ [𝒏] 𝟒 , 𝑿 𝑺 = 𝟏 𝑺是团 𝟎 𝑺不是团
∀𝑺∈ [𝒏] 𝟒 , 𝑿 𝑺 = 𝟏 𝑺是团 𝟎 𝑺不是团 𝑬 𝑿 𝑺 =𝑷 𝑿 𝑺 =𝟏 = 𝒑 𝟔 𝑲 𝟒 子图的个数：𝑿= 𝑺 𝑿 𝑺 𝑬 𝑿 𝑿 𝑺 =𝟏 = 𝑺 ′ 𝑬 𝑿 𝑺 ′ 𝑿 𝑺 =𝟏 =𝟏+ 𝒏−𝟒 𝟒 𝒑 𝟔 + 𝟒 𝒏−𝟒 𝟑 𝒑 𝟔 +𝟔 𝒏−𝟒 𝟐 𝒑 𝟓 +𝟒 𝒏−𝟒 𝟏 𝒑 𝟑 利用条件期望不等式可知 𝑷 𝑿>𝟎 ≥ 𝒏 𝟒 𝒑 𝟔 𝟏+ 𝒏−𝟒 𝟒 𝒑 𝟔 +𝟒 𝒏−𝟒 𝟑 𝒑 𝟔 +𝟔 𝒏−𝟒 𝟐 𝒑 𝟓 +𝟒 𝒏−𝟒 𝟏 𝒑 𝟑 →𝟏