柒葉灬 的博客

柒葉灬 的博客

期望总结(个人笔记9)(未完成)

posted on 2018-09-17 11:52:50 | under 未分类 |

期望题目总结。


  • 期望的定义:在概率论和统计学中,数学期望(mean)(或均值,亦简称期望)是试验中每次可能结果的概率乘以其结果的总和,是最基本的数学特征之一。它反映随机变量平均取值的大小。(百度百科)

    简单来说,期望就是各种情况的平均值。

    值得注意的是,一般期望的题目都是反着推更容易,或者说正着推会错。


  • 1.简单的期望题目往往只有一种转移状态(即不会回来)如期望专题的A题,转移方程如下 $$ dp[i]=a*dp[i-1]$$

但题目往往不会这么简单的,很多题目都会使自己回到自己。比如说期望专题的G题,


  • 2.那么如何解会回到自己的情况呢?这需要一丢丢数学解方程的思想,“移项”。

就拿期望专题的G题举例子,

大意:有 $n$ 个人,其中 $1$ 个是吸血鬼,每天随机两个人相遇,如果都是都是人或者都是吸血鬼则没有事情发生,否则有 $p$ 的几率使村民变吸血鬼,问全变成吸血鬼的期望天数

思路,首先要明白, $dp[x]$ 可能从自己转移。所以 $dp[1]!=0$ ,所以这题显然是不适合正着推,所以设 $dp[i]$ 为需要的步数,得到:

$$q=\frac{x*(n-x)}{C_n^2}*p$$

q是有x个吸血鬼的时候再变个吸血鬼的概率

$$dp[i]=dp[i+1]*q+dp[i]*(1-q)+1$$ $$dp[i]*q=dp[i+1]*q+1$$ $$dp[i]=\frac{(dp[i+1]*q+1)}{q}$$ $$dp[i]=dp[i+1]+\frac{1}{q}$$

因此可以轻易得到 $dp[1]$ 的值。

ps:做一件事情做到完成为止(例如投篮球),期望都是类似于这样加上 $\frac{1}{q}$ 。


  • 3.上面例举的期望题目仍旧是很简单的类型,因为他们之间不会有互相转移的情况,而又互相转移的情况,那么就复杂了。

比如说期望专题的L题,打棒球。

题目大意,一个人在练习棒球,击不中的概率为 $q$ 。如果连续 $ k1 $ 次击中,或者连续 $ k2 $ 次击不中,就停止练习。求练习的期望次数。

看到这题目一脸懵,什么鬼……

先硬着头皮先写下方程式……

设 $f(x)$ 是连续打中x球结束的期望, $w(x)$ 是连续不中x球结束的期望, $p$ 是击中的概率, $q$ 是打不中的概率。

$$f(x)=f(x+1)*p+w(1)*q+1$$ $$w(x)=w(x+1)*q+f(1)*p+1$$

我们就看 $f(x)$ 得到: $$f(x)-f(x+1)*p=w(1)*q+1=A$$ $$f(x)-f(x+1)*p= A $$ $$f(x)=f(x+1)*p+A$$ 于是我们就得到了一个递推的方程式,特殊的 $f(k1)=0$ ,再模拟下去…… $$f(k1-1)=A$$ $$f(k1-2)=(1+p)*A$$ $$\vdots$$ $$f(1)=xA$$ 同理,我们可以得到打不中的期望: $$w(1)=yB$$