基本概念
随机变量：有多种可能的取值的变量
(P(A)：)事件(A)发生的概率
(E(X)：)随机变量X的期望值，(E(X)=Sigma[P(X=i)*i])
独立事件：互相不影响的事件，满⾜(P(AB)=P(A)P(B)) 前提：(A,B);两个随机变量是独立的
对于独立事件，我们有(E(AB)=E(A)E(B))
常用公式
（等比数列求和公式+极限法）
期望的线性性：(E[X+Y]=E[X]+E[Y])
需要注意的是，以上的(X,Y)都是随机变量，不是事件，例如两个扔骰子的点数和。
(Sigma_{i=0}^n=frac{1-x^{n+1}}{1-x^n}),这是等比数列求和公式的变形
前缀和技巧
前缀和技巧是概率期望中很重要的一个技巧
对于离散变量 (X，P(X=K)=P(X<=K)-P(X<=K-1))
例：
1. 有 (n) 个随机变量 (X[1…n])，每个随机变量都是从 (1…S) 中
随机⼀个整数，求 (Max(X[1…n]))的期望
(Sol:)求最大值的期望，根据公式答案为(Sigma_{i=1}^{S}P[max=i]i)
(P[max=i])很难求，但我们可以用前缀和的思想预处理出(P[max<=i-1])和(P[max<=i])，相减即可。
(P[max<=i]=(frac{i}{S})^i)
2. 求证：概率为 (p) 的事件期望(frac{1}{p})次后发生
首先这个问题很显然，我们抛硬币的时候期望抛2次得到正面或者反面
用数学方法证明如下
(Sol:)使用反向前缀和，设成功次数为(X)，则(E[X=i]=E[X>=i]-E[X>=i+1]=(P[X>=i]-P[X>=i+1])*i)
容易得出(P[x>=i]=(1-p)^{i-1})，因为第(i)次是有可能成功的
所以(E[X=i]=[(1-p)^{i-1}-(1-p)^{i}]*i)
我们展开发现
(ans=(1-p)^0-(1-p)^1+2*(1-p)^1-2*(1-p)^3+3*(1-p)^3.......=Sigma_{i=0}^{infty}(1-p)^i)
根据等比数列求和公式得到(ans=frac{1-(1-q)^{infty}}{p})，又因为(qin(0,1))，所以(ans=frac{1}{p})
得证
概率为 (p) 的事件期望(frac{1}{p})次后发生
这个结论非常重要，之后很有用
另外的小技巧
很多东西都可以看成随机变量或用随机变量表示
例如表达式(exp>=0)，(exp=Sigma_{i=1}^{+infty}i<=exp)，这个其实很显然,相当于你前面有多少个人再加(1)就是你的排名
拿球问题
1.箱子里有 n 个球 1…n，你要从里面拿 m 次球，拿了后放回，求取出的数字之和的期望
(Sol:) 每个球都有(frac{n}{m})的概率被取到，根据期望的线性性质，取出数字之和的期望等于取出数字的期望之，求出每个数字期望，相加即可。
2.箱子里有 n 个球 1…n，你要从里面拿 m 次球，拿了后不放回，求取出的数字之和的期望
(Sol:)这个问题相对难想,设(E(S))为答案的期望，设(E(Xi))为第(i)项贡献的期望
则(E(S)=E(Sigma_{i=1}^{n}Xi)=Sigma_{i=1}^{n}E(Xi))
设(E(Yi))表示(i)取出次数的期望，在这个题目中显然(in(0,1))
为什么要这么设计，因为这是解决拿球问题的通法
那么我们得到(Xi=Yi*i)，对两边取期望得到(E(Xi)=E(Yi)*i)
接下来是重点
期望有点类似平均值的思想，或者说将总和离散了，也就是说(Sigma Yi=m)
那么又因为每个球都是独立平等的，所以每个(Yi)一定相等，即(Yi=frac{m}{n})
以上两句话是这类题的精髓
那么代回去得到(E(S)=Sigma_{i=1}{n}frac{m}{n}*i)，得到的结果和第一问一样，(ans=frac{m(n+1)}{2})
3.箱子里有 n 个球 1…n，你要从里面拿 m 次球，拿了后以p1 的概率放回，以 p2 的概率放回两个和这个相同的球，求取出的数字之和的期望
(Sol:)相信经过了前两问的铺垫，这一问思路已经显而易见了，和第二问完全一样，和这些概率没半点关系，当然你可能会问放回两个相同的球的话，一个球的(Yi)可能会增大，但别忘了，这类题的核心是每个球都是独立的平等的，其它球也有等概率放回两个，所以不管放回多少个，每个(Yi)还是相等的，平分(m)，然后只需要和第二问一样做就可以了，显然(ans=frac{m(n+1)}{2})
游走问题
• 在⼀条 n 个点的链上游走，求从⼀端走到另⼀端的概率
(Sol:) 老规矩，设答案为(S)，那么(E(S)=Sigma E(Xi))，(E(Xi))表示从(i)节点走到下一个节点的期望步数，那么我们可以像做(DP)列出一个“状态转移方程”，设我们现在要从(A)走到下一个点，我们从(B)走过来，那么我们可以直接一步过去，也可以往后退再回来走过去，所以我们得出了转移方程
(E(A)=frac{1}{2}*1+frac{1}{2}(1+E(B)+E(A)))
那么你可能会说，没有考虑往后退几步再往前走等等情况，但其实(E(B))已经被更新完毕了，也就是说(E(B))的值已经包含了所有可能，这所有可能也都包括到(E(A))的路径，可能是往后退(x)步，所以我们只用再加上(E(A))即可，这一直让初学的我有些困惑，是很重要的一个思想
将以上式子展开可以得到(E(A)=E(B)+2)，又因为(E(1)=1)(只有一种路径)，所以(E(Xi))构成了(1,3,5,7,9)的等比数列，我们只需用等比数列求和公式，得出(ans=(n-1)^2)。
• 在⼀张 n 个点的完全图上游走，求从一个点走到另一个点的概率
(Sol:) 第二个问题很有意思，其实不难
完全图：任意两点之间都有直接连边的图
因为是完全图，所以任意两个点都是平等的，除了出发点(A)外还有(n-1)个点，还是分两种情况讨论：第一种情况是直接到达(B)，另一种情况是走到其它的点(C)，也就是说
(E(A)=frac{1}{n-1}*1+E(C))
那我们发现问题了，(A)和(C)应该是平等的，不能因为我们选择了(A)就是特殊的，那么我们就将问题变为：每次都有(frac{1}{n})的概率到达目标点，从(A)开始就不停地尝试，这也就和我们之前的推论一样了
概率为 (p) 的事件期望(frac{1}{p})次后发生
好啊，那么答案(E(S))不就是(n-1)了吗。
• 在⼀张 2n 个点的完全二分图上游走，求从一个点走到另一个点的概率
• 在⼀张 n 个点的菊花图上游走，求从⼀个点走到另⼀个点的概率
• 在⼀棵 n 个点的树上游走，求从根走到 x 的期望步数
• 构造⼀张200个点的无向图，使得从 S 走到 T 的随机游走期望步数>=1000000