高维概率 High-Dimensional Probability

High-Dimensional Probability

高维概率

https://www.math.uci.edu/~rvershyn/papers/HDP-book/HDP-2.pdf

注记

本节我们举例说明概率方法，即利用随机性构造有用对象。书籍 [17] 主要从组合数学角度提供了该方法的诸多示例。

B. Maurey 在本节介绍的经验方法最初发表于 [271]，此后已发现许多应用。B. Carl 曾用它推导覆盖数的界 [76]，正如我们在推论 0.0.3 中所做的那样。

近似 Caratheodory 定理（定理 0.0.2）的一个较弱版本——不要求凸组合的所有权重相等——仍非平凡。它可不借助概率证明，而改用 Frank-Wolfe 算法的一种版本——一种确定性的、迭代的贪心算法，参见 [43, 引理 2.6]。

与 Caratheodory 定理类似，组合几何中若干其他结果可通过允许其为近似而非精确的形式，实现维度无关化 [10]。

定理 0.0.4 及其在习题 0.9 中的加强版最初由 B. Carl 和 A. Pajor [77] 证明。N. Dafnis、A. Giannopoulos 和 A. Tsolomitis [90] 通过考虑随机多面体，表明习题 0.9 中的界在整个有趣范围 n≤N≤en 内是最优的。

注记

本节我们举例说明概率方法，即利用随机性构造有用对象。书籍 [17] 主要从组合数学角度提供了该方法的诸多示例。

B. Maurey 在本节介绍的经验方法最初发表于 [271]，此后已发现许多应用。B. Carl 曾用它推导覆盖数的界 [76]，正如我们在推论 0.0.3 中所做的那样。

近似 Caratheodory 定理（定理 0.0.2）的一个较弱版本——不要求凸组合的所有权重相等——仍非平凡。它可不借助概率证明，而改用 Frank-Wolfe 算法的一种版本——一种确定性的、迭代的贪心算法，参见 [43, 引理 2.6]。

与 Caratheodory 定理类似，组合几何中若干其他结果可通过允许其为近似而非精确的形式，实现维度无关化 [10]。

定理 0.0.4 及其在习题 0.9 中的加强版最初由 B. Carl 和 A. Pajor [77] 证明。N. Dafnis、A. Giannopoulos 和 A. Tsolomitis [90] 通过考虑随机多面体，表明习题 0.9 中的界在整个有趣范围 n≤N≤en 内是最优的。

原文链接：https://www.math.uci.edu/~rvershyn/papers/HDP-book/HDP-2.pdf