第92课 - 概率与期望

学习目标

通过本节课的学习，你将能够：

1. 理解概率的基本定义及其在算法问题中的作用。
2. 掌握期望值（数学期望）的概念与计算方法。
3. 学会使用模拟的方法估算概率与期望。
4. 应用全期望公式等工具解决经典的随机过程与算法问题。

核心概念

1. 概率：不确定性有多少可能？

概率用来衡量一个随机事件发生的可能性大小，是一个介于0（不可能）到1（必然）之间的数值。在算法问题中，我们常需要计算“某个特定结果出现的概率是多少？”

通俗比喻：抛一枚均匀硬币，正面朝上的概率是0.5。这意味着如果我们抛很多很多次（理想情况下），大约一半的结果会是正面。

关键公式： P(事件A) = 事件A发生的可能结果数 / 所有可能结果的总数

2. 期望值：平均下来会怎样？

期望值是概率论中最重要的概念之一，它代表了在多次重复实验中，某个随机变量长期平均的结果。你可以把它理解为“在大量重复尝试后，某个量会稳定在哪个平均值附近”。

通俗比喻：掷一个公平的六面骰子，我们期望得到的点数是多少？答案是3.5。虽然你永远掷不出3.5点，但如果你掷成千上万次，计算所有点数的平均值，它会非常接近3.5。

关键公式： 对于离散型随机变量X，其期望E(X)为： E(X) = Σ [每个可能的值 × 该值发生的概率]

3. 全期望公式与条件期望

有时，一个事件的期望可以通过划分不同的情境（条件）来简化计算。

• 条件期望：E(X|Y) 表示在事件Y发生的条件下，随机变量X的期望。
• 全期望公式：E(X) = Σ E(X|Y=y) * P(Y=y) 这意味着，X的总体期望，等于在所有可能条件Y=y下，X的条件期望的加权平均（权重就是Y=y发生的概率）。

4. 大数定律简介

大数定律从理论上保证了：当独立重复实验的次数足够多时，事件的频率会趋近于其概率，样本的平均值会趋近于总体的期望。这是我们用模拟（蒙特卡洛方法）来估算概率和期望的理论基础。

代码示例

示例1：用模拟估算概率与期望

通过重复模拟一个随机过程，来估算其概率和期望值。

import random
import statistics

def simulate_dice_rolls(num_trials=100000):
    """
    模拟掷一个公平的六面骰子 num_trials 次。
    估算得到数字6的概率，以及所有点数的平均值（期望）。
    """
    results = []
    count_six = 0
    
    for _ in range(num_trials):
        roll = random.randint(1, 6)  # 随机生成1到6之间的整数
        results.append(roll)
        if roll == 6:
            count_six += 1
    
    # 计算估算值
    estimated_prob_of_six = count_six / num_trials
    estimated_expectation = statistics.mean(results)
    
    return estimated_prob_of_six, estimated_expectation

# 运行模拟
prob, exp_value = simulate_dice_rolls(500000)
print(f"掷50万次骰子:")
print(f"  得到6的频率（估算概率）: {prob:.4f}  (理论值: {1/6:.4f})")
print(f"  点数的平均值（估算期望）: {exp_value:.4f}  (理论值: 3.5)")

输出示例：

掷50万次骰子:
  得到6的频率（估算概率）: 0.1668  (理论值: 0.1667)
  点数的平均值（估算期望）: 3.4998  (理论值: 3.5000)

示例2：解析计算期望

对于一些简单问题，我们可以直接用数学公式精确计算期望，这比模拟更高效、更准确。

def expected_sum_of_two_dice():
    """
    计算掷两个公平六面骰子，点数之和的期望值。
    解析法：E(总和) = E(骰子1) + E(骰子2) = 3.5 + 3.5 = 7
    模拟法验证。
    """
    # 解析解
    analytical_expectation = 7.0
    
    # 模拟解
    num_trials = 100000
    sum_results = []
    for _ in range(num_trials):
        die1 = random.randint(1, 6)
        die2 = random.randint(1, 6)
        sum_results.append(die1 + die2)
    simulated_expectation = statistics.mean(sum_results)
    
    return analytical_expectation, simulated_expectation

analytic, simulated = expected_sum_of_two_dice()
print(f"两个骰子点数之和的期望:")
print(f"  解析计算值: {analytic}")
print(f"  模拟估算值: {simulated:.4f}")

输出示例：

两个骰子点数之和的期望:
  解析计算值: 7.0
  模拟估算值: 7.0021

示例3：经典问题 - “分糖果”问题

一个袋子中有5个红糖和3个白糖。你每次随机拿出一个糖，不放回。问你需要拿几次（平均）才能拿完所有的红糖？

