• 本文章是[学习笔记]概率与期望进阶的一部分

本文章是[学习笔记]概率与期望进阶的一部分

丢掉寒假作业继续学 题目:Warm up 2
平方期望基本推导:

2.Square of wins: You bought

N

N

(

N

≤

1

0

5

N ≤ 10^5

) lottery tickets. The

i

i

-th of them is winning with p-bility

p

i

p_i

. The event are independent (important!). Find EV of the square of the number of winning tickets. 给你

n

n

个

0

/

1

{0/1}

随机变量

x

i

x_i

，每个变量为

1

1

的概率为

p

i

p_i

求

E

[

(

∑

x

i

)

2

]

E[(\sum x_i)^2]

。

sol: 我们利用下面的期望基本性质对式子展开:

如果

X

,

Y

X,Y

独立，那么

E

[

X

Y

]

=

E

[

X

]

×

E

[

Y

]

E[XY]=E[X]\times E[Y]

E

[

X

+

Y

]

=

E

[

X

]

+

E

[

Y

]

E[X+Y]=E[X]+E[Y]

E

[

(

∑

i

x

i

)

2

]

=

E

[

∑

i

,

j

x

i

×

x

j

]

=

∑

i

,

j

E

[

x

i

×

x

j

]

=

∑

i

≠

j

E

[

x

i

]

×

E

[

x

j

]

+

∑

i

E

[

x

i

2

]

=

∑

i

≠

j

p

i

×

p

j

+

∑

i

p

i

\begin{aligned} E[(\sum_{i} x_i)^2]&=E[\sum_{i,j}x_i\times x_j]\\ &=\sum_{i,j}E[x_i\times x_j]\\ &=\sum_{i≠j}E[x_i]\times E[x_j]+\sum_{i}E[x_i^2]\\ &=\sum_{i≠j}p_i\times p_j+\sum_{i}p_i \end{aligned}

方差基本推导:
之前概率生成函数的时候已经说过了。

V

a

r

(

X

)

=

E

[

(

X

−

E

[

X

]

)

2

]

=

E

[

X

2

−

2

X

E

[

X

]

+

E

2

[

X

]

]

=

E

[

X

2

]

−

2

E

[

X

E

[

X

]

]

+

E

[

E

2

[

X

]

]

=

E

[

X

2

]

−

2

E

2

[

X

]

+

E

2

[

X

]

=

E

[

X

2

]

−

E

2

[

X

]

\begin{aligned} Var(X)&=E[(X-E[X])^2]\\ &=E[X^2-2XE[X]+E^2[X]]\\ &=E[X^2]-2E[XE[X]]+E[E^2[X]]\\ &=E[X^2]-2E^2[X]+E^2[X]\\ &=E[X^2]-E^2[X]\\ \end{aligned}

转为求平方期望

推导中有一个关键，就是

E

[

X

]

E[X]

是一个确定的常数。 因此才会有

E

[

X

]

E[X]

与

X

X

独立，

E

[

E

2

[

X

]

]

=

E

2

[

X

]

E[E^2[X]]=E^2[X]

等结论。

立方期望基本推导:

3.Cube of wins:Same but find EV of the 3-rd or 4-th power. 还是上面那道题，求

E

[

(

∑

x

i

)

3

]

E[(\sum x_i)^3]

和

E

[

(

∑

x

i

)

4

]

E[(\sum x_i)^4]

。

sol: 还是一样的套路:

E

[

(

∑

i

x

i

)

3

]

=

E

[

∑

i

,

j

x

i

×

x

j

×

x

k

]

=

6

∑

i

<

j

<

k

p

i

⋅

p

j

⋅

p

k

+

6

∑

i

<

j

p

i

⋅

p

j

+

∑

i

p

i

\begin{aligned} E[(\sum_{i} x_i)^3]&=E[\sum_{i,j}x_i\times x_j\times x_k]\\ &=6\sum_{i<j<k}p_i·p_j·p_k+6\sum_{i<j}p_i·p_j+\sum_{i}p_i \end{aligned}

4次方一样的。
CF 1187 Expected Square Beauty
详细题解

• 令

b

i

b_i

为

[

l

i

,

r

i

]

[l_i,r_i]

里面的随机数，

X

X

为

b

b

不同段的段数，求

E

[

X

2

]

E[X^2]

•

n

≤

1

0

5

n\leq 10^5

经典平方期望入门题。 设事件

X

i

X_i

表示

b

i

≠

b

i

+

1

b_{i}≠b_{i+1}

，其中我们强制规定

X

n

X_n

为必然事件。 这里一定要注意的是事件

X

i

X_i

与

X

i

+

1

X_{i+1}

互相不独立需要单独计算，计算的话可以考虑简单容斥一下。

E

[

X

2

]

=

E

[

(

∑

i

=

1

n

X

i

)

2

]

=

∑

∣

i

−

j

∣

≥

2

E

[

X

i

]

×

E

[

X

j

]

+

∑

i

E

[

X

i

X

i

+

1

]

+

∑

i

E

