递推方法
概述
递推方法是帕斯卡在1654年解决点数问题时使用的方法。他设定一个递推关系，将一个复杂的概率问题分解为更小的、类似结构的子问题，最终通过递推边界条件求解。这个方法本质上是后向归纳（backward induction）思想的原型，在现代博弈论、动态规划和决策理论中广泛应用。
关键内容
帕斯卡的递推方法
设 f(a, b) 为当A还差a局获胜、B还差b局获胜时，A应得的赌注份额。
递推关系
$$f(a, b) = \frac{f(a-1, b) + f(a, b-1)}{2}$$
边界条件
- f(0, b) = 1（A已经赢了，A应得全部赌注）
- f(a, 0) = 0（B已经赢了，A应得0）
计算过程
通过这个递推关系，可以逐步计算出f(a, b)的值。例如：
- f(1, 1) = [f(0, 1) + f(1, 0)] / 2 = [1 + 0] / 2 = 1/2
- f(2, 1) = [f(1, 1) + f(2, 0)] / 2 = [1/2 + 0] / 2 = 1/4
- f(1, 2) = [f(0, 2) + f(1, 1)] / 2 = [1 + 1/2] / 2 = 3/4
- f(2, 2) = [f(1, 2) + f(2, 1)] / 2 = [3/4 + 1/4] / 2 = 1/2
直觉解释
递推关系 f(a, b) = [f(a-1, b) + f(a, b-1)] / 2 的含义：
- 下一局有两种等可能的结果：A赢或B赢
- 如果A赢下一局，局面变为(a-1, b)，A此时的期望份额是f(a-1, b)
- 如果B赢下一局，局面变为(a, b-1)，A此时的期望份额是f(a, b-1)
- 由于两种结果各有1/2的概率，A的总期望份额是两者的平均值
与后向归纳的联系
递推方法本质上是后向归纳： 1. 从已知的边界条件开始（游戏已经结束） 2. 向后推导，一步步计算之前的状态 3. 最终得到初始状态的答案
这正是现代动态规划和博弈论中的核心思想。
与费马方法的比较
| 方面 | 帕斯卡的递推方法 | 费马的组合枚举法 | |------|------|------| | 思路 | 分解问题，逐步递推 | 列举所有情景，计算比例 | | 复杂度 | O(a × b)的计算量 | O(2^(a+b))种情景枚举 | | 优点 | 高效、优雅 | 直观、易于理解 | | 缺点 | 需要建立递推关系 | 对大数字繁琐 | | 原型 | 后向归纳、动态规划 | 样本空间、古典概率 |
意义
为什么递推方法重要
- 问题分解：将复杂问题分解为更小的相同结构的子问题
- 高效计算：避免穷举，通过递推关系大幅降低计算复杂度
- 理论洞察：揭示问题的内在结构，而不仅仅计算数值
- 广泛应用：这个思想在博弈论、动态规划、金融定价等领域无处不在
在概率论和决策理论中的地位
现代应用
博弈论
在完全信息博弈中，利用后向归纳求解子博弈完美均衡。
动态规划
金融衍生品定价
期权定价中的二叉树模型（Binomial Tree）本质上就是帕斯卡的递推方法的应用。