思路分析： 这是一个经典的“收集所有红球”问题。我们可以利用期望的线性性质（尽管不独立，但期望的线性性质仍然成立）和全期望公式来求解。

设随机变量 T 为拿完所有红糖需要的总次数。 设 Xi 表示从拿第 i-1 个红糖到拿第 i 个红糖之间需要的步数（X1 是从开始到拿到第一个红糖的步数）。 那么 T = X1 + X2 + ... + X5。 根据期望的线性性质：E(T) = E(X1) + E(X2) + ... + E(X5)。 Xi 的概率分布依赖于当前袋中红糖和白糖的数量。这可以用全期望公式精确计算，但对于本问题，模拟法更直观易懂。

import random

def simulate_candy_collector():
    """模拟拿完所有红糖需要的次数"""
    candies = ['R'] * 5 + ['W'] * 3 # R: Red (红), W: White (白)
    total_trials = 100000
    total_steps = 0
    
    for _ in range(total_trials):
        # 重置袋子
        bag = candies.copy()
        random.shuffle(bag) # 模拟随机抽取顺序
        # 找到所有红糖的位置
        red_positions = [i for i, candy in enumerate(bag) if candy == 'R']
        # 找到最右边的红糖位置，这个位置+1就是所需次数
        steps = max(red_positions) + 1
        total_steps += steps
    
    return total_steps / total_trials

expected_steps = simulate_candy_collector()
print(f"平均需要抽取 {expected_steps:.2f} 次才能拿完所有红糖。")

输出示例：

平均需要抽取 6.75 次才能拿完所有红糖。

(解析解也是6.75，模拟验证了这一点)

实践练习

练习1：基本期望计算（简单）

一个盒子里有1个红球（价值10分）和9个蓝球（每个价值1分）。随机从盒子中摸出一个球。

1. 计算摸出红球的概率。
2. 计算摸出球的分数的期望值。 编写一个模拟程序，用10000次模拟来验证你的理论计算。

预期输出：

理论概率: 0.10
理论期望: 1.90
模拟概率: 0.1002
模拟期望: 1.9025

(模拟值会因随机性略有浮动)

练习2：条件期望（中等）

一副扑克牌（52张）随机打乱。你从牌堆顶一张一张翻牌，直到翻出第一张A。问平均需要翻多少张牌？ 提示：设 E 为期望。考虑第一张牌的情况：

• 如果是A（概率4/52），则停止，翻了1张。
• 如果不是A（概率48/52），则进入“剩余51张牌中有4张A”的子问题，此时平均还需翻 E' 张，但总次数已经用了1张。

写出你的推理过程，并用模拟程序验证。

练习3：综合应用（较难）

有一个包含 n 个节点的完全图（每两个节点间都有边）。对每条边，独立地以概率 p 染成红色，否则为蓝色。

1. 对于任意一个固定的三角形（三个节点构成），它是纯红色三角形的概率是多少？
2. 期望在图中有多少个纯红色的三角形？ 提示：利用期望的线性性质。设 X_ij 为一个指示变量，当节点i, j, k构成的三角形是纯红时取1，否则取0。总纯红三角形数 Y = Σ X_ij，则 E(Y) = Σ E(X_ij)。

常见错误

1. 混淆概率与频率：概率是理论值，是事件固有的属性；频率是实际模拟中事件发生的比例。当模拟次数不够多时，两者可能差异较大。不能将一次模拟的频率等同于概率。
2. 误用条件概率：在计算 P(A|B) 时，忘记分母是 P(B) 而非 P(A)。记住公式：P(A|B) = P(A∩B) / P(B)。
3. 忽视“期望”的含义：期望是一个加权平均值，它不一定是某个可能出现的具体结果（如骰子期望3.5）。在实际问题中，需要解释期望值的实际意义。
4. 错误应用期望的线性性质：E(X+Y) = E(X) + E(Y) 始终成立，即使X和Y不独立。但 E(XY) = E(X)E(Y) 仅在X和Y独立时成立。初学者容易混淆这两者。
5. 模拟样本量不足：对于概率很小的事件（如p=0.001），需要非常大的模拟次数（如百万次）才能得到相对准确的估计。样本量太小会导致结果波动剧烈，不可靠。

小结

本节课我们探讨了概率与期望这两个核心概念：

• 概率量化了单次事件发生的不确定性。
• 期望值描述了随机变量在长期重复实验中的平均行为，是连接概率与确定性结果的桥梁。
• 全期望公式是处理复杂随机过程的强大工具，通过划分条件简化计算。
• 大数定律是我们使用模拟（蒙特卡洛方法）来估算概率和期望的理论依据。模拟虽然直观，但需要足够的样本量，并且对于精确解，解析法往往更优。

掌握这些概念和工具，将为你理解后续更复杂的随机化算法和博弈论奠定坚实的基础。