概率化方法.

Slides:



Advertisements
Similar presentations
G-518  来源:环球网 世界上的货币,源远流长,历史悠久,币面图案多采多样,有用真的珍珠镶嵌的,有用真正的猛犸象牙做的,有的还能闻到大海味道的硬币等等,使人目不暇接。在众多的收藏品中,货币是重要的一种,专门收藏和研究货币的大有人在。我们看看世界上最美的25种硬币。
Advertisements

职业教育课程改革创新教材 财经法规与会计职业道德.
會計學 第四版 第十章 投 資 10-1 金融商品概述 10-2 股票投資 10-3 債券投資 10-4 長期股權投資
案例分析 ——中交集团的设立的思考.
第三章 中国监察制度的演进 主讲:杨丛樱.
简明天文学 一、天文学简史 银河系猎户座马头星云.
华东师范大学第二附属中学 作者:高二(7)班 顾韬 景琰杰 指导教师:张成鹏
大学生素质拓展报告 网 络 软 件 §班级:软件05303班 №姓名:姜 玉 梅 仿佛什么都没有留下,一片空白。我想,这一周发生的事情会是我大学生 §班级:软件05303班 №姓名:姜 玉 梅 时光飞逝,又是一周过去了,不过这一周却不像以往那样,逝去无痕,
专题三 放眼世界 展望未来 ——国际战略环境 主讲教师:.
新的事业,心的成长 ——中小学心理健康教育的理论与实践
聖保祿 St. Paul.
第十三章 城市和地区电子政务案例.
一、歐洲概述 範圍 地理區. 一、歐洲概述 範圍 地理區 北極海 烏 拉 山 東半部 西半部 大 西 洋 高加索山 地中海.
信息技术教材分析 南宁市民主路小学 林大华
國小水墨畫教學 分享者 / 謝婉妮.
原作:七度鱼.
楼宇电梯、灯箱媒体推荐 咨询热线:
嘉義縣溪口國民中學 語文領域-國文科 閱讀與寫作 書目導讀 蕭奕鈞老師
常州市“十二五” 规划课题第二批课题 开题报告会.
高關懷冒險王推動報告 萬里國中推動探索教育之規劃 施青珍
第六章 会计报表编制前 的准备工作 期末账项的调整 财产清查 资产期末计价.
African Union 非洲聯盟 隊長: 蘇仕賢 張翔凌 郭峻岳.
世界绝美的 24 种硬币.
D、結構化技術 主要的結構化技術 結構化程式設計 (Structured Programming)
耐震「詳細評估」及「補強設計」勞務採購契約要項
  商学院EMBA联盟 成立大会