[

X

i

2

]

=

∑

∣

i

−

j

∣

≥

2

A

i

×

A

j

+

∑

i

B

i

+

∑

i

A

i

\begin{aligned} E[X^2]&=E[(\sum^n_{i=1} X_i)^2]\\ &=\sum_{|i-j|≥2}E[X_i]\times E[X_j]+\sum_{i}E[X_iX_{i+1}]+\sum_{i}E[X_i^2]\\ &=\sum_{|i-j|≥2}A_i\times A_j+\sum_{i}B_i+\sum_{i} A_i\\ \end{aligned}

A

i

,

B

i

A_i,B_i

懒得写了见之前的博客。
CF 1236 F Alice and the Cactus
概率与期望综合能力测试:)

• 给一个仙人掌，每个点1/2删除。 • 问期望下连通块个数的方差。

V

a

r

(

X

)

=

E

[

(

X

−

E

[

X

]

)

2

]

=

E

[

X

2

]

−

E

2

[

X

]

Var(X)=E[(X-E[X])^2]=E[X^2]-E^2[X]

。 连通块个数

X

=

V

−

E

+

C

X=V-E+C

。 先要算

E

[

V

]

−

E

[

E

]

−

E

[

C

]

E[V]-E[E]-E[C]

。 然后是最精彩的部分:

E

(

(

V

−

E

+

C

)

2

)

=

E

(

V

2

)

+

E

(

E

2

)

+

E

(

C

2

)

+

2

(

E

(

V

C

)

−

E

(

V

E

)

−

E

(

V

C

)

)

E((V-E+C)^2)=E(V^2)+E(E^2)+E(C^2)+2(E(VC)-E(VE)-E(VC))

。 这九种情况依次计算就好:) 放心…你一定不会自闭的…
Fibonacci’s Nightmare
推柿子游戏的噩梦关卡:)

•

a

0

=

1

a_0=1

•

a

n

=

a

i

+

a

j

a_n=a_i+a_j

,其中

i

,

j

i,j

在

[

0

,

n

−

1

]

[0,n-1]

之间随机选择。 • 求第n项的方差。 •

n

<

=

1

0

6

n<=10^6

推导写起来太麻烦GU
k方期望基本推导:
众所周知，第二类斯特林数是自然幂拆成组合数的系数(点我学习):

x

k

=

∑

i

=

0

k

{

k

i

}

x

i

‾

=

∑

i

=

0

k

{

k

i

}

(

x

i

)

⋅

i

!

x^k=\sum^{k}_{i=0}\begin{Bmatrix} k \\ i \end{Bmatrix}x^{\underline{i}}=\sum^{k}_{i=0}\begin{Bmatrix} k \\ i \end{Bmatrix}\binom{x}{i}·i!

UPD:当然，这并不意味着遇到求权值的k次方就要用这个结论。例如在权值由两个确定数字组成的时候，我们可以使用二项式定理直接解决。 我们将它运用到求k次的期望中。 例如之前我们求的

E

[

(

∑

i

x

i

)

3

]

E[(\sum_{i} x_i)^3]

。

E

[

(

∑

i

x

i

)

3

]

=

E

[

∑

i

,

j

x

i

×

x

j

×

x

k

]

=

{

3

3

}

⋅

3

!

∑

i

<

j

<

k

p

i

⋅

p

j

⋅

p

k

+

{

3

2

}

⋅

2

!

∑

i

<

j

p

i

⋅

p

j

+

{

3

1

}

⋅

1

!

∑

i

p

i

\begin{aligned} E[(\sum_{i} x_i)^3]&=E[\sum_{i,j}x_i\times x_j\times x_k]\\ &=\begin{Bmatrix} 3 \\ 3 \end{Bmatrix}·3!\sum_{i<j<k}p_i·p_j·p_k+\begin{Bmatrix} 3 \\ 2 \end{Bmatrix}·2!\sum_{i<j}p_i·p_j+\begin{Bmatrix} 3 \\ 1 \end{Bmatrix}·1!\sum_{i}p_i \end{aligned}

上面这东西不管是从代数意义上或者是从组合意义上都很好理解。
小栗子(好像没什么关系):

6.Small power of subtree You’re given a tree of size

N

N

(

N

≤

1

0

5

N ≤ 10^5

) and an integer

k

k

(

k

≤

10

k ≤ 10

). Find the sum of sizek over all “subtrees”, i.e. connected subgraphs. Print the answer modulo

1

0

9

+

7

10^9 + 7

. 给你一个节点数为

n

n

的树，求所有连通子树的siz的k次方的和

大概是CF1097G的简化版。 设一个连通子树为

T

T

，然后有:

∑

T

s

i

z

e

(

T

)

k

=

∑

T

∑

i

=

0

k

{

k

i

}

(

s

i

z

e

(

T

)

i

)

⋅

i

!

=

∑

i

=

0

k

{

k

i

}

⋅

i

!

∑

T

⋅

(

s

i

z

e

(

T

)

i

)

