概率DP学习笔记

longdie · 2020-12-31 14:52:10 · 个人记录

概率DP学习笔记

前置知识为高中基本数学知识，在此不讲。

知识

1. 条件概率 即使学过，但它很重要。 P(A|B) = \frac{P(A\ \bigcap B)}{P(B)}
2. 全概率公式 其实就是乱搞了搞。 设事件B1,B2,B3..Bn是一个完备事件组(事件两两互斥且所有事件交集为全集，这些事件也被称作样本空间的划分)，则对于任意一个事件A，有如下公式成立： P(A) = P(A|B1)P(B1) + P(A|B2)P(B2) + ... + P(A|Bn)P(Bn);

   其实就是换了一种方式。

3. 数学期望 通俗来说就是随机变量取值和概率的乘积之和。 性质 ： 数学期望是线性函数，满足E(aX + bY) = a * E(X) + b * E(Y)。 此性质具重要，是期望可以线性递推的依据。
4. 贝叶斯公式
   • 简单版 ： P(A)\times P(B|A) = P(B) \times P(A|B) 一般推到： P(A|B) = \frac{P(B|A) \times P(A)}{P(B)}
   • 真 * 贝叶斯公式 P(Ai|B) = \frac{P(B|Ai)P(Ai)}{\sum_{j=1}^{n} P(Aj|B)P(B)}

     其实就是个全概率公式套贝叶斯公式。

5. 概率DP 通俗点感性理解就是用DP思想去解决概率问题，一般通常用递推解决。 比较恶心人的地方是感觉很绕，令人难以理解。
   建议在题里慢慢感受它的奇妙毒瘤。

   收集邮票

   题目链接

   题目

   有n种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是n种邮票中的哪一种是等概率的，概率均为1/n。但是由于凡凡也很喜欢邮票，所以皮皮购买第k张邮票需要支付k元钱。 现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。

   分析

   一道令人云里雾里的题。
   提醒：千万不要走进一直买买买却一直收集不够的误区，这样会 mengbi 的。

可以先算出期望张数。
设f[i]为现在已经取了i张邮票，把剩下的邮票取走的期望次数。
显然f[n] = 0, 现在已经取得i张邮票，所以下一次有 \frac{i}{n} 的概率选到已经选的，显然有 \frac{n-i}{n} 的概率选到没选的。

那么转移方程为： f[i] = \frac{i}{n}(f[i] + 1) + \frac{n-i}{n}(f[i+1]+1), 化简一下可得 ： f[i] = f[i+1] + \frac{n}{n-i}

显然这是一个自己转移自己的方程，本来没有什么头绪，但是却通过数学中的移项却消掉了它，虽然感性理解很难，但是事实就是这样，小编也很奇怪。

恩，似乎推出了一个柿子，但是与题目的要求没有啥关系，没关系，我们可以再设g[i]表示已经买了i张邮票，把剩下的邮票买走的期望钱数。

我们试着套上面的柿子，那么g[n] = 0, 下一次有 \frac{i}{n} 的概率买到已经买的，显然有 \frac{n-i}{n} 的概率买到没买的。 所以转移方程为:

化简得： g[i] = \frac{i}{n-i} \times f[i] + g[i+1] + f[i+1] + \frac{n}{n-i}