Category Archives

15 Articles

OI/数学

概率 & 数学期望

Posted by kal0rona on

目录

  • 概述
  • 概率
    • 概率相关的概念
    • 概率的意义
    • 同时发生的概率
    • 概率的公理 & 命题
    • 条件概率
      • 概念
      • 全概率公式
      • 贝叶斯公式
      • 例题
    • 随机变量
    • 概率在 OI 中的应用
  • 数学期望
    • 数学期望的概念
    • 数学期望的线性性 & 递推
    • 数学期望在 OI 中的应用

OI/数学

数学期望和其线性性质

Posted by kal0rona on

背景

自从NOIp 2018初赛第一次知道有数学期望这个东西起,我就一直很难理解。我一直没有去仔细的了解数学期望,而今天打了一场比赛,被逼着去了解了,现在我来写点东西记录一下这个概念。

概念介绍

\(数学期望\)是一个跟概率相关的概念。他的定义是:

数学期望是一个有限的事件的结果乘上一个事件的概率。

我们可以通过举例子来解释这个概念。比如取一个随机数(1-10之间),那么取到5的数学期望就是\(\frac {1} {2}\)。一般,我们用\(\mathbb{E}\)来表示这个值。

性质介绍

在本篇文章中,我只介绍一个性质。未来如果我学到了一些关于数学期望的新东西,那么我会把这些内容写在这篇文章里的。

数学期望在OI中比较重要的性质就是其线性性。简单来讲,如果有两个事件的数学期望为\(\mathbb{E}(a)\)和\(\mathbb{E}(b)\),那么这两个事件叠加起来就是\(\mathbb{E}(a) + \mathbb{E}(b) = \mathbb{E}(a+b)\)。这个性质在OI中比较重要,一些题目会利用这个性质让解题者使用递推的方式解出答案。接下来我们看一道题目:

例题

链接:T2062:随机数生成器

这道题目是我在华南师范大学附属中学举办的比赛中遇到的题目。虽然我这一题并没有AC,但是不妨碍我们来解释数学期望的一些性质和递推得解的方法。

我们来思考这样一个方程,设置\(\mathbb{E}(i)\)为输入为\(i\)的数学期望,那么,根据数学期望的线性性质,我们可以很容易推出以下方程:\[\mathbb{E}(i) =\frac {\mathbb{E}(1) + 1}{i} + \frac {\mathbb{E}(2) + 1}{i} + \frac {\mathbb{E}(3) + 1}{i} + \frac {\mathbb{E}(4) + 1}{i} + \dots + \frac {\mathbb{E}(i) + 1}{i}\]

而在本题中,可知\(\mathbb{E}(1) = 0\)。那么我们来变换一下式子,变成:\[\mathbb{E}(i) = \frac {\mathbb{E}(1) + \mathbb{E}(2) + \dots + \mathbb{E}(i – 1) + i}{n – 1}\]这样我们就可以递推出式子。

数学期望是OI中常见的概念,掌握它很有帮助。建议读者可以自己去阅读相关的资料,我在这里便不再描述。