当前位置: 首页 > news >正文

Probabilistic method小记

概率方法是通过构造概率空间来证明组合命题的方法。
一个概率方法最简单的例子:
定义Ramsey数:\(R(a,b)\)表示最小的\(n\),使得对于\(n\)个点的图,无论将每条边染成红色还是蓝色,都存在一个大小为\(a\)的全部为红色边的完全图,或者存在一个大小为\(b\)的全部为蓝色边的完全图。\(R(a,b)\)存在且有限
人类目前对于Ramsey数的认识十分有限:\(R(5,5)\)的值还是未知的。
我们可以使用概率方法估计\(R(a,b)\)得下界:考虑随机把所有边染成红色或者蓝色(每条边为红色或者蓝色概率均为\(\frac{1}{2}\)
定义事件\(A_S\)\(S\)内的边同为蓝色(\(|S|=a\)),\(B_S\)\(S\)内的边同为红色(\(|S|=b\))。显然\(P(A_S)=2^{-\binom{a}{2}},P(B_S)=2^{-\binom{b}{2}}\)
假如图的大小为\(n\),如果所有\(A,B\)中至少有一个会发生,那么肯定无论将每条边染成红色还是蓝色,都存在一个大小为\(a\)的全部为红色边的完全图,或者存在一个大小为\(b\)的全部为蓝色边的完全图。
所有\(A,B\)中至少有一个会发生这个事件对应事件所有\(A,B\)的并(设为\(C\))。根据Union bound可得\(\sum_{|S|=a}P(A_S)+\sum_{|S|=b}P(B_S)=\binom{n}{a}2^{-\binom{a}{2}}+\binom{n}{b}2^{-\binom{b}{2}}\)的概率比这些事件的并的发生概率要大。
假如\(\binom{n}{a}2^{-\binom{a}{2}}+\binom{n}{b}2^{-\binom{b}{2}}<1\),那么存在一种染色方案使得\(C\)不会发生,也就是说\(R(a,b)>n\)
当然直接用Union bound进行估计是非常粗糙的,所以这个上界可以优化。

http://www.hskmm.com/?act=detail&tid=24713

相关文章:

  • 数据生成方法初步调研
  • Elastic Stack 9.1.4 发布:重要安全更新与功能优化
  • 2025钛白粉源头厂家最新推荐排行榜:覆盖广东珠三角东莞华南深圳长三角地区的优质供应商解析
  • 完整教程:图论回溯
  • 用 Whisper 打破沉默:AI 语音技术如何重塑无障碍沟通方式? - 指南
  • 做题记录(Oct.)
  • 生成式AI改进极端多标签分类技术
  • 2025.10.5——1绿
  • 【清晰教程】利用Git工具将本地项目push上传至GitHub仓库中 - 指南
  • 题解:2025.10.信友队.智灵班选拔面试题目
  • MX WEEK4
  • 实用指南:蓝桥杯_DS18B20温度传感器---新手入门级别超级详细解析
  • 2025.10.4 刷题
  • TDengine 运维——巡检工具(定期检查) - 指南
  • [ABC398G] Not Only Tree Game
  • 深入解析:Java基础(二):八种基本数据类型详解
  • 物理_备忘
  • 越秀凭一己之力打破了行业天花板 - 智慧园区
  • 在AI技术唾手可得的时代,挖掘JavaScript学习资源的新需求成为关键
  • 洛谷P9676 [ICPC 2022 Jinan R] Skills
  • 读人形机器人31未来30年
  • 【java面试】redis篇 - 指南
  • 洛谷P8421 [THUPC 2022 决赛] rsraogps
  • NLP学习路线图(十四):词袋模型(Bag of Words) - 详解
  • 实用指南:苍茫命令行:linux模拟实现,书写微型bash
  • 2025 年压滤机厂家最新推荐排行榜:隔膜压滤机,污泥压滤机,真空压滤机,板框压滤机,带式压滤机优质企业权威评选及选购指南
  • 2025 年搅拌器厂家最新推荐排行榜:涵盖立式、不锈钢、侧入式等多类型设备,深度解析实力厂商
  • 2025 年最新推荐承烧板厂家排行榜:筛选优质企业,破解采购难题,赋能高温工业生产
  • 一文看懂AI SoC芯片
  • 月球尘埃电解技术实现资源就地利用