随机变量：名字骗人的函数
Random Variable Examples随机变量 R 是定义在样本空间上的全函数——它根本不随机，随机的是输入。"掷三枚硬币的正面数" C：C(HHT)=2；"三币全同"指示变量 M：M(HHT)=0。
指示随机变量（indicator / Bernoulli 变量）把样本空间切成两块：I_E(ω)=1 当 ω∈E。每个事件天然对应一个指示变量，反之亦然（引理 19.2.1：事件独立 ⟺ 指示变量独立）。任何关于随机变量的断言都定义一个事件：[C=2] = {THH,HTH,HHT}，Pr = 3/8；而怪断言"C·M 是奇数"就是 {HHH}。
独立性升级到变量版（19.2）：R、S 独立 ⟺ 所有 [R=x] 与 [S=y] 独立。三硬币里 C 与 M 不独立（C=2 时 M 必为 0），但首掷指示变量 H₁ 与 M 独立。还有一条好用的：独立变量的函数仍独立（引理 19.2.2）。
分布函数：同一件事的两种问法
Distribution FunctionsPDF_R(x) = Pr[R=x]；CDF_R(x) = Pr[R ≤ x]（左侧阶梯累加）。两枚骰子和的 PDF 是 2..12 上的金字塔（7 最可能 6/36），CDF 是爬向 1 的阶梯。PDF/CDF 完全确定"行为"——不同样本空间上的随机变量可以同分布。
CS 三大常用分布：Bernoulli（0/1，f_p(0)=p、f_p(1)=1−p）、Uniform（n 个值各 1/n）、Binomial（下一节）。还有无处不在的 randomized algorithms：Ethernet 的指数退避、quicksort 的随机主元——随机性是性能工具，不是缺陷。
信封猜数：对上赌桌也必胜的策略
The Numbers Game两个信封装两个不同整数——由想赢你的对手挑选，可以完全非随机。你偷看一个，然后指认它是不是较大的数。随机瞎猜 50%；四步法证明如下策略必胜过半：先从半整数 ½, 3/2, 5/2, … 中随机猜一个 x，偷看到 T>x 就说"这是大的"，T<x 就说"这是小的"。猜中 x 落在两数之间时稳赢，猜不中也不亏：
范围 0..100 至少 50.5%；缩到 0..10 直接 55%。理论交给实践：
二项分布：尾巴塌得比想象快
Binomial Distributionsn 枚独立硬币各以概率 p 出正面，正面数 J 的 pdf：f_{n,p}(k) = ( n / k )·pᵏ(1−p)ⁿ⁻ᵏ。公平硬币是 p=1/2 特例。尾部（tails）以指数速度塌缩：100 掷至多 25 正的概率 < 1/3,000,000。
期望：被概率加权的平均
Great ExpectationsEx[R] = Σ_ω R(ω)Pr[ω] = Σ_x x·Pr[R=x]。骰子期望 7/2——"期望值"这个名字有误导性：没人能掷出 3.5。倒数的期望 ≠ 期望的倒数：Ex[1/R] = 49/120 ≠ 1/(7/2)。
条件期望（19.4.4）：Ex[R|A] 按缩小后的空间取平均——"骰子 ≥4"条件下期望恰为 5。全期望定律（定理 19.4.5）：按情况拆分再按概率加权，身高例：0.496×5'11″ + 0.504×5'5″ ≈ 5'8″。
系统每步独立以概率 p 崩溃，首次崩溃期望步数 Ex[C] = 1/p。自指推导：Ex[C] = 1·p + (1+Ex[C])(1−p)。几何分布（定义 19.4.6）。"生到男孩为止"的夫妇平均只要 2 胎——人口性别比不会被这种策略改变。
分池对赌：公平游戏怎么输掉 $500
Expected Returns in Gambling Games三人各押 $2 猜一枚公平硬币的正反，$6 池子由猜中者平分（全错则退池）。四步法算 8 个 outcome：你的期望回报恰好 0——公平。玩了 1000 局却输掉 $500？重新看牌桌：Eric 和 Nick 从来没有猜过一样的——他们串通了。这一个事实改写了 outcome 概率：Ex[payoff] = 0 → −1/2，每局期望亏 5 毛。
线性期望：不需要独立性
Linearity of ExpectationEx[R₁+R₂] = Ex[R₁]+Ex[R₂]，k 项推广 Ex[ΣaᵢRᵢ] = ΣaᵢEx[Rᵢ]。杀手锏：不需要任何独立性——两枚骰子的和的期望是 7，哪怕两骰被恶魔操控得完全相关，只要各自公平。
帽子问题（19.5.2）：n 个人的帽子随机发还，拿到自己帽子的人数 G 拆成指示变量之和，每人拿对概率 1/n，所以 Ex[G] = n·(1/n) = 1——与 n 无关！定理 19.5.4：期望发生的事件数 = ΣPr[Aᵢ]。顺手白拿一个恒等式：二项分布期望 np（式 19.13 的组合求和一秒收工）。优惠券收集（19.5.4）：集齐 n 种的期望购买数 = n·Hₙ ~ n ln n——调和数又来了。
终局自测
Final Check八题，覆盖 19.1–19.5。
彩蛋与课后挑战
Easter Eggs & ProblemsChernoff 怎么把彩票买成正期望（19.4.7 末尾）
州彩票一半销售额发奖、一半"装修州长官邸"，正常期望是 −50%。但大众爱挑生日号（1–31）和"红袜队夺冠日"，这些热门号中奖要跟一大群人分池。前 MIT 数学教授 Hermann Chernoff 专门买冷门组合——意外的"对手串通"让他把期望拉到 +7 美分/美元。与 Nick/Eric 的故事正好互为镜像：串通伤你，别人无意的串通可以喂你。
随机化算法：随机性当性能工具（19.3.3 侧栏）
共享总线的广播时机用指数退避（exponential backoff）——每次冲突后随机延迟翻倍；quicksort 随机选主元，让任何输入的期望运行时间都是 O(n log n)。信封猜数是它们的精神原型：对手知道你的确定性策略就能针对你，随机化让"针对"失效。
课后挑战（均出自原书习题）
- 19.1 证明：两事件独立 ⟺ 它们的指示变量独立。
- 条件期望与全期望（对应正文定义 19.4.4 / 定理 19.4.5）：(a) 证明条件期望 Ex[R|A] 及其按缩小空间求和的展开，(b) 给出全期望定律的完整证明（分组重排）。
- 19.28 不用线性的方法直接算 Σk·C(n,k)pᵏ(1−p)ⁿ⁻ᵏ = np，体会两种证明的落差。
- 18.31（前章预热） 三硬币定义 D="偶数枚正面"：A、B、C、D 不是相互独立，却 3-way 独立——动手验证。