概率

接着上一篇的问题 # 上一篇搞清楚了一件事：DDPM 的前向扩散虽然定义成一步一步加噪的马尔可夫链，但因为高斯分布在线性组合下的封闭性，任意时刻的 \(x_t\) 都可以一步算出来：

起因 # 最近在看 DDPM（Denoising Diffusion Probabilistic Models）。前向扩散的定义写得很清楚：从原始图片出发，每一步往上面加一点噪声，一步一步把图片变成纯噪声。

上一篇结尾用全期望公式把 \(V^\pi(s)\) 按"下一个 State"分组展开了。Markov Property 那篇讨论了为什么 Bellman Equation 需要 Markov Property 作为前提。 数学工具准备齐了，我打算正式跟一遍 Bellman Equation 的推导。

起因 # 上一篇讨论了 Markov Property，提到 Bellman Equation 需要它作为前提。 准备看 Bellman Equation 的推导时，我卡在了一个叫 Law of Total Expectation（全期望公式）的地方。它的核心思想是：计算整体期望时，可以先按某个变量的不同取值分组，分别算各组的条件期望，再按组别的概率加权平均。之前那篇定义的 State Value \(V^\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]\)，在 Bellman Equation 里正是用这个思路按"下一个 State"分组来展开。

起因 # 继续跟着 MIT 6.S191 Lecture 5 学强化学习。上一篇理解了 Return、State Value Function \(V^\pi(s)\) 和 Action Value Function \(Q^\pi(s,a)\)。

上一篇讲完 VAE，走到一条因果链：VAE 通过把 Encoder 的输出从确定点变成概率分布，让 latent space 服从已知 prior，于是可以从 prior 采样、交给 Decoder 生成新样本。 整个过程很精巧，但回头看，它对概率计算的依赖很重：Encoder 参数化 \(q(z|x)\)，训练目标里有 KL divergence、有 reconstruction likelihood，每一步都在和 density 打交道。

起因 # 最近在看 GAN 的时候，判别器的训练目标里反复出现两项： \(\log D(x)\) 和 \(\log(1 - D(G(z)))\) 我能看出 \(\log D(x)\) 越大越好——\(D(x)\) 越接近 1，判别器越确信这是真实样本。也能看出 \(\log(1-D(G(z)))\) 在 \(D(G(z))\) 接近 0 的时候最大——判别器越确信生成的是假样本。

起因 # 上一篇文章理清了 latent variable 和 latent space 的概念，最后停在一个地方： 不要直接在复杂的数据空间中生成数据。先在简单的 latent space 中采样一个 \(z\)，再通过学到的映射把 \(z\) 变成 \(x\)。

起因 # 最近在看 MIT 6.S191 Lecture 4——Generative Modeling。在这之前我对生成模型基本没什么了解，刚建立了一个很粗的认知：

上一篇只回答了"为什么不矛盾" # 上一篇文章里，我沿着一个概率问题一路追到了集合论。

起因 # 最近在补概率基础的时候，碰到一个解释：连续分布中，每一个单点的概率都是 0，但整个区间的概率可以是 1。

起因 # 上一篇把 RNN 拆成了两层：state transition 和 output projection。State transition 维护 hidden state，output projection 从 hidden state 中映射出当前任务需要的预测结果。

题目链接 题意：有n扇门，n种钥匙，一一对应。每扇门打开后可能得到k把钥匙（k可能为0）。一扇门还可以用一颗炸弹炸开。现在问要开所有门，使用炸弹的期望个数。 思路：状态压缩。用一个二进制串表示每扇门能打开的门的信息，对应的位上为1表示能打开，为0表示不能打开。

题目链接 题意：n（n<=300）个球，每个球上标有一个标号(a[i]<=300)，从中拿一个，不放回，再拿一个，问第一个球上的数字严格大于第二个球上的数字的概率。 思路：古典概型。总数为n*(n-1)/2…然后标号最大300，不妨用cnt[i]统计标号为i的球的个数。从小往大扫一遍cnt,cnt[i]对分子的贡献就是cnt[i]*cur。。cur 为 sum{cnt[1]..cnt[i-1]}; 最后注意将分子除以2，因为有一半是第一个球比第二个球小的情况。

http://acm.hdu.edu.cn/showproblem.php?pid=4336 题意：有n种卡片，买一包干脆面得到第i种卡片的概率是p[i]，每包干脆面最多有一张卡片，问收集齐所有卡片要买的干脆面的包数的数学期望。 思路：容斥模板题。1.0/p[i]就是拿到某张卡片需要买的包数的数学期望

