概率化方法
概率化方法(Probabilistic Method) 一种用概率证明存在性的方法。 先驱者:Paul Erdős
概率化方法(Probabilistic Method) 从盒子中随机选一个球 𝑷 该球是蓝色的 >𝟎 ⇒盒中有蓝球 概率化方法: 定义一样本空间𝛀及性质𝓟:𝛀→{𝟎,𝟏}: 𝑷 𝓟=𝟏 >𝟎⇒∃𝒙∈𝛀.𝓟(𝒙)=𝟏
Ramsey数 Ramsey定理: 图论语言:对 𝑲 𝟔 2-边着色, 则存在同色的 𝑲 𝟑 任意6个人中,必有3个人互相认识或互不认识。 图论语言:对 𝑲 𝟔 2-边着色, 则存在同色的 𝑲 𝟑 Ramsey数𝑹(𝒌,𝒌):最小 的𝒏,使得对 𝑲 𝒏 的任意2- 边着色中,均存在同色的 𝑲 𝒌
𝑹(𝒌,𝒌)的一个下界 证:对每一条边𝒆∈ 𝑲 𝒏 独立随机着色,即以1/2的概率 着红色,1/2的概率着蓝色。 定理(Erdős 1947) 如果 𝒏 𝒌 𝟐 𝟏− 𝒌 𝟐 <𝟏,则存在对 𝑲 𝒏 的某种2-边着色,其不含同色的 𝑲 𝒌 子图。 证:对每一条边𝒆∈ 𝑲 𝒏 独立随机着色,即以1/2的概率 着红色,1/2的概率着蓝色。 给定一 𝑲 𝒌 子图, 𝑷 该 𝑲 𝒌 同色 = 𝟐 𝟏− 𝒌 𝟐 ⟹𝑷 存在同色 𝑲 𝒌 子图 ≤ 𝒏 𝒌 𝟐 𝟏− 𝒌 𝟐 <𝟏 (Union bound) ⟹𝑷 不存在同色 𝑲 𝒌 子图 >𝟎, ⟹从而存在对 𝑲 𝒏 的某种2-边着色,其不含同色的 𝑲 𝒌 子图 推论:对所有𝒌≥𝟑,𝑹 𝒌,𝒌 >⌊ 𝟐 𝒌/𝟐 ⌋
竞赛图 有向图𝑻 𝑽,𝑬 𝒌矛盾: 问题:对于每一个有穷的𝒌,是否 总存在一个𝒌矛盾的竞赛图? 𝒏个玩家,每一对玩家有一场比赛 𝒖指向𝒗当且仅当𝒖打败𝒗 𝒌矛盾: 对于任意𝒌子集𝑺⊂𝑽,存在一个不属 于𝑺的玩家打败了所有𝑺中的玩家 问题:对于每一个有穷的𝒌,是否 总存在一个𝒌矛盾的竞赛图?
𝒌矛盾的竞赛图的存在性 问:对任意有穷的𝒌,是否总存在一个𝒌矛盾的竞赛图? 证:随机取一个包含𝒏个节点的竞赛图𝑻 𝑽,𝑬 定理(Erdős 1947) 若 𝒏 𝒌 𝟏− 𝟐 −𝒌 𝒏−𝒌 <𝟏,则存在𝒏个节点的𝒌矛盾的竞赛图. 证:随机取一个包含𝒏个节点的竞赛图𝑻 𝑽,𝑬 对𝒌子集𝑺,令 𝑨 𝑺 :不存在𝑽\𝐒中玩家打败了𝑺的所有玩家 𝑷 𝑨 𝑺 = 𝟏− 𝟐 −𝒌 𝒏−𝒌 ⟹𝑷 𝑺 𝑨 𝑺 ≤ 𝑺 𝑷 𝑨 𝑺 = 𝒏 𝒌 𝟏− 𝟐 −𝒌 𝒏−𝒌 <𝟏 ⟹𝑷 𝑺 𝑨 𝒔 >𝟎 即存在一个𝒌矛盾的竞赛图.
期望论证 若班级学生的平均身高为𝒍,则存在一个同学其 身高≥𝒍 (≤𝒍). 对随机变量𝑿,设𝑬 𝑿 =𝝁 𝑷 𝑿≥𝝁 >𝟎 𝑷 𝑿≤𝝁 >𝟎
竞赛图中的哈密尔顿路径 哈密尔顿路径: 哈密尔顿路径的数目能达到多少? 恰好访问每一个节点一次的路径 定理(Szele 1943) 存在包含至少𝒏! 𝟐 − 𝒏−𝟏 条哈密尔顿路径的𝒏个玩家的竞赛图。
竞赛图中的哈密尔顿路径 随机选取定义在𝒏个玩家上的竞赛图𝑻 [𝒏],𝑬 令𝑿表示𝑻中包含的哈密尔顿路径数目 定理(Szele 1943) 存在包含至少𝒏! 𝟐 − 𝒏−𝟏 条哈密尔顿路径的𝒏个玩家的竞赛图。 随机选取定义在𝒏个玩家上的竞赛图𝑻 [𝒏],𝑬 令𝑿表示𝑻中包含的哈密尔顿路径数目 考虑[𝒏]的置换𝝅,定义 𝑿 𝝅 = 𝟏 𝝅是哈密尔顿路径 𝟎 𝝅不是哈密尔顿路径 𝑬 𝑿 𝝅 =𝑷 𝑿 𝝅 =𝟏 = 𝟐 − 𝒏−𝟏 𝑬 𝑿 = 𝝅 𝑬 𝑿 𝝅 =𝒏! 𝟐 − 𝒏−𝟏
独立集 给定图𝑮(𝑽,𝑬),对于𝑺⊆𝑽, 若𝑺中节点互不相连,则称𝑺 为独立集(independent set) 定理 设𝑮节点数为𝒏,边数为𝒎,则𝑮有至少包含 𝒏 𝟐 𝟒𝒎 个节点的独立集。 随机选取一些节点? 若节点数多,则很有可能不是独立集
采样+修改 采样:以概率𝒑独立选取每个节点,构成𝑺 修改:∀𝒖𝒗∈𝑬,若𝒖,𝒗∈𝑺则从𝑺中删除𝒖或者 𝒗中的一个,得到 𝑺 ∗ 定理 设𝑮节点数为𝒏,边数为𝒎,则𝑮有至少包含 𝒏 𝟐 𝟒𝒎 个节点的独立集。 采样:以概率𝒑独立选取每个节点,构成𝑺 修改:∀𝒖𝒗∈𝑬,若𝒖,𝒗∈𝑺则从𝑺中删除𝒖或者 𝒗中的一个,得到 𝑺 ∗ 𝑺 ∗ 为独立集
采样+修改 采样:以概率𝒑独立选取每个节点,构成𝑺 修改:∀𝒖𝒗∈𝑬,若𝒖,𝒗∈𝑺则从𝑺中删除𝒖或者 𝒗中的一个,得到 𝑺 ∗ 𝑺 ∗ 为独立集 𝑬 |𝑺| =𝒏𝒑 令𝒀表示𝑺中节点间边的数目,𝑬 𝒀 =𝒎 𝒑 𝟐 |𝑺 ∗ |≥ 𝑺 −𝒀⇒𝑬 𝑺 ∗ ≥𝒏𝒑−𝒎 𝒑 𝟐 = 𝒏 𝟐 𝟒𝒎 其中取𝒑= 𝒏 𝟐𝒎
腰长较大的图 腰长(girth):图中最小圈的长度 事实上,存在密集的图腰长相对较大。 直觉上,密集的图腰长较小。 定理 对于任意整数𝒌≥𝟑,存在一个具有𝒏个节点的图,其拥有至少 𝟏 𝟒 𝒏 𝟏+ 𝟏 𝒌 条边,且腰长至少为𝒌。
随机图(Random Graphs) 记为𝑮 𝒏,𝒑 𝑽 =𝒏 ∀𝒖,𝒗∈𝑽, 𝑷 𝒖,𝒗 ∈𝑬 =𝒑 且独立
腰长较大的图 采样:任选一随机图𝑮∼𝑮(𝒏,𝒑),其中𝒑= 𝒏 𝟏 𝒌 −𝟏 修改: 对𝑮中每一个长度小于𝒌的圈,删除其中 一条边(破圈) 定理 对于任意整数𝒌≥𝟑,存在一个具有𝒏个节点的图,其拥有至少 𝟏 𝟒 𝒏 𝟏+ 𝟏 𝒌 条边,且腰长至少为𝒌。 采样:任选一随机图𝑮∼𝑮(𝒏,𝒑),其中𝒑= 𝒏 𝟏 𝒌 −𝟏 修改: 对𝑮中每一个长度小于𝒌的圈,删除其中 一条边(破圈)
腰长较大的图 采样:任选一随机图𝑮∼𝑮(𝒏,𝒑),其中𝒑= 𝒏 𝟏 𝒌 −𝟏 采样:任选一随机图𝑮∼𝑮(𝒏,𝒑),其中𝒑= 𝒏 𝟏 𝒌 −𝟏 修改: 对𝑮中每一个长度小于𝒌的圈,删除其中 一条边(破圈),得到图 𝑮 ∗ ,其腰长至少为𝒌 分析 𝑮 ∗ 的边数𝒁: 𝑿: 𝑮中的边数,𝑬 𝑿 = 𝒏 𝟐 𝒑 𝒀:𝑮中长度小于𝒌的圈数,𝑬 𝒀 = 𝒊=𝟑 𝒌−𝟏 𝒏 𝒊 𝒊−𝟏 ! 𝟐 𝒑 𝒊 𝒁≥𝑿−𝒀 ⇒𝑬 𝒁 ≥𝑬 𝑿 −𝑬 𝒀 ≥ 𝟏 𝟒 𝒏 𝟏 𝒌 +𝟏 (当𝒏充分大)
随机图的单调性 耦合(coupling):欲比较两个不关联的变量,通过某种 方式强制让它们关联 设 𝒙 𝒖𝒗 均匀分布在[0,1]之间 定理 如果𝟎≤ 𝒑 𝟏 ≤ 𝒑 𝟐 ≤𝟏,则 𝑷 𝑮 𝒏, 𝒑 𝟏 是连通图 ≤𝑷(𝑮 𝒏, 𝒑 𝟐 是连通图) 耦合(coupling):欲比较两个不关联的变量,通过某种 方式强制让它们关联 设 𝒙 𝒖𝒗 均匀分布在[0,1]之间 𝒙 𝒖𝒗 ≤ 𝒑 𝟏 ⇔𝒖𝒗∈𝑮 𝒏, 𝒑 𝟏 𝒙 𝒖𝒗 ≤ 𝒑 𝟐 ⇔𝒖𝒗∈𝑮 𝒏, 𝒑 𝟐 𝑮 𝒏, 𝒑 𝟏 ⊆𝑮 𝒏, 𝒑 𝟐 ⇒𝑷 𝑮 𝒏, 𝒑 𝟏 是连通图 ≤𝑷(𝑮 𝒏, 𝒑 𝟐 是连通图)
随机图的单调性 对图 𝑮 𝟏 𝑽, 𝑬 𝟏 和 𝑮 𝟐 𝑽, 𝑬 𝟐 ,若性质𝓟: 𝓖 𝒏 → {𝟎,𝟏}满足 对图 𝑮 𝟏 𝑽, 𝑬 𝟏 和 𝑮 𝟐 𝑽, 𝑬 𝟐 ,若性质𝓟: 𝓖 𝒏 → {𝟎,𝟏}满足 𝑮 𝟏 ⊆ 𝑮 𝟐 ⟹𝓟 𝑮 𝟏 ≤𝓟 𝑮 𝟐 则称𝓟为单调图性质。 定理 设𝓟为单调图性质, 𝑮 𝟏 ∼𝑮 𝒏, 𝒑 𝟏 , 𝑮 𝟐 ∼𝑮 𝒏, 𝒑 𝟐 且𝟎≤ 𝒑 𝟏 ≤ 𝒑 𝟐 ≤𝟏,则 𝑷 𝓟 𝑮 𝟏 =𝟏 ≤𝑷 𝓟 𝑮 𝟐 =𝟏
阈值(Threshold)
阈值(Threshold) 给定单调图性质𝓟和𝒑(𝒏), 𝒑=𝒐 𝒑 𝒏 ⇒𝑷 𝑮 𝒏,𝒑 具有性质𝓟 =𝒐(𝟏) 𝒑=𝒐 𝒑 𝒏 ⇒𝑷 𝑮 𝒏,𝒑 具有性质𝓟 =𝒐(𝟏) 𝒑=𝝎 𝒑 𝒏 ⇒𝑷 𝑮 𝒏,𝒑 具有性质𝓟 =𝟏−𝒐(𝟏) 则称𝒑(𝒏)是性质𝓟的阈值。
𝑲 𝟒 的阈值 性质 𝑲 𝟒 :含有 𝑲 𝟒 子图 𝒑=𝒐 𝒏 − 𝟐 𝟑 ⇒𝑷 𝑮 𝒏,𝑷 含有 𝑲 𝟒 子图 →𝟎,𝒏→∞ 定理 𝑲 𝟒 的阈值为𝑝 𝑛 = 𝑛 − 2 3 . 𝒑=𝒐 𝒏 − 𝟐 𝟑 ⇒𝑷 𝑮 𝒏,𝑷 含有 𝑲 𝟒 子图 →𝟎,𝒏→∞ 𝒑=𝝎 𝒏 − 𝟐 𝟑 ⇒𝑷 𝑮 𝒏,𝑷 含有 𝑲 𝟒 子图 →𝟏,𝒏→∞
𝑲 𝟒 的阈值: 𝒑=𝒐( 𝒏 − 𝟐 𝟑 ) ∀𝑺∈ [𝒏] 𝟒 , 𝑿 𝑺 = 𝟏 𝑺是团 𝟎 𝑺不是团 𝑲 𝟒 的阈值: 𝒑=𝒐( 𝒏 − 𝟐 𝟑 ) ∀𝑺∈ [𝒏] 𝟒 , 𝑿 𝑺 = 𝟏 𝑺是团 𝟎 𝑺不是团 𝑲 𝟒 子图的个数:𝑿= 𝑺 𝑿 𝑺 𝑬 𝑿 𝑺 =𝑷 𝑺是团 = 𝒑 𝟔 𝑬 𝑿 = 𝑺 𝑬 𝑿 𝑺 = 𝒏 𝟒 𝒑 𝟔 =𝐨(𝟏) 根据马尔可夫不等式, 𝑷 𝑿≥𝟏 ≤𝑬 𝑿 =𝒐 𝟏
方差论证 设𝑿是非负整数型随机变量,则 𝑷 𝑿=𝟎 ≤ 𝑫 𝑿 𝑬 𝑿 𝟐 证明:根据切比雪夫不等式, 𝑷 𝑿=𝟎 ≤ 𝑫 𝑿 𝑬 𝑿 𝟐 证明:根据切比雪夫不等式, 𝑷 𝑿=𝟎 ≤𝑷 𝑿−𝑬 𝑿 ≥𝑬 𝑿 ≤ 𝑫 𝑿 𝑬 𝑿 𝟐
𝑲 𝟒 的阈值: 𝒑=𝝎( 𝒏 − 𝟐 𝟑 ) 𝑫 𝑿 = 𝑺 𝑫 𝑿 𝑺 + 𝑺≠𝑻 𝒄𝒐𝒗( 𝑿 𝑺 , 𝑿 𝑻 ) 𝑲 𝟒 的阈值: 𝒑=𝝎( 𝒏 − 𝟐 𝟑 ) 只需证明𝑷 𝑿=𝟎 ≤ 𝑫 𝑿 𝑬 𝑿 𝟐 =𝒐(𝟏) 𝑫 𝑿 = 𝑺 𝑫 𝑿 𝑺 + 𝑺≠𝑻 𝒄𝒐𝒗( 𝑿 𝑺 , 𝑿 𝑻 ) 𝑫 𝑿 𝑺 =𝑬 𝑿 𝑺 𝟐 − 𝑬 𝑿 𝑺 𝟐 ≤𝑬 𝑿 𝑺 𝟐 =𝑬 𝑿 𝑺 = 𝒑 𝟔 ⇒ 𝑺 𝑫 𝑿 𝑺 =𝑶 𝒏 𝟒 𝒑 𝟔
𝒄𝒐𝒗 𝑿 𝑺 , 𝑿 𝑻 , 𝑺≠𝑻 𝑺∩𝑻 ≤𝟏,则 𝑿 𝑺 , 𝑿 𝑻 独立 𝒄𝒐𝒗 𝑿 𝑺 , 𝑿 𝑻 =𝟎 𝑺∩𝑻 =𝟐 𝒄𝒐𝒗 𝑿 𝑺 , 𝑿 𝑻 , 𝑺≠𝑻 𝒄𝒐𝒗 𝑿 𝑺 , 𝑿 𝑻 =𝑬 𝑿 𝑺 𝑿 𝑻 −𝑬 𝑿 𝑺 𝑬 𝑿 𝑻 ≤ 𝑬 𝑿 𝑺 𝑿 𝑻 𝑺∩𝑻 ≤𝟏,则 𝑿 𝑺 , 𝑿 𝑻 独立 𝒄𝒐𝒗 𝑿 𝑺 , 𝑿 𝑻 =𝟎 𝑺∩𝑻 =𝟐 𝑬 𝑿 𝑺 𝑿 𝑻 ≤ 𝒑 𝟏𝟏 𝑺∩𝑻 =𝟑 𝑬 𝑿 𝑺 𝑿 𝑻 ≤ 𝒑 𝟗
𝑲 𝟒 的阈值:𝒑=𝝎( 𝒏 − 𝟐 𝟑 ) 只需证明𝑷 𝑿=𝟎 ≤ 𝑫 𝑿 𝑬 𝑿 𝟐 =𝒐(𝟏) 𝑫 𝑿 = 𝑺 𝑫 𝑿 𝑺 + 𝑺≠𝑻 𝒄𝒐𝒗( 𝑿 𝑺 , 𝑿 𝑻 ) 𝑺 𝑫 𝑿 𝑺 =𝑶 𝒏 𝟒 𝒑 𝟔 𝑺≠𝑻 𝒄𝒐𝒗( 𝑿 𝑺 , 𝑿 𝑻 ) =𝑶 𝒏 𝟔 𝒑 𝟏𝟏 + 𝒏 𝟓 𝒑 𝟗 𝑷 𝑿=𝟎 ≤ 𝑫 𝑿 𝑬 𝑿 𝟐 =𝑶 𝒏 −𝟒 𝒑 −𝟔 + 𝒏 −𝟐 𝒑 −𝟏 + 𝒏 −𝟑 𝒑 −𝟑 =𝒐(𝟏)
条件期望不等式 对于0-1分布随机变量的和,可以选择使用如下 方法来替代方差论证。 定理 令𝑿= 𝒊=𝟏 𝒏 𝑿 𝒊 ,其中 𝑿 𝒊 为0-1分布随机变量。则 𝑷 𝑿>𝟎 ≥ 𝒊=𝟏 𝒏 𝑷( 𝑿 𝒊 =𝟏) 𝑬[𝑿| 𝑿 𝒊 =𝟏] 注意:该公式无须假设 𝑿 𝒊 间的独立性。
条件期望不等式 令𝑿= 𝒊=𝟏 𝒏 𝑿 𝒊 ,其中 𝑿 𝒊 为0-1分布随机变量。则 令𝑿= 𝒊=𝟏 𝒏 𝑿 𝒊 ,其中 𝑿 𝒊 为0-1分布随机变量。则 𝑷 𝑿>𝟎 ≥ 𝒊=𝟏 𝒏 𝑷( 𝑿 𝒊 =𝟏) 𝑬[𝑿| 𝑿 𝒊 =𝟏] 证:令𝒀= 𝟏 𝑿 , 𝑿>𝟎 &𝟎, 𝑿=𝟎 ,则𝑷 𝑿>𝟎 =𝑬[𝑿𝒀]. 𝑬 𝑿𝒀 = 𝒊=𝟏 𝒏 𝑬 𝑿 𝒊 𝒀 = 𝒊=𝟏 𝒏 (𝑬 𝑿 𝒊 𝒀| 𝑿 𝒊 =𝟏 𝑷 𝑿 𝒊 =𝟏 +𝑬 𝑿 𝒊 𝒀 𝑿 𝒊 =𝟎 𝑷 𝑿 𝒊 =𝟎 ) = 𝒊=𝟏 𝒏 𝑬 𝟏 𝑿 𝑿 𝒊 =𝟏 𝑷 𝑿 𝒊 =𝟏 ≥ 𝒊=𝟏 𝒏 𝑷( 𝑿 𝒊 =𝟏) 𝑬[𝑿| 𝑿 𝒊 =𝟏] 其中最后一步利用了Jensen不等式.
2nd方法: 𝑲 𝟒 的阈值—𝒑=𝝎( 𝒏 − 𝟐 𝟑 ) ∀𝑺∈ [𝒏] 𝟒 , 𝑿 𝑺 = 𝟏 𝑺是团 𝟎 𝑺不是团 ∀𝑺∈ [𝒏] 𝟒 , 𝑿 𝑺 = 𝟏 𝑺是团 𝟎 𝑺不是团 𝑬 𝑿 𝑺 =𝑷 𝑿 𝑺 =𝟏 = 𝒑 𝟔 𝑲 𝟒 子图的个数:𝑿= 𝑺 𝑿 𝑺 𝑬 𝑿 𝑿 𝑺 =𝟏 = 𝑺 ′ 𝑬 𝑿 𝑺 ′ 𝑿 𝑺 =𝟏 =𝟏+ 𝒏−𝟒 𝟒 𝒑 𝟔 + 𝟒 𝒏−𝟒 𝟑 𝒑 𝟔 +𝟔 𝒏−𝟒 𝟐 𝒑 𝟓 +𝟒 𝒏−𝟒 𝟏 𝒑 𝟑 利用条件期望不等式可知 𝑷 𝑿>𝟎 ≥ 𝒏 𝟒 𝒑 𝟔 𝟏+ 𝒏−𝟒 𝟒 𝒑 𝟔 +𝟒 𝒏−𝟒 𝟑 𝒑 𝟔 +𝟔 𝒏−𝟒 𝟐 𝒑 𝟓 +𝟒 𝒏−𝟒 𝟏 𝒑 𝟑 →𝟏