概率与期望

· · 个人记录

概率与期望

一、概率

随机事件:

1.可以重复试验

2.可以枚举所有可能情况

3.出现的情况无法预料

样本空间:指的是随机事件的所有可能(样本点)的集合

离散的和连续的

离散的随机变量：X

P(X=1)=1/6（骰子点数为一概率）

P:概率

二、期望Expectation(倒退推)

E(X)=∑Pi*Xi(离散型随机变量)

   =∑概率*权值

eg:掷一个骰子点数的期望:

E(X)=1*1/6+2*1/6+3*1/6+......6*1/6

掷一个骰子点数平方的期望:

E(X)=1*1/6+4*1/6+9*1/6+......36*1/6

性质:E(a*X+b*Y)=a*E(X)+b*E(Y)

三、排列组合:

A(m,n)=m!/(m-n)!(排列)

C(m,n)=A(m,n)/A(n,n)(组合)

例一、40支笔,30黑,10红,任取4支,至少一支是红色概率？

P(A)=1-P(B)=1-C(30,4)/C(40,4)

P(A):结果

P(B):全黑

1:100%

例二、两篮球运动员,投球命中率分别为60%与50%,各投一次,问:

1.都命中概率

2.恰好一人命中

  解:当A∩B={∅},即A,B之间无影响时(独立),P(A∩B)=P(A)*P(B)

     当A∩B≠{∅},即A,B之间有影响时,见笔记

例三、洛谷SP1026

假设已出现i面,再扔一次,仍为这i种,概率为i/n;为新的的概率为(n-i)/n

dp[i]:表示已出现了i面，还期望掷多少次骰子使得每一面都出现的次数

dp[i]=i/n*dp[i]+(n-i)/n*dp[i+1]+1

dp[i]=dp[i+1]+n/(n-i)

边界条件:dp[n]

求:dp[0]

例四、POJ2096

dp[i][j]:已找到了i种bug且在j各子系统中
  1.在i种bug中,也在j种子系统中,p1=i*j/(n*s)
  2.在i种bug中,不在j种子系统中,p2=i*(s-j)/(n*s)
  3.不在i种bug中,在j种子系统中,p3=(n-i)*j/(n*s)
  4.不在i种bug中,也不在j种子系统中,p4=(n-i)*(s-j)/(n*s)
dp[i][j]=p1*dp[i][j]+p2*dp[i][j+1]+p3*dp[i+1][j]+p4*dp[i+1][j+1]+1