首页 > 其他分享 >【数学】- 概率论

【数学】- 概率论

时间:2023-11-12 19:23:35浏览次数:49  
标签:Pr 概率 期望 times cfrac 数学 概率论 omega

概率论

参考:https://zhuanlan.zhihu.com/p/330669300

简介

被期望坑过无数次了。痛定思痛,决定写一写。OI中期望常可以通过线性递推得到状态转移,所以也有很大一部分期望题因此被冠以 “期望/概率DP” 之称,属于广义的 “动态规划” 范畴。当然,OI中涉及的大多是离散概率,所以连续概率这里一贯不提。

定义

  • 样本空间 \(\Omega\) 是在问题中可能发生的 所有结果
  • 每个 基本事件 \(\omega\in\Omega\) 有一个 概率 \(\Pr(\omega)\)。其中,明显的有 \(\displaystyle\sum_{\omega\in\Omega}Pr(\omega)=1\),譬如掷一次骰子,每个面朝上的概率是 \(\cfrac{1}{6}\)。\(Pr\) 被称作 概率分布,通过它将概率值 \(1\) 分布在了各事件 \(\omega\) 之间。
  • 一个 事件 \(A\) 则是 \(\Omega\) 的子集。我们可以通过组成事件 \(A\) 的基本事件概率之和定义 事件的概率 \(Pr(\omega\in A)=\displaystyle\sum_{\omega\in A}Pr(\omega)\)。
  • 随机变量 \(S(\omega)\) 是在基本事件 \(\omega\) 上定义的 函数 (所以随机变量一定是被定义有一个值的!!)。譬如定义掷两次骰子得到的点数之和为 \(S(\omega)\),那么我们就可以使之等于 \(2\sim12\),并计算对应的概率为所有满足这一条件的基本事件概率之和。

注意:一般只涉及一个概率空间时,\((\omega)\) 通常会被省略。

有了这些定义,我们就可以研究同一概率空间内的两个随机变量 \(X、Y\) 了。首先,对于属于其对应取值范围的基本事件 \(x\in X,y\in Y\),如果有它们的 联合分布 \(Pr(X=x\and Y=y)=Pr(X=x)\cdot Pr(Y=y)\),那么它们就是 独立 的,互不影响。不然,它们的 条件概率 \(Pr(X=x|Y=y)\)(表示 \(Y=y\) 时 \(X=x\) 发生的概率)则被计算为 \(\cfrac {Pr(X=x\and Y=y)} {Pr(Y=y)}\)。