\begin{aligned} \sum_{T} size(T)^k&=\sum_{T}\sum^{k}_{i=0}\begin{Bmatrix} k \\ i \end{Bmatrix}\binom{size(T)}{i}·i!\\ &=\sum^{k}_{i=0}\begin{Bmatrix} k \\ i \end{Bmatrix}·i!\sum_{T}·\binom{size(T)}{i}\\ \end{aligned}

接下来就是算

∑

T

⋅

(

s

i

z

e

(

T

)

i

)

\sum_{T}·\binom{size(T)}{i}

。 考虑dp。 令

d

p

i

,

j

dp_{i,j}

为以

i

i

为根的连通子树，siz为

j

j

的方案数。 做一个背包即可。 注意做背包的复杂度其实是

O

(

n

k

)

O(nk)

的。
火车题
指hc出的题…

• 无向图的权值为连通块个数的

m

m

次。 • 求所有

n

n

个点有标号图的权值和。 •

n

≤

30000

n\leq 30000

,

m

≤

15

m\leq 15

。

还是之前的套路，我们需要计算连通块选

i

i

个的方案数。 使用无向图含

j

j

个连通块计数的套路:

f

i

=

ln

⁡

G

(

x

)

g

i

,

j

=

∑

k

(

n

k

)

g

k

,

j

−

1

⋅

f

i

−

k

f_i=\ln G(x)\\ g_{i,j}=\sum_{k} \binom{n}{k} g_{k,j-1}·f_{i-k}

选

i

i

个的话就是

∑

k

(

n

k

)

g

k

,

i

⋅

2

n

−

k

i

!

\sum_{k}\binom{n}{k}g_{k,i}·\frac{2^{n-k}}{i!}

。
SRM 686 CyclesNumber
下面出现的结论可以在这里看到。

• 求n个点的置换循环个数m次方的和。 •

n

≤

100000

,

m

≤

500

n\leq 100000, m\leq 500

看到求置换个数首先想到第一类斯特林数。 于是答案就是

∑

i

=

1

n

[

n

i

]

⋅

i

m

\sum^{n}_{i=1} \begin{bmatrix} n \\ i \end{bmatrix}·i^m

。 有一个结论:

[

n

+

1

m

+

1

]

=

∑

i

[

n

i

]

(

i

m

)

\begin{bmatrix} n+1 \\ m+1 \end{bmatrix}=\sum_{i} \begin{bmatrix} n \\ i \end{bmatrix} \binom{i}{m}

。 然后就可以跟之前一样推式子了:

∑

i

=

1

n

[

n

i

]

⋅

i

m

=

∑

i

=

1

n

[

n

i

]

∑

j

=

0

m

{

m

j

}

(

i

j

)

⋅

j

!

=

∑

j

=

0

m

j

!

⋅

{

m

j

}

∑

i

=

1

n

[

n

i

]

(

i

j

)

=

∑

j

=

0

m

j

!

⋅

{

m

j

}

[

n

+

1

j

+

1

]

\begin{aligned} \sum^{n}_{i=1} \begin{bmatrix} n \\ i \end{bmatrix}·i^m &=\sum^{n}_{i=1}\begin{bmatrix} n \\ i \end{bmatrix}\sum^{m}_{j=0}\begin{Bmatrix} m \\ j \end{Bmatrix}\binom{i}{j}·j!\\ &=\sum^{m}_{j=0}j!·\begin{Bmatrix} m \\ j \end{Bmatrix}\sum^{n}_{i=1}\begin{bmatrix} n \\ i \end{bmatrix}\binom{i}{j}\\ &=\sum^{m}_{j=0}j!·\begin{Bmatrix} m \\ j \end{Bmatrix}\begin{bmatrix} n+1 \\ j+1 \end{bmatrix} \end{aligned}

O

(

n

m

)

+

O

(

m

2

)

O(nm)+O(m^2)

预处理两个数计算即可。
展开全文
• 如果说数学期望是对一条曲线整体波动性的描述（用值 X 概率，再相加或积分），那么方差则更深入到这个波动性的内部，提示了波动性产生的原因（也就是偏离程度，用随机变量X的平方数学期望 减去 X的数学期望的...
如题：2019年10月：

分析：由方差的性质，详见4
D(2x+1)=D(2x)+0=4D(x)=10,所以D(x)=2.5,答案选B
在此之前，不知什么是方差。
1、什么是方差呢？