http://codeforces.com/problemset/problem/148/D # 题意：盒子里有w只白老鼠，b只黑老鼠，公主和魔王轮流取（公主先），先取到白老鼠的人获胜。魔王每次取完以后，盒子中的老鼠会因为吓尿了跑掉一只，跑掉的老鼠不算任何人取的。问公主获胜的概率。

http://codeforces.com/problemset/problem/107/B 题意：有m个部门，每个部分s[i]个人，HW在第h部门，现在要从这m个部门中挑选包括HW在内的n个人去参加比赛，问被挑选的人中有HW的队友（同部门的人）的概率是多少。如果m个部分的人数不够组成n人的球队，输出-1. # 思路：考虑一般情况。至少有一个队友的情况较多，应该从反面考虑，即没有一个队友的情况。选完HW以后面临的状态是：事件总数为从total(m个部门的人员之和)-1个人中选n-1个的方案数，包含的事件数目为从a(a=total-s[h])中选n-1个人包含的方案数。 可以看出分母相同，可以约掉。 # 然后对于边界情况，首先判断total是否比n小。然后，如果a<n-1，表示除去HW所在的h部分之外的人不可能组成n-1个人，也就是一定要选择HW的队友，概率为1.

http://codeforces.com/problemset/problem/518/D 题意：有n个人排队上一个电梯。。。在某一秒内，队首的人有p的概率上电梯，1-p的概率不动。每个人只有在队首的位置才可以上电梯（也就是每一秒内，最多只有一个人可以上电梯）。电梯无线长（也就是上了电梯就不会离开了），问在第t秒的时候，电梯上的人的个数的数学期望是多少。 # 思路：一开始推公式的我还是图样。这题是dp.其实也不难想。dp[i][j]表示第i秒时电梯上有j个人的概率。 当j==n的时候，也就是所以人都上了电梯以后。dp[i+1][j]+=dp[i][j]，对于其他时刻 dp[i+1][j+1]+=dp[i][j]p,dp[i+1][j]+=dp[i][j](1-p). 初始化dp[0][0]=1，即0时刻电梯上有0个人的概率为1. # 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月02日 星期二 15时57分06秒 4File Name :code/cf/518D.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=2E3+7; 34int n,t; 35double p; 36double dp[N][N]; 37int main() 38{ 39 #ifndef ONLINE_JUDGE 40 freopen("code/in.txt","r",stdin); 41 #endif 42 ms(dp,0); 43 dp[0][0] = 1; 44 cin>>n>>p>>t; 45 for ( int i = 0 ; i <= t ; i++) 46 { 47 for ( int j = 0 ; j <= n ; j++) 48 { 49 if (j==n) 50 { 51 dp[i+1][j]+=dp[i][j]; 52 } 53 else 54 { 55 dp[i+1][j+1]+=dp[i][j]*p; 56 dp[i+1][j]+=dp[i][j]*(1-p); 57 } 58 } 59 } 60 double ans = 0 ; 61 for ( int j = 1 ; j <= n ; j++) 62 ans +=j*dp[t][j]; 63 64 printf("%.12f\n",ans); 65 66 #ifndef ONLINE_JUDGE 67 fclose(stdin); 68 #endif 69 return 0; 70}

http://codeforces.com/problemset/problem/312/B # 题意：两个人比赛射箭，先射的人射中的概率是a/b，后射的人射中的概率是c/d，问先射的人赢的概率。 思路：应该叫条件概率。。。？ 不过我们可以用古典概型的思维想。每射一次看成一个点，射中的点用白色表示，没有射中的用黑色表示。如果两个人第i次都没有射中，那么就要继续第i+1 轮，而第i+1轮和之前的每一轮是独立的。等于重复这个过程。所以古典概型的样本总量应该减去宝石两个人都没有射中的点的个数，为bd-(b-a)(d-c)，整理为bc+ad-a*c，设为n.要想第一个人赢，那么对于某一次，只要不是第一个人没射中，第二个人射中这种情况，就都是第一个人赢。而第一个人没射中的事件数为b-a，第二个人射中的事件数为c，总数为（b-a）*c，所以答案为(n-(b-a)*c)/n

http://codeforces.com/problemset/problem/453/A 题意：m面骰子，每面点数出现的概率相同，连续投掷n次，问出现的最大值的数学期望。 思路：手写样例。。。发现答案为 。。。记得把（1/m）^n放进去。 观察答案，可以这样理解（我是用样例推出公式后理解。。。数学差的人心好累）：如果i为最大值，那么n次每次必须投掷出1..i的点数，概率为 (i/m)^n，但是要至少有一个投掷成i，也就是要减去所有的数都是1..i-1中的情况（概率 为((i-1)/m)^n），