我们最早涉及到的概率论相关知识无疑是均值、中位数、众数。对于样本空间内取出的 一个事件 \(X\)(注意,这里讨论的概念都 被限制在样本内,这也是为什么说后文提到的期望是均值随样本趋于无穷的极限),它们在这里有了严谨的定义:

  • 均值:\(\displaystyle\sum_{x\in X(\Omega)}x\cdot Pr(X=x)\) (\(Pr(X=x)\) 无疑等于 \(\cfrac1 {|X|}\),每个概率都相等,那么提取这一项就是常见的和除以个数的形式了)
  • 中位数:满足 \(Pr(X\le x)\ge \cfrac1{2} \and Pr(X\ge x)\ge\cfrac1 2\) 的集合 \(x\in X(\Omega)\)
  • 众数:满足 \(Pr(X=x)\ge Pr(X=x'),\forall x'\in X(\Omega)\) 的集合 \(x\in X(\Omega)\)

而我们的大主角 —— 期望值 现在终于可以被定义了:对于 随机变量(谨记随机变量是函数,有着一个值!) 的 均值 有的特殊名称和记号,\(EX=\displaystyle\sum_{\omega\in \Omega}X(\omega)Pr(\omega)\)。(是的,期望本质就是均值,这也是为什么我们常常看到“期望是一种加权平均数”一说)

有了期望值,我们又能定义 方差:\(VX=E\big((X-EX)^2\big)\)。这可以度量 \(X\) 的分布的 “分散程度”。当然,方差开根后就得到了保持单位不变的 标准差:\(\sigma=\sqrt{VX}\)。

因为期望值相同的情况下,有的飘忽不定,有的稳如老狗,相信在初中没少做过 “选将” 决策:表现均值相同时,将发挥稳定的选手送上赛场无疑更优。

性质

下面简述一些关于同一概率空间定义的两个随机变量 \(X,Y\) 的期望的性质。

期望的 线性性

  • \(X+Y\) 也是该概率空间的随机变量,那么可以发现其和的平均值等于其平均值的和:\(E(X+Y)=\displaystyle\sum_{\omega\in \Omega}(X(\omega)+Y(\omega))Pr(\omega)=EX+EY\)。
  • 对于常数 \(\alpha\) 有 \(E(\alpha X)=\alpha EX\)。

乘法法则:

  • \(E(XY)=(EX)(EY)\),如果 \(X\) 和 \(Y\) 独立。

正是其线性性与乘法法则的存在才使得其有了被递推得出答案的可能!

对于它们的应用,譬如对于一对由骰子得到的点数 \(S_1,S_2\),我们如何应用以上性质?设有 \(S=S_1+S_2,P=S_1S_2\),那么首先 \(ES_1=ES_2=\cfrac 7 2\),(骰子掷出点数的期望是 \(ES_x=1\times\cfrac 1 6+...+6\times \cfrac 1 6=\cfrac 7 2\) 是一个经典结论)所以 \(ES=ES_1+ES_2=7\)。又有 \(S_1,S_2\) 独立, \(EP=\cfrac 7 2 \times \cfrac 7 2=\cfrac {49} 4\),甚至有 \(E(S+P)=ES+EP=7+\cfrac{49} 4\)。掷两次骰子后求它们点数之和加上点数之积的期望?太酷啦!

例题

  1. [国家集训队] 单选错位

    第 \(i\) 个选择题有 \(a_i\) 个选项,那么把正确答案填涂后错一位时期望答对几题?

每个选择题互相独立,总答对数的期望可以相加每个题答对的期望得到。而只有相邻题目答案相同时才有 \(X=1\)。对于第 \(i\) 题,它与前一题的答案搭配起来有 \(a_i\times a_{i-1}\) 种可能。而填错后仍正确只有 \(\min \{a_i,a_{i-1}\}\) 种可能。所以 \(O(n)\) 求和即可。

  1. 绿豆蛙的归宿

    典,求DAG上从 \(1\) 到 \(n\) 节点的期望路径长度

考虑在反图上转移。很明显 \(f[u]=\sum (f[v]+w(u,v))\times \cfrac 1 {degree[v]}\)。

  1. [SHOI2002] 百事世界杯之旅

    典,一瓶饮料上每个球星出现的概率相同。要求收集满 \(n\) 名球星期望买多少瓶饮料?

考虑倒推。\(f(i)\) 表示拥有 \(i\) 名球星,期望要买的饮料数。那么这时第 \(j\) 次买到新球星的概率是 \((\cfrac i n)^{j-1}\times\cfrac {n-i} n\),\(E=1\times \cfrac{n-i}n+2\times \cfrac i n\times \cfrac{n-i} n+...+j\times(\cfrac i n)^{j-1}\times \cfrac{n-i} n+...\)。

\(f(i+1)=f(i)+E\\=f(i)+1-1\times\cfrac i n+...+j\times (\cfrac i n)^{j-1}-j\times (\cfrac i n)^j+...\\=f(i)+1+\cfrac i n+(\cfrac i n)^2+...\)。其后的无限等比数列求和等于 \(\cfrac n {n-i}\)。所以就得到 \(f(n)=\displaystyle\sum_{i=1}^n\cfrac n {n-i}\)。

拓展:看到的思维题

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

\(S=\displaystyle\sum_{i=0}(\cfrac 1 3)^{i}=\cfrac 3 2\)

\(\displaystyle\sum_{i=1}i\times (\cfrac 1 3)^{i-1}=S+S\times \cfrac 1 3+S\times (\cfrac 1 3)^2+...=S\times \big(1+\cfrac 1 3+(\cfrac 1 3)^2+...\big)=S\times S=\cfrac 9 4\)

标签:Pr,概率,期望,times,cfrac,数学,概率论,omega
From: https://www.cnblogs.com/Arson1st/p/17827608.html

相关文章

  • 组合数学
    组合数学排列组合——插板法:例1:\(n\)个相同的球,放入\(m\)个不同的盒子且不能有空盒存在,方案数是多少?我们考虑使用插板法,一共\(n\)个球,\(n-1\)个间隔,选出\(m-1\)个间隔,就可以将\(n\)个球分成\(m\)组,方案数\(\binom{n-1}{m-1}\)例2:\(n\)个相同的球,放入\(m\)个不......
  • 数学微积分,学习笔记,等价无穷小的证明:(1+x)^a-1 ~ ax
    \(\lim_{x\to0}\frac{\sqrt[n]{1+x}-1}{\frac{x}{n}}=1\)的证明\[\lim_{x\to0}\frac{\sqrt[n]{1+x}-1}{\frac{x}{n}}=\lim_{x\to0}\frac{\left(1+x\right)^{\frac{1}{n}}-1}{\frac{x}{n}}=\lim_{x\to0}\frac{e^{x\frac{1}......
  • C. Serval and Toxel's Arrays 组合数学
    题目链接......
  • 数学
    邱老师的数学。幻方入门先把这个幻方画出来\[x_1\qquadx_2\qquadx_3\]\[x_4\qquadx_5\qquadx_6\]\[x_7\qquadx_8\qquadx_9\]方便起见,下面记\(f(m)=10-m\),记\(dis(n,m)\)为\(x_n,x_m\)在幻方中的距离,比如\(dis(1,2)=1,dis(1,9)=\sqrt{8}=2\sqrt{2}.\)根......
  • 258-各位相加-归根到底是数学
    给定一个非负整数 num,反复将各个位上的数字相加,直到结果为一位数。返回这个结果。 示例1:输入:num=38输出:2解释:各位相加的过程为:38-->3+8-->1111-->1+1-->2由于 2是一位数,所以返回2。classSolution(object):defaddDigits(self,num):......
  • 离散数学 第一章 命题逻辑 1-3命题公式与翻译
    前面已经提到,不包含任何联结词的命题叫做原子命题,至少包含一个联结词的命题称作复合命题。设p和q是任意两个命题,则┓p,p∨q,(p∧q)∨(p→q),p«(q∨┓p)等都是复合命题。若p和q是命题变元,则上述各式均称作命题公式。p和q称作命题公式的分量。必须注意:命题公式是没有真假值的,仅当在一个公式中......
  • 离散数学 第一章 命题逻辑 1-2 联结词
    在自然语言中,常常使用“或”,“与”,“但是”等一些联结词,对于这种联结词的使用,一般没有很严格的定义,因此有时显得不很确切。在数理逻辑中,复合命题是由原子命题与逻辑联结词组合而成,联结词是复合命题中的重要组成部分,为了便于书写和进行推演,必须对联结词作出明确规定并符号化。下面介......
  • 离散数学 第一篇 数理逻辑
    第一篇数理逻辑    逻辑学是一门研究思维形式及思维规律的科学。逻辑规律就是客观事物在人的主观意识中的反映。逻辑学分为辨证逻辑与形式逻辑两种,前者是以辨证法认识论的世界观为基础的逻辑学,而后者主要是对思维的形式结构和规律进行研究的类似于语法的一门工具性学科。......
  • 离散数学蕴含式的问题
    如何理解数理逻辑中的蕴含?P→Q它表示自然语言的“如果…,则…”这种假言判断的,如果P为真命题,Q也为真命题时,P→Q是真命题,当P为真命题,而Q为假命题时,P→Q是一个假命题。比如张三说,“如果明天天不下雨(P),那么他去你家玩(Q)”,如果第二天天不下雨,他去了你家,他说了真话(P→Q为真),如果天不......
  • 离散数学 第一章 命题逻辑 1-1 命题及其表示法
    在数理逻辑中,为了表达概念,陈述理论和规则,常常需要应用语言进行描述,但是日常使用的自然语言进行描述,往往叙述时不够确切,也易产生二义性,因此就需要引入一种目标语言,这种目标语言和一些公式符号,就形成了数理逻辑的形式符号体系。所谓目标语言就是表达判断的一些语言的汇集,而判断就是对......