可以说是建立在数学期望基础上的概念，什么是数学期望呢？详见扩展：《关于数学期望由来？？》
从方差的概念中：X-E(x),可以看出是随机变量X的取值偏离E(x)平均程度的值，可能是正，也可能是负，再取平方之后，都是正。可见方差是对数学期望的偏离程度的放大。如果说数学期望是对一条曲线整体波动性的描述（用值 X 概率，再相加或积分），那么方差则更深入到这个波动性的内部，提示了波动性产生的原因（也就是偏离程度，用随机变量X的平方的数学期望  减去    X的数学期望的平方）。
也就是计算方差公式：公式很重要！！！！！！
2、常见离散型随机变量方差：
0-1分布:        D(x)=p(数学期望）   *   （1-p)
二项分布：   D(x)=np                    *     (1-p)
泊松分布：   Ｄ(x)=$\lambda$(与数学期望一样）
3、常见连续型随机变量的方差：
均匀分布：   D(x)=$\frac{(b-a)^{2}}{12}$,区间长度的平方除以12
指数分布：   D(x)=$\frac{1}{\lambda ^{2}}$
正态分布：  D(x)=$\sigma$^2
4、方差的性质：

扩展：
关于数学期望由来？？
整个随机变量的数学特征，数学期望描述的是随机变量取值的平均程度。方差描述的是随机变量的取值偏离其数学期望的偏离程度。相关系数描述的是两个随机变量之间的相互关系，是不是具有线性关系。可见，前两个都是随机变量的取值的特征，也是最先想到的，至于为什么用平均程度来衡量呢？书中提到个词“波动性”就很关键了，这也是其中的原因。
离散型随机变量的数学期望：

为什么离散型随机变量的数学期望是通过不同值乘其对应概率，相加得到的呢？可以从其离散型随机变量图形得到，每个具体的值（在x轴），分别对应一个不同的概率值，相加后自然会得到一个值，对于同一个事物研究这个和，仿佛没有什么意义，但当相同的事物大于2个的时候，和越大，说明这个事物的波动性越大，越不稳定，从而具有现实意义和价值。
需要记忆的常见离散型随机变量的数学期望：
0-1分布：P{X=1},P{X=0}=1-p,EX=1*p+0*(1-p)=p
二项分布：X$\sim$(n,p) ,  EX=np
泊松分布：X$\sim$P($\lambda$),EX=$\lambda$
离散型随机变量的函数的数学期望：由于随机变量X是离散的，那么关于X的函数也是离散的，所以求函数的分布律只需要将X换成X函数的形式就可以了
连续型随机变量的数学期望：

连续型随机变量的数学期望是：没有边界[$-\infty ,+\infty$]的积分，什么含义呢？由连续型随机变量的图形（脑补成一条曲线），x就取全域值[$-\infty ,+\infty$]，f(x)代表这条曲线，积分的话是f(x)在x全域上的值相加，可以看到要知道“波动性”是不是也可以通过个相加的值呢？脑补一下，不同高度的曲线面积。所以连续型随机变量的数学期望就是全域上的积分值。
需要记忆的常见连续型随机变量的数学期望：
均匀分布：EX=$\frac{a+b}{2}$,也就是[a,b]区间的中点。符合数学期望是关于平均程度的描述。
指数分布：EX=$\frac{1}{\lambda }$
正态分布：X$\sim$N($\mu$,$\sigma$^2)EX=$\mu$.
连续型随机变量函数的数学期望：也是将随机变量换成随机变量函数的形式，概率密度不变。

二维随机变量的数学期望：思想与一维是一样的，千万不要记公式，只需要明白原理（参考一维)
离散型：

连续型：

数学期望的性质：

性质1-3总结：线性组合的数学期望等于期望的线性组合

总结：

展开全文
• ## 浅谈数学期望

千次阅读 2019-07-27 19:14:00
数学期望当前在OI中是一个类似于数论方面门槛的知识，在竞赛中有考察。本文将详细的讲解此内容，但也不是只纠缠于简单的概念，而会解决一些题目.可能这样介绍的知识对于大佬来说还是比较基础，但对像我这样的萌新来...

声明：本文严禁转载

0.前言：
数学期望当前在OI中是一个类似于数论方面门槛的知识，在竞赛中有考察。本文将详细的讲解此内容，但也不是只纠缠于简单的概念，而会解决一些题目.可能这样介绍的知识对于大佬来说还是比较基础，但对像我这样的萌新来说通俗易懂，所以请各位大佬不要喷我。

1.什么是期望?
日常生活中，我们每做一件事，都有对它的期望，这里的期望不仅仅只结果的胜负之类，也可以与状态有关。但在OI中，一般指的就是达到结果的期望，最朴素的计算是每次可能结果的概率乘以其结果的总和
这是最基本的数学特征。
广义下的定义：一次随机抽样中所期望的某随机变量的取值。
数学定义：
2.引入：
问题1：
先看一个问题：
甲乙两个正常人赌博，丙作为裁判监督，五局三胜，赢家可以获得100元的奖励。当比赛进行到第四局的时候，甲胜了两局，乙胜了一局，但这时赌场遇到了警察的查封，丙见势不妙，立马逃走了，甲乙两人被迫中止了比赛，那么，如何分配这100元？（每局都能分出胜负）
方案1：
每人50元。
这显然是和平解决问题的方式，此时乙会赞成，但是甲一定有意见，显然，自己已经拿下赛点，不可能心甘情愿的平均分钱。
方案2：
按照获胜的概率分。
假设比赛继续进行，那么下一轮：
50%:甲赢，拿下100元。
50%：乙赢，继续比赛。
但是，如果问题就进行到这里，也就没有接下来的期望了。
当然，如果乙在暗中操纵下赢了，那么再下一轮中，
甲乙两人都有50%的概率获胜，拿下100元。
甲乙：？？这怎么算？

