信息競賽——概率與期望

• 事件
• • 事件的蘊含、包含
  • 事件的互斥
  • 事件的對立
  • 事件的和（并）
  • 事件的積（交）
  • 事件的差
• 概率
• • 事件的獨立性
  • 全概率公式
  • 貝葉斯公式
  • 概率DP（競賽中的考察）
• 期望（競賽中的考察）

前言，溫馨提醒

你得明白自己是信息競賽選手，而非數(shù)學(xué)競賽選手。

并非是專業(yè)性的正確性的講解，因為網(wǎng)上不缺權(quán)威專家的授課。

作為一名普通高中蒟蒻，對我而言，能夠運用做信息競賽題就足夠了。

所以如果不太精準(zhǔn)的表述還請見諒，對于完全錯誤的地方歡迎指出，歡迎大家交流競賽中的概率期望套路。

這樣的形式【這樣的形式】是蒟蒻自己的看法，僅供參考。

跨越知識鏈邏輯的超前學(xué)習(xí)本就會漏洞百出，還請理性看待。

事件

概率論中研究的“事件”，有這樣三層含義：

• 有一個明確界定的試驗（或觀察）
• 這個試驗的全部可能結(jié)果，是在試驗前就明確的
• 有一個明確的陳述，界定了試驗的全部可能結(jié)果中一確定的部分。這個陳述，或者說一確定的部分，就叫做一個事件。

全部結(jié)果即最后的所有情況可能集合，事件指的是其中某一種符合給定要求的情況集合

我個人更喜歡將事件理解為是篩選的條件/要求/限制，從所有可能結(jié)果/情況中選出所有符合這個條件的結(jié)果/情況

i.e. 擲骰子，全部結(jié)果就是骰子朝上點數(shù)的所有情況 $\{1,2,3,4,5,6\}$，隨便一種有特性限制的事件，比如點數(shù)為奇數(shù)，情況就是 $\{1,3,5\}$。

事件的蘊含、包含

事件 $A$ 和事件 $B$，當(dāng) $A$ 發(fā)生的時候 $B$ 一定發(fā)生，則稱 $A$ 蘊含 $B$ 或 $B$ 包含 $A$，記為 $A?B$。

形象來看：

$A$ 發(fā)生 $B$ 必然發(fā)生，所以 $A$ 的所有情況是被 $B$ 所有情況包含的。

若二者相互蘊含，即 $A?B,B?A$ ，則稱兩事件相等，即 $A=B$。

用“事件是實驗的一些結(jié)果”觀點來看，可以理解為符合 $A$ 條件的實驗結(jié)果必在符合 $B$ 條件的實驗結(jié)果中，$A$ 的條件更為苛刻，相比與 $B$ 而言，更難發(fā)生，所以概率就不會超過 $B$ 發(fā)生的概率。

事件的互斥

若 $A,B$ 兩個事件不能同時發(fā)生（可以都不發(fā)生），則稱他們是互斥的。

形象地看：

數(shù)學(xué)化的理解就是兩個集合的交集為空

如果多個事件中任意兩個事件都互斥，則稱這些事件是兩兩互斥的，簡稱互斥的。

構(gòu)成這兩個事件的結(jié)果情況/實驗結(jié)果是不會有交集的

i.e. 擲骰子的點數(shù)為 $3$ 和擲骰子的點數(shù)為 $2$ 的倍數(shù)這兩個事件就是互斥的，因為不能同時發(fā)生。

事件的對立

事件 $A$ 的對立事件 $B=\{A$ 不發(fā)生 $\}$，也記為 $\bar{A}$。

用事件的限制篩選出了符合的情況后，剩余的情況就是這個事件的對立事件集合

形象地看：

紅色區(qū)域是 $A$ 事件，黃色區(qū)域就是其對立事件 $B$。

i.e. 擲骰子點數(shù)為奇數(shù)為事件 $A$，則 $A=\{2,4,6\},\bar{A}=\{1,3,5\}$。

事件的和（并）

