期望练习
P1393 Mivik 的标题
不难想到一个暴力\(dp\),\(dp_{i,j}\)表式前\(i\)位匹配了\(j\)位的概率,如果\(n\)不大直接矩阵就行了
这里我们变化一下思路,考虑设\(f_i\)表示到\(i\)位第一次匹配到\(S\)的概率
不难发现答案即为\(\sum\limits_{i=1}^nf_i\)
对于计算\(f_i\),考虑\(\dfrac{1}{m^{|S|}}\)减去\(\sum\limits_{i=1}^{i-|S|-1}f_i\)以及\(\sum\limits_{j\in Border}f_{i-|S|+B_j}\)
前面的那个可以直接前缀和,后面那个的我们可以直接将\(Border\)分为\(log|S|\)个等差数列,同样分开前缀和即可(好像很麻烦)
这里介绍一个很新的东西
对于随机变量\(X\)
定义\(f(x)=\sum\limits_{i=0}Pr(X=i)x^i\),称之为概率生成函数
不难发现\(f(1)=1\)
\(f’(x)=\sum\limits_{i=1}iPr[X=i]x^{i-1}\)
则\(f'(1)=E(X)\)
对于这道题我们定义\(F(x)\)表示第一次匹配到\(S\)的\(n\)长度的生成函数
\([x^i]G(x)\)表示未匹配到\(S\)但已经选了\(i\)个字符的概率
对于这道题,我们要求的就是\(1-[x^n]G(x)\)
首先有个式子是\([x^i]F(x)+[x^i]G(x)=[x^{i-1}]G(x)\),这个不难理解
我们形式话一点就是\(F(x)+G(x)=1+G(x)x\)
\(F(x)=G(x)\times (x-1)+1\)
还有个式子,我们考虑对一个未完成序列后面直接接一个\(S\)
如果是长度为\(i\)的序列直接接了\(S\),那他一定会结束
我们设\(a_i\)表示\(i\)长度是不是\(border\)
则\([x^i]G(x)(\dfrac{1}{m})^{|S|}=\sum\limits_{j=1}^{|S|}a_j[x^{i+j}]F(x)(\dfrac{1}{m})^{|S|-j}\)
也即是\(G(x)(\dfrac{1}{m}x)^{|S|}=\sum\limits_{i=1}^{|S|}a_iF(x)(\dfrac{1}{m}x)^{|S|-i}\)
也即\(G(x)=\sum\limits_{i=1}^{|S|}a_i\dfrac{F(x)}{(\frac{x}{m})^i}=\sum\limits_{i=1}^{|S|}a_i\dfrac{(G(x)\times (x-1)+1)}{(\frac{x}{m})^i}\)
\(G(x)=((G(x)\times (x-1)+1))\sum\limits_{i=1}^{|S|}\dfrac{a_i}{(\frac{x}{m})^i}\)
好像化不走了
同时乘个\(x^S\)
\(G(x)\dfrac{x^S}{m^S}=(G(x)(x-1)+1)\sum\limits_{i=1}^{|S|}a_i(\dfrac{x}{m})^{|S|-i}\)
我们不妨将\(\sum\limits_{i=1}^{|S|}a_i(\dfrac{x}{m})^{|S|-i}\)记为\(H(x)\)
则\(G(x)\dfrac{x^S}{m^S}=(G(x)(x-1)+1)H(x)\)
\(G(x)=\dfrac{H(x)}{\dfrac{x^S}{m^S}-H(x)(x-1)}\),如果直接求逆或者\(bostan−mori\)
P4548 [CTSC2006]歌唱王国
和上题差不多,只是改成求期望生成多少长度可以得到\(S\)
不难发现就是\(F'(1)\)
\(F(x)=G(x)\times (x-1)+1\)
则\(F'(x)=G'(x)x+G(x)-G'(x)\)
\(F'(1)=G(1)=H(1)m^S=\sum\limits_{i=1}^{|S|}a_im^i\)
给国与赌场
大致题意:你有\(X\)的钱\((X<1)\),你可以考虑拿\(Y\)的钱去赌,有\(p\)的概率变成\(2Y\),\(p<\dfrac{1}{2}\),有\(1-p\)的概率变成\(0\),你每次的\(Y_i\)必须单调递增,如果不能拿出这样的\(Y\)为输,否则到\(1\)为赢,求在最优策略下赢的概率
由于\(p<\dfrac{1}{2}\),那其实拖得越久赢的概率越小,所以只要\(X>\dfrac{1}{2}\),我们就可以直接用\(\dfrac{1}{2}\)
对于\(X<\dfrac{1}{2}\)，最优策略似乎是拿在小数二进制下的最低位,不会证
剩下的\(Dp\)也很复杂,咕了
补充
条件概率\(P(A|B)=\dfrac{P(A\cap B)}{P(B)}\)
一个有意思的问题
1.一对夫妇有两个孩子,已知其中一个是女孩,求另一个也是女孩的概率
事件\(A\)一个是女孩
事件\(B\)另一个是女孩,\(A,B\)互相独立
\(P(A)=P(B)=\dfrac{1}{2},P(A|B)=\dfrac{1}{2}\)
2.一对夫妇有两个孩子,已知有女孩,求都是女孩的概率
事件\(A\)都是女孩,\(P(A)=\dfrac{1}{4}\)
事件\(A\)有女孩,\(P(B)=\dfrac{3}{4}\)
\(P(A|B)=\dfrac{1}{3}\),可以发现问题的关键在于有和其中一个是的区别