再次观察。
假设甲最终在想象中输了，那么他是在什么概率下输的呢？
$$\frac{1}{2}\times \frac{1}{2}=\frac{1}{4}$$
他实际上只有四分之一的概率输。
显而易见，因为每局都能分出胜负，所以他有$$\frac{3}{4}$$的概率赢掉。
那么情况就简单了，我们根据他们的胜率来分钱。
甲分$$100\times \frac{3}{4}=75$$元
乙分$$100\times \frac{1}{4}=25$$元
此游戏完结~

问题2：
一位公司招募员工，几乎没有什么面试，甲乙两个年轻人就意外的获得了一份工作，这时，面试官却说要给他们发入司奖金，每人需要从各自的三个红包中选择一个。
此时，他们已知红包中有一个1000元的，两个500元的。
两位年轻人各自抽取了一个。
他们刚要打开红包，面试官却制止了他们，随机打开每人剩下红包中的一个，相同的，里面都装着500元钱。
于是面试官向他们询问：如果同意你们用手上的红包换取未打开的红包，你会换吗？

乍一看，这是一个无厘头的问题，可能有些意气风发的人便想到坚持自我等诸多大道理，或者暗自猜测面试官在红包上做了什么标记。
但也有些人想把握机会。
凑巧，甲坚持了原来的选择，乙却尝试了机会。
表面上看，这是一个完全机会均等，拼手气的选择。
但真的是这样吗？
稍加理性分析，我们可以得到一个初步的结论，帮助我们做出选择：
如果员工刚开始恰巧选择了1000元，他不交换会得到1000元，而显然有更大概率他刚开始选到了500元，那么他相应的就只能得到500元了。
由此，选择交换会获得更大的收益。
当然，我们可以不仅仅停留在定向判断。
下面定量计算一下：
设为A，B，C三个红包
当员工选择了A红包后，就将三个红包分为两组，第一组为A红包，第二组为B、C红包。很明显1000元在第一组的概率为$$\frac{1}{3}$$，在第二组的概率为$$\frac{2}{3}$$，而面试官打开了B红包，发现B为500元红包，这里其实是帮助员工在第二组里筛选掉了一个错误答案，所以1000元在C红包的概率其实为$$\frac{2}{3}$$。
所以就要换喽
当然，看到是面试官来做这个实验就知道这还是一个面试环节
于是甲就被炒鱿鱼了

但是，当甲走到门口时，面试官灵机一动，告诉他可以再回答一个问题。
于是甲满怀激动地走了过来。
面试官把向两人踢出提出了下一个问题：
如果给你手上的红包，让你换已经打开的呢？（打开的那个是500元）
显然无论如何都是不换的于是两人完美的成为了同事
面试官因招到了人完美的收到了4000元
3.例题1：
刚才的故事就是数学期望的一个简单应用，两个人都有对自己赢钱的期望（理性分析），便成功的解决了问题。
但是对模型：每次可能结果的概率乘以其结果的总和
的使用却并不是很明显
那么
下面给出一道入门题目，可用以上知识解决：
戳
题意简叙：
一个01串中每个长度为$$X$$的全1子串可贡献$$X^3$$的分数。
给出n次操作的成功率$$p[i]$$，求期望分数。
分析：
我们可以观察到每次对答案的贡献是三次方级别的。
吼啊，我不会三次方期望啊。
仔细观察，首先发现一次方的期望是很好弄的。
于是设$$a[i]$$表示前i位中第i位为1的长度的期望：
则有
$a[i]=(a[i-1]+1)\times p[i]$
tag：即为在i-1的末尾加一个概率为$$p[i]$$出现的1
接着推平方
设$$b[i]$$表示前i位中第i位为1的长度的平方的期望：
则有
$b[i]=(b[i-1]+2\times a[i-1]+1)\times p[i]$
tag:期望的线性延伸：
$x^2->(x+1)^2->x^2+2x+1$
运用这种方法，我们可以在求出$$a[i]$$的基础上推出$$b[i]$$
同理，设$$f[i]$$表示前i位中第i位为1的长度的立方的期望：
则有：
$f[i]=(f[i-1]+3\times b[i-1]+3\times a[i-1]+1)\times p[i]$
哇塞我要A紫题了！！！
然后在满心欢喜的提交上去后发现wa了。