事件 $A,B$ 的和為事件 $C=\{A$ 發(fā)生或 $B$ 發(fā)生 $\}$，即 $A,B$ 至少發(fā)生一個。記為 $C=A+B$。

形象地看：

$A$ 藍(lán)點，$B$ 黃圈，$C$ 紅線。

數(shù)學(xué)上的理解為兩個圖形面積的并集

所以兩個事件至少發(fā)生其中之一的概率并不是簡單的概率相加。

i.e. 擲骰子，點數(shù)為偶數(shù)事件 $A$，點數(shù)為質(zhì)數(shù)事件 $B$。

則 $A=\{2,4,6\},B=\{2,3,5\}?C=\{2,3,4,5,6\}$。

加法定理：兩兩互斥的事件之和的概率等于各事件的概率之和。事件個數(shù)可以有限可以無限。

$P(A_1+A_2+...)=P(A_1)+P(A_2)+...$

形象地看：

每個事件都是單獨的完整的不與其他事件相重合的顏色區(qū)域，所有顏色區(qū)域就是這些互斥事件的和。

數(shù)學(xué)化的理解就是所有圖形面積的并

i.e. 擲骰子，點數(shù)為 $1$ 事件 $A_1$，點數(shù)為 $2$ 事件 $A_2$，點數(shù)為 $3$ 事件 $A_3$，三個事件和為 $B$

則 $P(B=\{1,2,3\})=P(A_1=\{1\})+P(A_2=\{2\})+P(A_3=\{3\})=\frac{1}{6}+\frac{1}{6}+\frac{1}{6}=\frac{1}{2}$

推論：$P(\bar{A})=1?P(A)$

在競賽中，有可能 $P(A)$ 并不好求，反而是 $P(\bar{A})$ 好求。

事件的積（交）

事件 $A,B$ 的積為事件 $C=\{A,B$ 同時發(fā)生 $\}$，記為 $C=AB$。

如果兩事件互斥，等于是在說 $AB$ 為不可能事件，即不能同時發(fā)生。

形象地看：

$A$ 藍(lán)點，$B$ 黃圈，$C$ 紅線。

數(shù)學(xué)上的理解為兩個圖形面積的交集

i.e. 擲出點數(shù)為奇數(shù)事件 $A$，點數(shù)為偶數(shù)事件 $B$。

則兩事件積 $C=AB=?$。因為不可能一個點數(shù)又是奇數(shù)又是偶數(shù)。

事件的差

兩個事件 $A,B$ 的差，記為 $A?B$，定義為 $A?B=\{A$ 發(fā)生，$B$ 不發(fā)生 $\}$。

形象地看：

$A?B$ 紅色區(qū)域。

從所有符合A限制的情況中剔除掉同時符合B情況的

顯然，$A?B=A\bar{B}$

$A,\bar{B}$ 都發(fā)生，相當(dāng)于在說 $A$ 發(fā)生，$B$ 不發(fā)生。

由此可見，差可以通過積去定義。

概率

概率可以理解為：一個事件的情況總數(shù)占所有情況總數(shù)的比例，前提是每個情況都是等權(quán)位的，不存在誰優(yōu)誰劣

定義：兩個條件 $A,B,P(B)=0$，則 $P(A|B)=\frac{P(AB)}{P(B)}$。

意思是，在給定條件 $B$ 情況下 $A$ 條件發(fā)生的概率。

條件概率就是這個條件發(fā)生的概率，當(dāng)然是有相對參照物的，競賽中一般都是以全局所有情況為參照空間的，無條件限制

概率 $P(A\cap B)$，即 $A$ 和 $B$ 同時發(fā)生的概率。

也就是說，條件概率 $P(A|B)$ 表示當(dāng)確定 $B$ 發(fā)生時，樣本空間不再是 $\Omega$【全局樣本空間】，而是縮小成 $B$。我們需要計算在樣本空間為 $B$ 時，事件 $A\cap B$ 發(fā)生的概率。

