摘要：
本文主要讲解了怎样运用递推法求解一个离散型随机变量的数学期望，首先介绍数学期望，然后是数学期望的性质，最后通过例题的形式，分析如何利用递推及性质求解一个离散型随机变量的数学期望。
首先应该知道数学期望的定义：
数学期望(mean)（亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。它反映随机变量平均取值的大小。因为随机变量分为离散型和连续性，对应的数学期望也有不同的求法。
简单来说一个离散型随机变量的例子，设投掷一个色子的到的数为随机变量x，得到的数可能是1,2,3,4,5,6，它们的概率都是1/6，那么x的数学期望就是（1/6 * 1）+（1/6 * 2）+（1/6 * 3）+（1/6 * 4）+（1/6 * 5）+（1/6 * 6） = 21/6；
然后对应数学期望的线性性质有：
E（C） = C；常数的期望等于期望本身。
E（CX） = CE（X）；
E（X + Y） = E（X） + E（Y）；也就是说和的期望等于期望的和。
最后，也是最难的一步，根据不同的情况写出递推式，最后求解期望。
下面题为例，侧重写出递推式的过程。
题意
给出一个n，n随机的除以它的一个因子c变成n/c计数一次，问如此重复随机的除以它的一个因子直至最后变成1为止 所除的次数的数学期望。
解题思路
定义状态dp[i]为：数字i循环的随机的除以它的一个因子变为1所需次数的数学期望
最后dp[n]即为所求；
设n的因子从小到大依次是1，a2，a3，a4...aN-1，n，个数是N，可以知道的是随机选择其中一个因子都是对应因子的次数的数学期望加一步，根据数学期望的线性性质可以写出：
dp[n] = (dp[1] + 1)/N + (dp[a2] +1)/N + (dp[a3] + 1)/N + (dp[a4] + 1) /N + ... + (dp[aN-1] + 1)/N + (dp[n] + 1)/N;
化简可得：
dp[n] = (dp[a2] + dp[a3] + dp[a4] + ... + dp[aN-1] + N) / (N - 1);
代码如下：
1 #include <cstdio> 2 3 const int maxn = 100000 + 10; 4 double dp[maxn]; 5 int main() 6 { 7 dp[1] = 0; 8 for(int i = 2; i < maxn; i++) { 9 double sum = 0; 10 int cnt = 0; 11 for(int j = 1; j * j <= i; j++) { 12 if(i % j == 0) { 13 sum += dp[j]; 14 cnt++; 15 if(i / j != j) { 16 sum += dp[i/j]; 17 cnt++; 18 } 19 } 20 } 21 dp[i] = (sum + cnt)/(cnt-1); 22 } 23 int T, t = 1; 24 int n; 25 scanf("%d", &T); 26 while(T--) { 27 scanf("%d", &n); 28 printf("Case %d: %.7lf ", t++, dp[n]); 29 } 30 return 0; 31 }
light OJ 1104 Birthday Paradox
题意
输入一年的天数，问至少有几个人才能保证两个人生日是同一天的概率超过%50.
解题思路
至少有几个人才能保证两个人的生日是同一天的概率超过%50，我们可以反向思考，至少几个人才能保证每个人的生日都不重复的概率低于%50.
每个人的生日可能是1/n，那么第i个人的生日不同于之前所有人的概率就是(n - i) / n，那么整个事件发生的概率就是这i个人的概率的乘积小于等于%50.
1 #include <cstdio> 2 int main() 3 { 4 int n; 5 int T, t = 1; 6 scanf("%d", &T); 7 while(T--) { 8 scanf("%d", &n); 9 double ans = 1.0; 10 for(int i = 1; ; i++) { 11 ans *= (double)(n - i) / n; 12 if(ans <= 0.5) { 13 printf("Case %d: %d ", t++, i); 14 break; 15 } 16 } 17 } 18 return 0; 19 }
题意
输入n和n个数，每个位置上的数表示该格子的金币数，从第一个格子出发，每次投掷一个色子，出现多少就意味着向后走几步，走到那个格子就将其对应的金币收走，问最后获得金币数的数学期望。
解题思路
定义状态dp[i]从第i个格子走到第n个格子所获得金币数的数学期望
最后dp[1]即为答案。
首先应该想到的是第i个格子的数学期望是它能走到的格子的数学期望除以总的能走到的格子数 之和，即dp[i] = dp[i]/cnt + dp[i + 1]/cnt + dp[i +cnt]/cnt;其中cnt为它能走到的格子数。
然后逆着递推计算，最后输出dp[1]即可。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int maxn = 110; 6 double dp[maxn]; 7 int n; 8 9 int main() 10 { 11 int T, t = 1; 12 scanf("%d", &T); 13 while(T--) { 14 scanf("%d", &n); 15 for(int i = 1; i <= n; i++) { 16 scanf("%lf", &dp[i]); 17 } 18 19 for(int i = n - 1; i >= 1; i--) { 20 int cnt = min(n - i, 6); 21 for(int j = 1; j <= cnt; j++) { 22 dp[i] += dp[i + j]/(1.0*cnt); 23 } 24 } 25 printf("Case %d: %.7lf ",t++, dp[1]); 26 } 27 return 0; 28 }
在算法竞赛中，经常会出一些涉及一些概率论的知识，代码不难实现，关键是通过题意找出递推关系即可。