显然，我们还有没考虑到的地方？
是什么呢？
是最后求得的答案与中间过渡式子的不同性。
其实，前三个式子我们都只考虑第i位，这样做是为了递推下面的式子，但是答案让我们求出最终的期望分数，也就是前n位，这时输出f[n]自然就炸了。
所以，只需把三次方递推式稍微变形一下即可；
$f[i]=(f[i-1]+3\times b[i-1]+3\times a[i-1]+1)\times p[i]+f[i-1]\times (1-p[i])=f[i-1]+(3\times b[i-1]+3\times a[i-1]+1)\times p[i]$
这样最终的$$f[n]$$就是答案喽！
code：
//AC记录：https://www.luogu.org/record/21569138
#include<cstdio>
using namespace std;
double a[100005],b[100005],f[100005],p[100005];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf",&p[i]);
a[i]=(a[i-1]+1)*p[i];
b[i]=(b[i-1]+2*a[i-1]+1)*p[i];
f[i]=f[i-1]+(3*b[i-1]+3*a[i-1]+1)*p[i];
}
printf("%.1lf\n",f[n]);
return 0;
}

学好数学期望，递推AC紫题！(其实这应该算dp

4.例题2：
思考题：
tag：这道题笔者并没有找到题目出处，如有发现者，欢迎在评论区留言！
给定一个无向图，每个点可以等概率地走到与它有边的点求从1走到n所需要的期望步数N<=500
分析：
$$F[i]$$表示从i走到n的期望步数$$F[n]=0$$;$$F[i]=aver$${$$f[j]$$}$$+1$$,$$(i,j)$$有边
tag：
天哪上面这张图小的洛谷都水印不上了？？
构成n元一次方程组高斯消元？
5.例题3
https://www.luogu.org/problem/P2911
我怎么开始讲红题了真是trl
题意简叙：
三个骰子，每个面的概率均等，显然，三个面相加能得到一个唯一的数，而得到这个唯一的数却有多种不同的组合方法。
现在你需要求出哪个和出现的概率最大。
解法1：
这题的数据范围很小，直接暴力跑三重循环就行了。
解法2：
这里我闲的没事用了与期望相关的知识来简化了一下。但是这里只是定向的判断一下。
直接计算骰子的期望，得：
$\frac{(a+b+c+3)}{2}$
但是这个想法却有考虑不周的情况，这里留给读者思考。
6.例题4
题目链接：
https://www.luogu.org/problem/UVA10288
题意简叙：
每张彩票上有一个漂亮图案，图案一共n种，如果你集齐了这n种图案就可以召唤神龙兑换大奖。
现在请问，在理想（平均）情况下，你买多少张彩票才能获得大奖的？
$$n\leq33$$
分析：
本题我们设已经有了k个图案
令
$a=\frac{k}{n}$
设拿到一种新的图案需要t次。
则概率为：
$a^{t-1}(1-a)$
则平均需要（已提出了（1-a））:
$(1-a)(1+2a+3a^2+4a^3+5a^4+...)$
即为
$E(1-a)$
而此时我们需要观察其和$$E(a)$$的关系：
$E(a)=a+2a^2+3a^3+4a^4+...=E-1-a-a^2-a^3...$
整理可得
$E(1-a)=1+a+a^2+a^3=\frac{1}{1-a}$
然后代换一下
$E(1-a)=\frac{n}{n-k}$
这样结论就显而易见了：
假设有k个图案在手，那么平均再买$$\frac{n}{n-k}$$ 次就可以再得到一种新的图案，故可得总次数为：
$(\frac{1}{n}+\frac{1}{n-1}+\frac{1}{n-2}+\frac{1}{n-3}+\frac{1}{2}+1)n$
但是这样最后可能会得到一个分数，这就导致输出变得并不是那么方便为自己偷懒找理由
7.期望与均值？
期望与均值是两个十分相近的概念，但又可以说是截然不同。
均值往往是在实验中简单的对数据进行平均。而期望就好像在上帝视角的人。
举个掷骰子的例子：
我们的均值怎么算呢？
显然要掷上一定多的次数来求平均数。
比如，掷了6次，分别为1,5,5,6,3,3，那么均值为
$\frac{1+5+5+6+3+3}{6}=3.8333333...$
居然无限循环小数...看来我是自己出数坑自己
可是期望呢？
我们不用掷骰子就能计算出来：

可以看出，两个值是有明显差别的，而且还时刻不同。
但是为什么容易弄混呢？
因为我太弱了在将多个均值求均值后，两者就无限接近了。
8、期望的小性质：
设X是随机变量，C是常数，则$$E(CX)=C\times E(X)$$
简单证明一下：
设x 的多个随机变量为
$Ca_1,Ca_2,Ca_3$
对应的出现概率为
$p_1,p_2,p_3$
那么对应的求期望的式子
$E(CX)=C(a_1\times p_1 +a_2\times p_2 +a_3\times p_3 )$
(C提出来)
由于：
$E(X)=a_1\times p_1 +a_2\times p_2 +a_3\times p_3$
所以
$E(CX)=C\times E(X)$
下面的可以自行思考，都不难
设X，Y是任意两个随机变量，则有$$E(X+Y)=E(X)+E(Y)$$。设X，Y是相互独立的随机变量，则有$$E(XY)=E(X)\times E(Y)$$。设C为常数，则$$E(C)=C$$。
9、期望的应用
彩票问题

在买彩票中，大多数人相信基本上是没法中奖的，但还是有少数人幻想，于是就再这里简要分析一个彩票问题的期望.

设一张彩票为2元，每售$$1000000$$张开奖，假设中奖号码为$$342356$$，则每张彩票有一个对应的六位数号码，奖次如下：（中奖不叠加）
末位相等,安慰奖：奖励4元，中奖概率0.1%后两位相等,幸运奖：奖励20元，中奖概率0.01%后三位相等,手气奖：奖励200元，中奖概率0.001%后四位相等,一等奖：奖励2000元，中奖概率0.0001%后五位相等,特等奖：奖励20000元，中奖概率0.00001%
某大佬：咦我六位都相等，快给我200000元！！！
彩票公司:你没看你这一项没有吗？你只是特等奖（我是不会告诉你再给钱就亏了
那到底为什么亏了呢
我们来用简单的概率知识来计算一下，对于每一位购买彩票的用户，公司可能支出为：
$0.1\times 4+0.01\times 20+0.001\times 200+0.0001\times 2000+0.00001\times 20000=1.2$
也就是说，公司期望对每个人赚0.8元。
每1000000张，就是800000元！
回到刚才大佬的疑问，显然，如果按照开奖规律继续的话，公司会少赚200000元！！
这显然是一笔不小的损失
彩票公司：我这怎么给员工发工资？！

dalao:

由此可见，彩票公司售卖彩票会让买家有惊现不同的体验（奖次不同），但即使是随机生成彩票号码，卖得多了所支出的钱一定在期望值附近，而能保证稳定的收入，而且彩票单价低，还有可能中那么多奖，买的人多，这样彩票市场才得以持续下去。
10、条件期望
这种期望的求解一般是在有一定条件下的。废话
如下题：
假设你不断扔一个等概率的六面骰子，直到扔出6停止。求在骰子只出现过偶数的条件下扔骰子次数的期望。
分析：
第一眼，我的答案是3
至于如何得出的，在这里就不卖关子了，因为上面的答案是错的！
思考一下，为什么呢？
我们再读一下题：

假设你不断扔一个等概率的六面骰子，直到扔出6停止。求在骰子只出现过偶数的条件下扔骰子次数的期望。
求在骰子只出现过偶数的条件下扔骰子次数的期望。
只出现过偶数的条件
只出现过偶数
只出现
只

抽丝剥茧
细细的考虑一下，题目所说的并不是指出现奇数就pass再扔，而是出现奇数就终止了操作！！！
所以把条件这样转换后，就可以得到正确答案：$$\frac{3}{2}$$ 了
什么？你问怎么得到的？
那我把题意转换一下：

假设你不断扔一个等概率的六面骰子，直到扔出1,3,5，6停止。求骰子最后一次是6次数的期望。

这样再结合前面的知识，大家应该都明白了吧。

这类问题属于数学期望中较有拓展的知识，考察的概率较低，感兴趣者可作为兴趣钻研。其实也不难
n.后记：
期望的定义等少数内容为了精准参考了百度百科即其他大佬的blog等,本文如有错误，欢迎大佬指正

转载于:https://www.cnblogs.com/ShineEternal/p/11256360.html
展开全文
• 前三条是无条件的性质，第四条是需要相互独立 证明 例1 例2 例 正态分布的数学期望证明 例 二项分布的数学期望 例3 例4
 前三条是无条件的性质，第四条是需要相互独立
证明


展开全文
• 数学期望：又叫均值，是一种概率论概念，样本出现的情况结合出现的概率，是一种加权平均。 平均值：是数理统计的概念，对观察样本的统计，所有出现样本的平均值。 而在英语中平均值写作average,均值写作mean，这...
• 数学期望数学期望的性质，方差，标准差，方差的性质，协方差，相关系数，协方差矩阵 数学期望 变量分布的中心 数学期望也叫期望，或者均值，E(X)完全由X的概率分布决定，若X服从某一分布，也成E(X)是该分布的...
• ## 数论小白都能看懂的数学期望讲解

千次阅读 多人点赞 2019-08-15 08:16:00
声明：本文严禁转载 -1....数学期望当前在OI中是一个类似于数论方面门槛的知识，在竞赛中有考察。本文将详细的讲解此内容，但也不是只纠缠于简单的概念，而会解决一些题目.可能这样介绍的知识对于...
• 概率论对于学习 NLP 方向的人，重要性不言而喻。于是我打算从概率论基础篇开始复习，也顺便巩固巩固基础。 这是基础篇的第七篇知识点总结 ...一维随机变量期望与方差 二维随机变量期望与方差 协方差 切比雪夫不等式
• 1、数学期望（先判断是否存在——绝对收敛） 离散型随机变量：分布律（随机变量的取值——对应的概率） 连续型随机变量：先离散化后取极限，利用微积分办法推导 随机变量函数 2、性质 3、方差——...
• 试验中每次可能结果的概率f(x), 或pk 乘以其结果的总和，是最基本的数学特征之一。它反映随机变量平均取值的大小 连续性： 离散型： 或: 3. 协方差： 随机<变量X 和均值的差的平方的均值...
• 数学期望 数学期望其实就是加权平均数。 P(X=Xk)=Pk,如果∑k=1nxkP(Xk)收敛，则E(X)=∑k=1nxkP(Xk)为X的数学期望。P(X = X_k) = P_k, 如果\sum_{k=1}^{n}x_kP(X_k)收敛，则E(X) = \sum_{k=1}^{n}x_kP(X_k)为X的数学...
• 数学期望 以实验中观查实验结果值的算术平均为例，解释数学期望的物理含义： 设共作了N次独立实验，实验结果值为x，x可能有m种值，即 ，在N次实验中各x值得到的次数分别为 ，则有 次，故可求出x的算术...
• 数学期望 在概率论和统计学中，数学期望(mean)（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。它反映随机变量平均取值的大小。 再举个例子理解一下数学期望： &...
• 目录 一、条件数学期望 1. 随机变量的条件数学期望 （1）离散型 （2）连续型 2. 随机变量的函数的条件数学期望 （1）离散型 （2）连续性 3. 性质 二、条件方差 1. 定义 2. 性质 条件密度函数： 条件分布函数： 一、...
• 一 、数学期望（均值）： 在概率论和统计学中，数学期望(mean)（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和。是最基本的数学特征之一。它反映随机变量平均取值的大小。其公式如下： x.....
• 数学期望 ：  1.设X是随机变量，A,B是常数，则E（AX+B）=CE（X）+B 2.设X，Y是任意两个随机变量，则有E（X+Y）=E（X）+E（Y）. 3.设X,Y是相互独立的随机变量，则有E（XY）=E（X）E（Y） 方差：  1、设A是常数...
• 1 期望（数学期望、均值） 在概率论和统计学中，数学期望(mean)（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。它反映随机变量平均取值的大小。 需要注意的是，期望...
• 接下来我们要学习对概率事件进行评判的技术——期望、方差、协方差。 这些概念有什么用呢，举例来说，对于一次期末考试，如何评估同一个年级的不同班级的学生的学习状况差异，如何找出年级最优班级和最差班级呢，...
• ## 数学期望 Expectation

千次阅读 2017-05-28 18:55:33
机器学习中涉及到的很多概念都和 Expectation 相关联，本文对 数学期望展开进行讨论
• 期望与方差 异或：1+0=1，0+1=1，0+0=0，1+1=0。简单记就是相同为0，不同为1。 深层次一些的理解： 不考虑溢出的加法，因为1+1应该等于10，不考虑溢出的1，故结果为0。 异或的特点：奇数个1相加得到1，偶数个1...
• 平方差公式是小学奥数计算中的常用公式。通常写为：a²-b²=(a+b)x(a-b)它的几何方法推导过程是这样的：如下图所示，四边形ABCD和四边形DEFG为正方形，边长分别为a和b，求阴影部分面积。纯手绘显然，阴影部分面积...
• 方差=平方期望-期望平方。 显然只用维护点对的个数和总方案数就行了。 利用分步的思想来统计。 要统计覆盖一个矩形(x1,y1,x2,y2)(x1,y1,x2,y2)(x1,y1,x2,y2)的方案数 只需要统计左上角在矩形(xmin,ymin,x1,y1)(x...
• 期望 1.1 期望的性质 无条件成立 E(kX)=kE(X) E(X+Y)=E(X)+E(Y) 若X和Y互相独立 E(XY)=E(X)E(Y) 反之不成立。实际上，若E(XY)=E(X)E(Y)，只能说明X和Y不相关。 1.2 事件的独立性 1.3 计算期望 1.4计算...
• 所以，求解该变量的幂的数学期望对我们求解该变量的幂的方差十分有帮助。但是，显式地给出所有符合高斯分布的变量的幂的数学期望并不是一件易事，这里我们主要讨论均值为零的高斯分布。一方面均值为零可以避免多项式...
• E(1/h^2)=3E(1/a平方) 超了好几次，最后将我总结的点分享出来 1、尽量少开ll容易超时 2、intll容易爆，llint不用担心 3、做数学题要稳住，别推错了2333 上代码 #define _CRT_SECURE_NO_WARNINGS #include<...
• 文章目录期望（Expected value）意义定义离散型连续型期望与平均值的区别方差（Variance)案例概率论方差统计学方差样本方差python实现代码标准差（Standard Deviation)方差和标准差的区别python实现代码协方差...
• 020 Г函数在正态分布数学期望及方差公式推导的应用；矩估计量、最大似然估计量习题；评价标准之无偏性
• 我们先从数学期望开始。 1、数学期望 概率论是描述现实世界的一个重要学科。我们从现实世界了解数学规律往往是通过一次一次的抽样开始的。我们没做一个事情就会是一次抽样。同样我们也通过做一个事情的经理（也...
• 本文作者：小嗷 微信公众号：aoxiaoji ...方差描述随机变量对于数学期望的偏离程度。（随机变量可以看成随机像素点） 两人的5次测验成绩如下：(X,Y代表2个人，E(X)代表平均分) X： 50，100，100，60，50 E(X)=...

...