我們在 $B$ 樣本空間中尋找 $A$ 發(fā)生的概率。從上面的圖中看，就是 $A\cap B$ 的面積(概率測度)，除以 $B$ 占據(jù)的面積(概率測度)，也就是我們條件概率的定義。

而定義式中的 $P(A\cap B),P(A),P(B)$ 等都是以 $\Omega$ 為樣本空間的。

【以上都是數(shù)學(xué)規(guī)范化的廢話，壓根沒有必要知道那么精確的定義，自己有個大致感覺就行了】

事件的獨立性

兩事件 $A,B$，$A$ 的無條件概率 $P(A)$ 和給定 $B$ 之下的條件概率 $P(A|B)$，一般是不同的，這反應(yīng)了兩個事件之間的關(guān)聯(lián)。

若 $P(A|B)>P(A)$，則 $B$ 的發(fā)生使得 $A$ 的發(fā)生可能性增大【盡管一個的參照是 $B$ 的樣本空間，一個參照是全局樣本空間】，即 $B$ 的發(fā)生促進了 $A$ 的發(fā)生。

形象地看：

圓內(nèi)區(qū)域表示符合這個事件的情況集合。

除了左圖是促進作用，其余兩張都是抑制作用，右圖更是杜絕這種可能，注意此時是兩個事件隸屬于同一個實驗。

若 $P(A|B)=P(A)$，則 $B$ 的發(fā)生與否對 $A$ 發(fā)生的可能性毫無影響，這在概率論上稱為 $A,B$ 兩事件獨立。

定理：兩獨立事件的積概率等于其各自概率的積，即 $P(AB)=P(A)P(B)$

i.e. 同時拋硬幣和擲骰子，點數(shù)為 $1$ 事件 $A$ ，硬幣正面朝上事件 $B$。顯然兩者不會相互干擾。

形象地看：上面最右邊的圖兩個就是。 因為這個時候兩個事件所屬的實驗都不一樣了。

一般【一般！】都是兩個實驗結(jié)果彼此不影響才會有獨立事件。

乘法定理：若干個獨立事件 $A_1,...,A_n$ 之積的概率，等于各概率之積。

即 $P(A_1{A}_2...A_n)=P(A_1)P(A_2)...P(A_n)$

條件：相加是互斥，相乘是獨立

推論1：獨立事件的任意部分都獨立。

i.e. 事件 $A,B,C,D$ 相互獨立，則 $A,B,C$ 也獨立。

推論2：若一系列事件相互獨立，則將其中一部分事件改為對立事件，仍是相互獨立的。

如果一系列事件任意兩個都獨立，則稱它們兩兩獨立。

定理：相互獨立必然推出兩兩獨立，反過來不一定對。

i.e.：有四個一樣的球，分別寫上數(shù)字 $1,2,3$，第四個球上三個數(shù)字都寫了。

定義事件 $A_i:\{$ 等概率抽一個球，上面有數(shù)字 $i\}$ 。

則 $P(A_1)=P(A_2)=P(A_3)=\frac{1}{2},P(A_1{A}_2)=P(A_1{A}_3)=P(A_2,A_3)=\frac{1}{4}$。

對于任意事件 $A_i,A_j$ 都有 $P(A_i{A}_j)=P(A_i)P(A_j)$，所以 $A_1,A_2,A_3$ 兩兩獨立。

但不相互獨立，因為 $P(A_1)P(A_2)P(A_3)=\frac{1}{8}=P(A_1{A}_2{A}_3)=\frac{1}{4}$。

【因為原樣本空間都不是等權(quán)位的，三個球只有一個數(shù)字，一個球有三個數(shù)字】

【這里只是寫到了，順便寫了，在競賽中是不會有這種數(shù)學(xué)的，所以看不看得懂并不重要】

接下來的東西，就經(jīng)常在競賽中使用了

全概率公式

設(shè) $B_1,B_2,...$ 為有限或無限個事件，兩兩互斥且每次實驗中至少發(fā)生一個。

