Reviews and Examples

不熟悉的知识点的罗列

1: Union Bound. 2: 容斥. 3: Jenson 不等式. 若 是凸的, 则 .

Proof. 是凸的则 , 在 处展开 : 于是 4: 随机变量 的 阶矩为 .

5: Markov 不等式和 Chebyshev 不等式.

矩母函数

随机变量 的矩母函数定义为 .

定理 1 在期望和微分可交换的条件下, . 其中 表示 阶导数.

Proof.

定理 2 对于随机变量 , 若存在 使 对所有 都成立, 则 具有相同的分布.

Proof.

定理 3 若随机变量 互相独立, 则 .

Proof.

特征函数

设 是实随机变量, 定义复随机变量 , 且 , 且 是关于分布函数 的 Fourier-Stieltjes 变换. 定义 为随机变量 的特征函数, 当 是离散型随机变量时,

特征函数的性质

下面仅涉及到随机变量 , 因此略去下标 .

1. .

2. .

3. 设随机变量 , 则 .

4. 在 上一致连续, 即对任意 , 存在 , 使得 , 对 一致地有 .

5. 是非负定的, 即对任意 , 任意 , 任意 , 有

6. (Bochner-Khintchine Theorem) 函数 是特征函数的充要条件是 是一致连续的且非负定的且 .

7. 设 的 阶矩存在, 则 .

8. (反演公式) 对 的任意连续点 , 有 若不是连续点, 则将左端改为 .

   反演公式说明了特征函数和分布函数是一一对应的.

9. (唯一性定理) 分布函数 恒等的充要条件是它们的特征函数 和 恒等.

例题

1: (判断 是否成立) 给定 , 随机变量 , 证明 时 .

Proof.

2: (Randomized Min-Cut) 给定连通的 , 选择 并收缩 , 保证收缩后两个点之间可以存在重边而不存在自环, 直到只剩下两个点, 输出这两个顶点之间的边的集合 . 证明 . 于是运行 次算法无法得到 min-cut (算法输出错误) 的概率的上界为 .

Proof. 设某个 min-cut 为 . 算法每次将两个点变成一个点, 迭代 次后结束, 则为使算法输出 min-cut, 需要保证这 次迭代收缩的边都不在 中. 设 表示第 次迭代收缩的边不在 中, 表示前 次迭代收缩的边都不在 中, 则计算 即可. 注意到以下事实:

• 有 个顶点且 min-cut 大小为 的图, 每个顶点的度数至少为 .

  反证法: 假设存在一个顶点度数为 , 那么该图的 min-cut 大小就为 了.

• 有 个顶点的 -正则图的边数为 .

  考虑握手定理, , 结论立即成立.

• 综上, 有 个顶点且 min-cut 大小为 的图, 边数至少为 .

于是 . 第 次收缩时顶点数为 , 则 , 则 这就是要证的. 运行 次后, 错误的概率 , 用到了不等式 .

3: (赠券收集问题, coupon's collector problem) 有 种不同的赠券, 某商品中会有一种赠券, 且该赠券的选取是独立同分布地在 种赠券中均匀选取的. 至少需要买多少商品, 才可以集齐所有赠券?

4: (快排的期望运行时间)

习题