期望与概率记录¶

首先期望的重要性质，注意$X$为随机变量

$E(aX)=aE(X)$

$E(X+Y)=E(X)+E(Y)$

$XY$独立时$E(XY)=E(X)E(Y)$

[AGC019F] Yes or No¶

题面翻译¶

有 $N+M$ 个问题，其中有 $N$ 个问题的答案是 YES，$M$ 个问题的答案是 NO。当你回答一个问题之后，会知道这个问题的答案，求最优策略下期望对多少。

答案对 $998244353$ 取模。

首先考虑暴力dp，考虑运用性质2，设 $f(n,m)$ 表示 $n,m$ 时的期望，我们选择 $n,m$，中最多的来选择，此随机变量分为两部分：当前选的和之后选的；当前选因为最大的，可以得出当前选的期望为：$ \frac{\max (n,m)}{m+n}$，之后选的有可能这个是少了一个 yes 或少了一个no，考虑用概率来考虑之后选的，期望为：$\frac{n}{m+n} f(n-1,m)+\frac{m}{m+n}f(n,m-1)$。

所以总递推式子为 $f(n,m)=\frac{\max (n,m)}{m+n}+\frac{n}{m+n} f(n-1,m)+\frac{m}{m+n}f(n,m-1)$。

尝试优化，设 $m\leq n$,我们可以仍然考虑单个给我们带来的期望，当前局面若为 YES,猜对了有贡献;当前局面若为 NO,没猜对无贡献但是我们却可以让 $m$减小，也就是 NO 时 $n$ 仍然可以保持最大。考虑期望最坏的情况，此时我们一直没有猜对，$m$ 一直减小减小到了 $0$，最后全是 $n$，这样就可以猜对 $n$ 次，而其它不同的情况的猜对次数肯定比这个高，所以期望保底有 $n$。

需要注意的是，即使前期一直猜对导致n=m，期望仍不会低于 $n$，因为 $m>n$ 的局面我们只需转化为 $n>m$ 的局面来看待发现期望的变化仍然一样。

这是我们的出来了由 $n>m$ 局面得来的保底期望，剩下的便是 $n=m$ 时的局面，$n=m$ 时我们选择哪一个的概率都是 $\frac{1}{2}$，所以若是单次选择，期望便是 $\frac{1}{2}$。

考虑这种局面的总期望，由于选择对错的随机变量和局面数的随机变量无关，由$E(XY)=E(X)E(Y)$，我们可以得出来$n=m$所带来的贡献。其实就是拿“期望出现的 $n=m$ 的局面数”乘上“期望单次选择对错"（即 $\frac{1}{2}$)。

那么我们现在的问题就只差求出来“期望出现的 $n=m$ 的局面数”，这个东西改咋子求嘞?可以轻易发现这东西就是出现 $n=m$ 的局面的概率（因为不出现 $n=m$ 的局面的概率乘上 $0$ 没了）。设这个点为 $(k,k)$，也就是说我们通过减 $n$ 或 $m$ 减到了 $(k,k)$,也就是说总共减去了 $n-k+m-k$,而我们究竟有多少种方案走到这个地方呢？可以知道有 $n-k$ 次 yes，所以我们可以得出有 $\binom{n-k+m-k}{n-k}$ 种方案走到(当然要是你考虑从 no 出发了话下面就是 $m-k$)，但是因为是要求全程的方案（也就是经过，而不只是到达），所以我们又要从 $(k,k)$ 走到 $(0,0)$,这个好求，总距离$2k$，$k$ 个 yes,即 $\binom{2k}{k}$。综上，经过的总方案为$\binom{n-k+m-k}{n-k}\binom{2k}{k}$.

只需要再除去总路径的方案数就大功告成了。总距离为 $n+m$,选 yes 的有 $n$，也就是说总方案数为 $\binom{n+m}{n}$。所以得出“期望出现的 $n=m$ 的局面数”为$\displaystyle\sum_{k=1}^{min(m,n)}\frac{\binom{n-k+m-k}{n-k}\binom{2k}{k}}{\binom{n+m}{n}}$

ok总结一下吧，总共期望就是：

\[max(n,m)+\frac{1}{2}\displaystyle\sum_{k=1}^{min(m,n)}\frac{\binom{n-k+m-k}{n-k}\binom{2k}{k}}{\binom{n+m}{n}}\]

来自黄赫哲。