即 $B_i{B}_j=?(i=j),B_1+B_2+...=\Omega$ （必然事件）

有時把具有這些性質(zhì)的一組事件稱為一個“完備事件群”。

顯然，事件和其對應(yīng)事件是一個“完備事件群”。

現(xiàn)在考慮任一事件 $A$，有 $A=A\Omega =A{B}_1+A{B}_2+...$，因為 $B_1...$ 兩兩互質(zhì)，所以 $A{B}_1,...$ 也兩兩互質(zhì)。

加法定理有，$P(A)=P(A{B}_1)+P(A{B}_2)+...$

由條件概率定義得，$P(A{B}_i)=P(B_i)P(A|B_i)?P(A)=P(B_1)P(A|B_1)+P(B_2)P(A|B_2)+...$

最后的式子即為全概率公式。

“全部”概率 $P(A)$ 被分解成多個部分的和。

一般在競賽中，從另一個角度考察這個式子。把Bi當(dāng)作導(dǎo)致A發(fā)生的一種可能途徑。對不同途徑，A發(fā)生的概率即條件概率P(A|B)各各不同，而采取哪個途徑也是隨機的。類似于加權(quán)平均的感覺。遞推求解類？？

【比如，不同班級的升學(xué)率不同，學(xué)校總升學(xué)率是各班升學(xué)率的加權(quán)平均，其權(quán)和班級人數(shù)成比例】

貝葉斯公式

$$P(A?B)=P(A)?P(B|A)=P(B)?P(A|B)?P(A|B)=\frac{P(B|A)?P(A)}{P(B)}$$

概率DP（競賽中的考察）

概率相較于期望而言，更容易讓人接受和理解。

一般都是順著推就可以了，比如 $d{p}_{i,j}:$ 從起始位置走到 $(i,j)$ 位置的概率，每走一步都有不同的概率，直接概率相乘轉(zhuǎn)移。

初始化，往往是起始點設(shè)為必然事件，概率為 $1$。

輸出最終狀態(tài)即可。

比較簡單，一般是題目怎么說就怎么翻譯，直接轉(zhuǎn)移，至于優(yōu)化就是另一回事了。

較難的有，對于一個狀態(tài) $s$，可能是由若干個狀態(tài) $t_i$ 都可以轉(zhuǎn)移過來的，這中間可能還包括自己。

比如有百分之多少的概率會原地不動。總之，反正你可以列出一個等式。

然后將 $s$ 參與的項放在等式左邊，其余的放右邊，然后把 $s$ 狀態(tài)的結(jié)果當(dāng)成未知數(shù)來計算，將前面的系數(shù)也扔到右邊去。

這個時候如果右邊全是常數(shù)已知項，就可以直接計算。

否則就是出現(xiàn)環(huán)的模型，彼此概率相互影響。

這個時候列出若干個等式，高斯消元即可。

概率除了遞推的形式，還有用符合條件的方案數(shù)占所有方案數(shù)的比例表示，前提是等概率。

期望（競賽中的考察）

隨機變量的期望是其每一個取值以概率為權(quán)重的加權(quán)平均值。

在競賽中這個隨機變量就是最終要求期望的一些限制，類似于事件

【比如最后長度為多少的期望，那么從所有情況中選出最后長度為這么多的情況，再進行期望的相關(guān)計算】

有點所有情況帶來的價值的平均值的感覺，是一種整體性的估價。

【因為以后的事情永遠(yuǎn)都是未知的，期望就相當(dāng)于是提前預(yù)測的手段，對于每一種情況的可能性，其最終的結(jié)果值以及最終發(fā)生這種情況的概率】

期望值：反映一個隨機變量取值的平均值。

即 $E(X)={\sum }_{i\in \Omega }p(i)w(i)$（$p(i),w(i)$ 分別表示情況結(jié)局為 $i$ 的概率及加權(quán)）

【比如最后長度的期望，就是每種可能長度再乘上導(dǎo)致最后結(jié)果為這個長度的概率】

關(guān)于期望的有三個式子：