服装结构设计.
太平洋經濟合作香港委員會 CEPA與香港在珠三角的新機遇 《會計業》
DV摄像 第一章 摄像机拍摄技巧入门.
职业教育课程改革创新教材 财经法规与会计职业道德.
第三节 带状疱疹 一、概念 带状疱疹(herpes zoster)是由潜伏在体内的水 痘-带状疱疹病毒(VZV)再激活所致,以沿单侧周
2 nd 企業倫理報告 -博達案- 指導老師 : 張民昌 組長: 盧子鈴
控制权市场的建设 和公司治理 张新.
講員:黃榮村先生 時間:十一月三十日,2004年 地點:海洋大學
科技计划体系 与 科技计划管理 浙江省科技厅综合计划处 二OO九年八月
概率论与数理统计 2.1 随机变量与分布函数.
组织 广州医科大学 副研究员 黄丹华 2015年3月 课件网页
影片另附 八月九日生於廣東省潮安縣。 初名福森,字選堂,號固庵。 1917 生平經歷 治學方法 學術研究 重要著作 他人評論.
第十一章 社會安全.
資料庫管理 HOMEWORK #2 ERD練習 楊立偉教授 台灣大學工管系 2013 Fall.
Demographics T IN aiwan Team 1.
非结构化P2P网络.
啟示錄 人 子 七 教 會 寶 座 七 印 七 號 龍 與 獸 七 碗 巴 比 倫 千 禧 年 前 後 新 耶 路 撒 冷 第9章(第5號)
如何進行限制性招標採購案.
Randomized Algorithms
生物顯微影像快速分析-細胞核中異染色質之定量分析
第一章.
势如劈竹 锋不可当 劈锋 Made in Germany.
B 解析 A项“寥”读“liáo”。C项“赁”读“lìn”。D项“骜”读“ào”。.
幸福小組聚會 天國勇士的產生 ─從掃羅到保羅.
智慧財產權與創用CC.
An Introduction to Communication Complexity
講師:郭育倫 第2章 效能分析 講師:郭育倫
列王紀下.
貝氏刷牙法 (Bass Method) 外埔國小.
陳博志
第十六章 有效且公平地课税 最适课税理论(theory of optimal taxation) 最适课税理论的基本含义:
第十四章 有效且公平地课税 最适课税理论(theory of optimal taxation) 最适课税理论的基本含义:
實習一 RC耦合串級放大電路實驗 實習二 直接耦合串級放大電路實驗 實習三 變壓器耦合串級放大電路實驗
犹太 耶稣从那里起身,来到犹太的境界并约但河外。众人又聚集到他那里,他又照常教训他们。(可10:1) 撒玛利亚 耶稣最后半年的服事
塞尚 畫家~塞尚→ 組員;楊子嫻.林雯萱.陳怡臻 指導老師;黃芝莉.
我們又在一起 我們又在一起 來讚美主 我們又在一起 同心合意 美好事必定要成就 美好事已顯明
Probability Statistics p65 ~ 85 & p119~ /6/7
請弟兄姊妹預備心來敬拜.
推動搖籃的手─製作部門 ﹝西子劇坊﹞ 蔡如歆.
等离子体物理介绍.
生化危急結果之報告處理時效改善經驗分享 Experience of quality improvement of critical value response time in the clinical chemistry laboratory 蔡明純, 許烜朝, 蕭玉鑫 彰化基督教醫療財團法人彰化基督教醫院.
第二章 咖啡豆處理方法 咖啡豆處理流程 咖啡豆精製 咖啡豆炒焙.
Presentation transcript:

概率化方法

概率化方法(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方法: 𝑲 𝟒 的阈值—𝒑=𝝎( 𝒏 − 𝟐 𝟑 ) ∀𝑺∈ [𝒏] 𝟒 , 𝑿 𝑺 = 𝟏 𝑺是团 𝟎 𝑺不是团 ∀𝑺∈ [𝒏] 𝟒 , 𝑿 𝑺 = 𝟏 𝑺是团 𝟎 𝑺不是团 𝑬 𝑿 𝑺 =𝑷 𝑿 𝑺 =𝟏 = 𝒑 𝟔 𝑲 𝟒 子图的个数:𝑿= 𝑺 𝑿 𝑺 𝑬 𝑿 𝑿 𝑺 =𝟏 = 𝑺 ′ 𝑬 𝑿 𝑺 ′ 𝑿 𝑺 =𝟏 =𝟏+ 𝒏−𝟒 𝟒 𝒑 𝟔 + 𝟒 𝒏−𝟒 𝟑 𝒑 𝟔 +𝟔 𝒏−𝟒 𝟐 𝒑 𝟓 +𝟒 𝒏−𝟒 𝟏 𝒑 𝟑 利用条件期望不等式可知 𝑷 𝑿>𝟎 ≥ 𝒏 𝟒 𝒑 𝟔 𝟏+ 𝒏−𝟒 𝟒 𝒑 𝟔 +𝟒 𝒏−𝟒 𝟑 𝒑 𝟔 +𝟔 𝒏−𝟒 𝟐 𝒑 𝟓 +𝟒 𝒏−𝟒 𝟏 𝒑 𝟑 →𝟏