• $E(\alpha X)=\alpha E(X)$，其中 $\alpha$ 是常數(shù)。
• $E(X+Y)=E(X)+E(Y)$。
• $E(XY)=(EX)(EY)$

別忘了，互斥才能相加，獨立才能相乘。

這種線性性質(zhì)證明的話，根據(jù)期望的定義 $E(x)=\sum p_i{w}_i$ ，顯然可以拆開相加的。

但好像不懂也可以直接來。因為一般競賽中的都是互斥獨立的。

競賽中的期望有兩種。

一種是純數(shù)學(xué)的感覺：

對于次數(shù)，步數(shù)，排名類，這種每次操作會帶來 $1$ 的增長類題目，通常采取遞推，但要注意是順著推還是逆著推。

順推一般定義為從起始態(tài)開始到現(xiàn)在的期望。【已經(jīng)】

逆推一般定義為從現(xiàn)在開始到終止態(tài)的期望。【還差】

但一般會采取逆推的形式，因為我們只對終止態(tài)的期望有所了解，一般都為 $0$。

【比如：求平面棋盤從左上角走到右下角的期望步數(shù)。我們只知道終止態(tài)右下角到右下角的期望步數(shù)是 $0$ 步】

這種一般會用到一個很強的公式：假設(shè)當(dāng)前點到每個后繼點都有對應(yīng)的概率，那么逆推是該點的期望是每個后繼點的期望乘以正著時對應(yīng)轉(zhuǎn)移的概率，求和，再 $+1$。【表示一次操作的代價，當(dāng)然有可能是 $+2$ 什么的】

i.e. $i\to j$ 概率為 $c(j)$，$i\to k$ 概率為 $c(k)$。則逆推時 $E(i)=E(j)?C(j)+E(k)?C(k)+1$。

【還是抓住加權(quán)平均的想法，期望的設(shè)置，就默認(rèn)了加權(quán)平均的分母，將 $C$ 看作情況的概率（新加權(quán)）乘上去，之所以能拆開成所有后繼的貢獻，是因為這個點只能轉(zhuǎn)移到這些后繼點，他們的和是必然事件，后面加的常數(shù)是不管怎么轉(zhuǎn)移都會帶來的貢獻，放在里面也行：$E(i)=(E(j)+1)?C(j)+(E(k)+1)?C(k)$，因為 $C(j)+C(k)=1$，必然事件】

當(dāng)然，如果正著維護出從初始態(tài)開始到每個點的概率，也是可以轉(zhuǎn)移的。

【邊對后一個點的貢獻其實是相當(dāng)于起點到前一個點的概率乘以邊權(quán)，加權(quán)平均】

當(dāng)寫出遞推式子的時候，可以手玩小數(shù)據(jù)跑一下，看看是否與預(yù)想一般轉(zhuǎn)移。

另一種就是利用期望公式：結(jié)果為 $i$ 的概率乘以 $i$ 再求和。

這種就只能尋找工具（數(shù)據(jù)結(jié)構(gòu)？？）看能否快速計算出。

這里可以考慮使用概率的相關(guān)變化，符合結(jié)果條件的情況數(shù)占總方案數(shù)的概率。

或者預(yù)處理概率【比如 $i$ 個中 $j$ 個相關(guān)操作，劈里啪啦一頓】

或者是結(jié)果為 $i$ 的方案數(shù)乘以 $i$ 求和后，再最后除以所有方案數(shù)及其加權(quán)。

或者其余的。。。

多半要用到組合計數(shù)相關(guān)知識了。

【比如：一條路徑長度的期望=所有情況下路徑的長度和/所有路徑情況方案數(shù)，這是由加權(quán)平均值的思想得出的】

再一種就是期望可以分段計算，即為所有單獨小情況的概率之和

當(dāng)然如果出現(xiàn)和概率一樣的環(huán)轉(zhuǎn)移，就要說使用高斯消元了。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的【学习笔记】信息学竞赛中的概率与期望小结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。