概率与期望
离散概率
基本定义
概率空间\(\Omega\):在一个给定问题中可能发生的所有情况.
事件:\(\Omega\)的一个子集.
基本事件\(\omega\):\(\Omega\)中的单个元素,也可以看作集合大小为\(1\)的事件.
概率:若\(\omega \in \Omega\),我们称它发生的概率为\(\Pr ( \omega )\),有\(\Pr ( \omega ) \geq 0\)且\(\sum_{ \omega \in \Omega } \Pr ( \omega ) = 1\).
随机变量:在概率空间的基本事件上定义的函数.
联合分布:如果两个随机变量\(X\)和\(Y\)定义在同一个概率空间\(\Omega\)上,对于每一个在\(X\)取值范围内的\(x\)以及在\(Y\)取值范围内的\(y\),我们称\(\Pr ( X = x \land Y = y )\)为它们的联合分布.
独立:如果对于每一个在\(X\)取值范围内的\(x\)以及在\(Y\)取值范围内的\(y\),\(\Pr ( X = x \land Y = y ) = \Pr ( X = x ) \times \Pr ( Y = y )\),我们称\(X\)和\(Y\)是独立的.
期望(均值)\(E X\):我们设概率空间上的随机变量\(X\)的期望\(EX = \sum_{ x \in X ( \Omega ) } x \times \Pr ( X = x ) = \sum_{ w \in \Omega } X ( \omega ) \Pr ( \omega )\).
中位数:我们设概率空间上的随机变量\(X\)的中位数为满足\(\Pr ( X \leq x ) \geq 0 . 5 \land \Pr ( X \geq x ) \geq 0 . 5\)的\(x \in X ( \Omega )\)所组成的集合.
众数:我们设概率空间上的随机变量\(X\)的众数为满足\(\Pr ( X = x ) \geq \Pr ( X = x ' ) , \forall x ' \in X ( \Omega )\)的\(x \in X ( \Omega )\)所组成的集合.
方差\(VX\):我们设概率空间上的随机变量\(X\)的方差\(VX = E ( ( X - EX )^2 )\).
标准差\(\sigma\):我们设概率空间上的随机变量\(X\)的标准差\(\sigma = \sqrt{ VX }\).
期望的简单运算
如果\(X , Y\)是定义在同一个概率空间上的两个随机变量,那么:
\(E ( X + Y ) = EX + EY\).
\(E ( \alpha X ) = \alpha EX\).
如果\(X\)和\(Y\)互相独立,那么\(E ( XY ) = ( EX ) ( EY )\).
上述法则都可以通过期望的定义简单证明.
方差的简单运算
我们考虑方差的定义式:
\[ \begin{aligned} E ( ( X - EX )^2 ) & = E ( X^2 - 2 X ( EX ) + ( EX )^2 ) \\ & = E ( X^2 ) - 2 ( EX ) ( EX ) + ( EX )^2 \\ & = E ( X^2 ) - ( EX )^2 \end{aligned} \]
也即:方差等于随机变量平方的均值减均值的平方.
当\(X\)和\(Y\)为独立的随机变量时,我们有:
\[ \begin{aligned} V ( X + Y ) & = E ( ( X + Y )^2 ) - ( EX + EY )^2 \\ & = E ( ( X + Y )^2 ) - ( EX )^2 - 2 ( EX ) ( EY ) - ( EY )^2 \end{aligned} \]
而又有:
\[ \begin{aligned} E ( ( X + Y )^2 ) & = E ( X^2 + 2 XY + Y^2 ) \\ & = E ( X^2 ) + 2 ( EX ) ( EY ) + E ( Y^2 ) \end{aligned} \]
则:
\[ \begin{aligned} V ( X + Y ) & = E ( X^2 ) + 2 ( EX ) ( EY ) + E ( Y^2 ) - ( EX )^2 - 2 ( EX ) ( EY ) - ( EY )^2 \\ & = VX + VY \end{aligned} \]
即:独立随机变量之和的方差等于它们的方差之和.
接下来,我们可以得到切比雪夫不等式:
\[ \Pr ( ( X - EX )^2 \geq \alpha ) \leq \cfrac{ VX }{ \alpha } , \alpha > 0 \]
证明如下:
\[ \begin{aligned} VX & = \sum_{ \omega \in \Omega } ( X ( \omega ) - EX )^2 \Pr ( \omega ) \\ & \geq \sum_{ \omega \in \Omega } ( X ( \omega ) - EX )^2 \Pr ( \omega ) [ ( X ( \omega ) - EX )^2 \geq \alpha ] \\ & \geq \sum_{ \omega \in \Omega } \alpha \Pr ( \omega ) [ ( X ( \omega ) - EX )^2 \geq \alpha ] \\ & = \alpha \Pr ( ( X - EX )^2 \geq \alpha ) \end{aligned} \]
如果我们用\(c^2 VX\)代替\(\alpha\),我们就有:
\(\Pr ( | X - EX | \geq c \sigma ) \leq \cfrac{ 1 }{ c^2 }\).
简单来说,这个不等式说明:\(X\)落在\(( EX - c \sigma , EX + c \sigma )\)之外的概率至多为\(\cfrac{ 1 }{ c^2 }\).
另外,如果我们取\(n\)个独立的样本\(X_1 , X_2 , . . . , X_n\),令\(S = \sum_{ i = 1 }^n X_i\),那么它的均值是\(nEX\),标准差是\(\sqrt{ n } \sigma\),也就是说,\(\cfrac{ S }{ n }\)落在\(( EX - \cfrac{ c \sigma }{ \sqrt{ n } } , EX + \cfrac{ c \sigma }{ \sqrt{ n } } )\)之外的概率小于等于\(\cfrac{ 1 }{ c^2 }\).
随机抽样调查
如果我们随机取得了\(n\)个值\(X_1 , X_2 , . . . , X_n\),那么我们可以通过这些值来估计概率空间的期望和方差.
\(\hat EX = \cfrac{ \sum_{ i = 1 }^n X_i }{ n }\).
\(\hat VX = \cfrac{ \sum_{ i = 1 }^n X_i^2 }{ n - 1 } - \cfrac{ ( \sum_{ i = 1 }^n X_i )^2 }{ n ( n - 1 ) }\).
这里的\(\hat VX\)似乎与定义不是那么相符.但是它拥有更好的性质:\(E ( \hat VX ) = VX\).
证明如下:
\[ \begin{aligned} E ( \hat VX ) & = \cfrac{ 1 }{ n - 1 } E ( \sum_{ i = 1 }^n X_i^2 - \cfrac{ 1 }{ n } \sum_{ j = 1 }^n \sum_{ k = 1 }^n X_j X_k ) \\ & = \cfrac{ 1 }{ n - 1 } ( \sum_{ i = 1 }^n E ( X_i^2 ) - \cfrac{ 1 }{ n } \sum_{ i = 1 }^n \sum_{ j = 1 }^n E ( X_i X_j ) ) \\ & = \cfrac{ 1 }{ n - 1 } ( \sum_{ i = 1 }^n E ( X^2 ) - \cfrac{ 1 }{ n } \sum_{ i = 1 }^n \sum_{ j = 1 }^n ( ( EX )^2 [ j \ne k ] + E ( X^2 ) [ j = k ] ) ) \\ & = \cfrac{ 1 }{ n - 1 } ( nE ( X^2 ) - \cfrac{ 1 }{ n } ( nE ( X^2 ) + n ( n - 1 ) ( EX )^2 ) ) \\ & = E ( X^2 ) - ( EX )^2 \\ & = VX \end{aligned} \]
条件概率
已知事件B发生时事件A发生的概率为\(P ( A | B ) = \frac{ P ( AB ) }{ P ( B ) } \\\).
贝叶斯公式
贝叶斯公式:如果有\(\{ B_i \}\)是样本空间的一个划分,即\(\forall i , j\),有\(B_i \cap B_j = \emptyset\),并且有\(\bigcup_{ i = 1 }^n B_i = \Omega\).则有\(P ( B_i | A ) = \frac{ P ( AB_i ) }{ P ( A ) } = \frac{ P ( AB_i ) }{ P ( A ) \sum P ( B_j ) } = \frac{ P ( A B_i ) }{ \sum_{ j = 1 }^n P ( A B_j ) } = \frac{ P ( A | B_i ) P ( B_i ) }{ \sum_{ j = 1 }^n P ( A | B_j ) P ( B_j ) } \\\).
简化形式:\(P ( B | A ) = \frac{ P ( A | B ) P ( B ) }{ P ( A ) } \\\).
另外,我们考虑设\(O ( B ) = \cfrac{ P ( B ) }{ P ( \lnot B ) }\),称\(\cfrac{ P ( B | E ) }{ P ( \lnot B | E ) }\)为贝叶斯算子,则同理可得:
\[ O ( B | E ) = O ( B ) \cfrac{ P ( B | E ) }{ P ( \lnot B | E ) } \]
这个公式更加精准地分开了先验概率和后验概率,也表现了贝叶斯算子对先验概率的改变.
概率生成函数
如果\(X\)是定义在概率空间\(\Omega\)上的随机变量,那么它的概率生成函数为\(G_X ( z ) = \sum_{ k \geq 0 } \Pr ( X = k ) z^k = E ( z^X )\).
不难发现\(G_X ( z )\)需要满足的条件:所有系数都非负并且\(G_X ( 1 ) = 1\).
我们发现,当我们定义了概率生成函数后,期望和方差都可以使用它来表示:
\[ \begin{aligned} EX & = G_X ' ( 1 ) \\ E ( X^2 ) & = G ' '_X ( 1 ) + G_X ' ( 1 ) \\ VX & = G_X ' ' ( 1 ) + G_X ' ( 1 ) - ( G_X ' ( 1 ) )^2 \end{aligned} \]
通常,我们也可以将方差和均值的定义扩展到任意函数上,于是我们定义:
\[ \begin{aligned} Mean ( G ) & = G ' ( 1 ) \\ Var ( G ) & = G ' ' ( 1 ) + G ' ( 1 ) - ( G ' ( 1 ) )^2 \end{aligned} \]
不过,求导的过程可能会有些麻烦,但我们可以直接使用泰勒定理:
\[ G ( 1 + t ) = \sum_{ i \geq 0 } \cfrac{ G^{ ( i ) } ( 1 ) }{ i ! } t^i \]
另外,我们不难发现:\(G_{ X + Y } ( z ) = G_X ( z ) G_Y ( z )\).
根据前面的推导,我们有:
\[ \begin{aligned} Mean ( G_{ X + Y } ) & = Mean ( G_X ) + Mean ( G_Y ) \\ Var ( G_{ X + Y } ) & = Var ( G_X ) + Var ( G_Y ) \end{aligned} \]
换句话说,若\(G_X ( 1 ) = 1 , G_Y ( 1 ) = 1\),那么这个式子与直接对\(G_{ X + Y }\)使用求导的那个公式是等价的.注意,这里并没有要求这些生成函数的系数是非负的.
于是我们有了另一个法则:
\[ \begin{aligned} Mean ( G_X ) & = Mean ( G_{ X + Y } ) - Mean ( G_Y ) \\ Var ( G_X ) & = Var ( G_{ X + Y } ) - Var ( G_Y ) \end{aligned} \]
Example1
一枚硬币正面向上的概率为\(p\),反面向上的概率为\(q\),设硬币正面向上为H,反面向上为T,不断抛掷硬币直到抛掷出连续的THTTH为止,求期望次数.
考虑设\(N\)为所有不包含THTTH的硬币序列的生成函数,\(S\)为所有只有结尾为THTTH的硬币序列的生成函数,令\(H = pz , T = qz\),\(1\)为空集,我们显然有:
\[ \begin{aligned} 1 + N \times ( H + T ) & = N + S \\ N \times THTTH & = S + S \times TTH \end{aligned} \]
解方程即可.
另外不难发现,这种方法取决于字符串的所有border,显然是通用方法.
我们考虑扩展这个方法,设\(A\)是我们要找到的字符串,\(m\)是它的长度,令\(A^{ ( k ) }\)表示\(A\)字符串的前\(k\)个字符所组成的字符串,\(A_{ ( k ) }\)表示\(A\)字符串的后\(k\)个字符所组成的字符串.这样的形式与\(k\)阶导的形式可能会起冲突,但至少在接下来我们的式子中不会出现导数(好吧其实是因为《具体数学》上就这么写的我也懒得改了).
我们的方程将会变为:
\[ \begin{aligned} 1 + N ( H + T ) & = N + S \\ N \times A & = S ( \sum_{ k = 0 }^{ m - 1 } A^{ ( k ) } [ A^{ ( m - k ) } = A_{ ( m - k ) } ] ) \end{aligned} \]
如果我们设\(\tilde{ A }\)为将字符串\(A\)中的H替换成\(\cfrac{ 1 }{ p } z\),T替换成\(\cfrac{ 1 }{ q } z\)之后的值,那么显然有:
\[ \begin{aligned} N \times A & = A \times S \times ( \sum_{ k = 1 }^{ m } \tilde{ A }_{ ( k ) } [ A^{ ( k ) } = A_{ ( k ) } ] ) \\ N & = S \times ( \sum_{ k = 1 }^{ m } \tilde{ A }_{ ( k ) } [ A^{ ( k ) } = A_{ ( k ) } ] ) \\ \cfrac{ S - 1 }{ H + T - 1 } & = S \times ( \sum_{ k = 1 }^{ m } \tilde{ A }_{ ( k ) } [ A^{ ( k ) } = A_{ ( k ) } ] ) \\ S \times ( 1 + ( 1 - H - T ) \times ( \sum_{ k = 1 }^{ m } \tilde{ A }_{ ( k ) } [ A^{ ( k ) } & = A_{ ( k ) } ] ) ) = 1 \end{aligned} \]
这显然是一个卷积的形式.
令\(w = \sum_{ k = 1 }^{ m } \tilde{ A }_{ ( k ) } [ A^{ ( k ) } = A_{ ( k ) } ]\).
令\(H ( z ) = 1\),\(F ( z ) = ( 1 + ( 1 - z ) \times w )\),\(G ( z ) = S\).
那么我们显然可以直接求\(G ( z )\)的期望和方差,事实上:
\[ \begin{aligned} EX & = \sum_{ k = 1 }^{ m } \tilde{ A }_{ ( k ) } [ A^{ ( k ) } = A_{ ( k ) } ] \\ VX & = ( EX )^2 - \sum_{ k = 1 }^m ( 2 k - 1 ) \tilde{ A }_{ ( k ) } [ A^{ ( k ) } = A_{ ( k ) } ] \end{aligned} \]
如果硬币是均匀的(\(p = q = \cfrac{ 1 }{ 2 }\))我们引入另一个符号:我们设\(A : A = \sum_{ k = 1 }^m 2^{ k } [ A^{ ( k ) } = A_{ ( k ) } ]\).那么显然期望需要的抛硬币次数就是\(( A : A )\).
Example2(Penney游戏)
一枚均匀硬币,设硬币正面向上为H,反面向上为T.不断扔硬币直到扔出连续的HHT或HTT为止,求最后以HHT结尾的概率.
我们设\(S_A\)为所有以HHT结尾的硬币序列的生成函数,设\(S_B\)为所有以HTT结尾的硬币序列的生成函数.\(N\)为其它的硬币序列的生成函数,令\(H = T = 0 . 5 z\).
我们显然有:
\[ \begin{aligned} 1 + N ( H + T ) & = N + S_A + S_B \\ N \times HHT & = S_A \\ N \times HTT & = S_A \times T + S_B \end{aligned} \]
解方程并带入\(z = 1\),可以有得知以HHT结尾的概率为\(\cfrac{ 2 }{ 3 }\).
事实上,我们使用类似Example1的方法,设这两个硬币序列分别为\(A\)和\(B\),那么可以求出:
\[ \cfrac{ S_A }{ S_B } = \cfrac{ B : B - B : A }{ A : A - A : B } \]
Example3([SDOI2017] 硬币游戏)
是Example2的超级加强版.
把上面的东西给形式化一下,不妨设\(g_i\)表示进行了\(i\)步还未结束的概率,\(f_{ k , i }\)为进行了\(i\)步恰好第\(k\)个人胜利的概率,\(F , G\)是它们的生成函数,我们自然有:
\(1 + xG ( x ) = \sum_k F_k ( x ) + G ( x )\).
\(( \frac{ 1 }{ 2 } x )^L G ( x ) = \sum_{ j = 1 }^n F_j ( x ) \sum_{ i = 0 }^{ L - 1 } ( \frac{ 1 }{ 2 } x )^i [ A_k^{ ( L - i ) } ={ A_j }_{ ( L - i ) } ]\).
第一个式子的用处在于带入\(x = 1\),发现\(\sum_{ k } F_k ( 1 ) = 1\).
把(2)化简一下,有:
\[ \begin{aligned} x^L G ( x ) & = \sum_{ j = 1 }^n F_j ( x ) \sum_{ i = 0 }^{ L - 1 } ( \frac{ 1 }{ 2 } x )^{ i - L } [ A_k^{ ( L - i ) } ={ A_j }_{ ( L - i ) } ] \\ x^L G ( x ) & = \sum_{ j = 1 }^n F_j ( x ) \sum_{ i = 1 }^{ L } ( \frac{ 1 }{ 2 } x )^{ - i } [ A_k^{ ( i ) } ={ A_j }_{ ( i ) } ] \end{aligned} \]
带入\(x = 1\),有:
\[ G ( 1 ) = \sum_{ j = 1 }^n F_j ( 1 ) \sum_{ i = 1 }^{ L } 2^i [ A_k^{ ( i ) } ={ A_j }_{ ( i ) } ] \]
不难发现对于不同的\(k\),(2)的右边不同,而左边一定相同,这样就给出了\(n\)个等式,算上(1)一共有\(n + 1\)个等式,可以算出\(G ( 1 ) , F_{ 1 \cdots n } ( 1 )\)这\(n + 1\)个未知数.
二项式分布
现在有一个大小为\(n + 1\)的概率空间,其中\(\Pr ( \omega_k ) = \binom{ n }{ k } p^k q^{ n - k } \\\),我们把这样的概率序列称为二项式分布.
如果我们令\(H ( z ) = q + pz\),不难发现二项式分布的生成函数为\(H ( z )^n\).
不难发现,满足二项式分布的随机变量的均值是\(np\),方差是\(npq\).
与二项式分布相对应的还有负二项式分布,它的生成函数形如:\(G ( z )^n = ( \cfrac{ p }{ 1 - qz } )^n = \sum_{ k } \binom{ n + k - 1 }{ k } p^n q^k z^k\).
我们考虑如何求\(G ( z )\)的方差和均值,不妨设\(F ( z ) = \cfrac{ 1 - qz }{ p } = \cfrac{ 1 }{ p } - \cfrac{ q }{ p } z\),则\(G ( z )^n = F ( z )^{ - n }\).
不难发现\(F ( z )\)满足二项式分布.也就是说,以\(( n , p , q )\)为参数的负二项式分布也就是以\(( - n , - \cfrac{ q }{ p } , \cfrac{ 1 }{ p } )\)为参数的二项式分布.
模型
树上随机游走
随机游走指每次从相邻的点中随机选一个走过去， 重复这样的过程若干次.
Example1
给一棵所有边长都为\(1\)的\(n\)个点的树,问所有点对\(( i , j ) ( 1 \leq i , j \leq n )\)中,从\(i\)走到\(j\)的期望距离的最大值是多少.
由于树上简单路径唯一,我们考虑设\(f_u\)表示\(u\)随机走到它父亲的期望,\(g_v\)表示\(v\)的父亲(假设是\(u\))走到\(v\)的期望.
对于\(f_u\),我们有:
\[ \begin{aligned} f_u & = \cfrac{ \sum_{ u \rightarrow v } ( f_v + f_u ) }{ \deg_u } + 1 \\ f_u & = \deg_u + \sum_{ u \rightarrow v } f_v \end{aligned} \]
对于\(g_v\),我们有:
\[ \begin{aligned} g_v & = \cfrac{ g_u + g_v + \sum_{ u \rightarrow w , w \ne v } ( g_v + f_w ) }{ \deg_u } + 1 \\ g_v & = g_u + \sum_{ u \rightarrow w , w \ne v } f_w + \deg_u \end{aligned} \]
Example2
给出一棵\(n\)个节点的树,每个点有可能是黑白两种颜色的一种.
现在从\(1\)号点开始随机游走(即走这个点的每条出边的概率是相同的),每到一个点,如果这个点是黑点,或者这是白点并且这个点第一次经过,那么答案\(+ 1\).当走到度数为\(1\)的节点时游走停止.
注意到黑白点对答案的贡献是互相独立的,所以分开讨论:
如果只有黑点,那么显然答案就是路径的期望长度,我们设\(f_u\)表示以\(u\)为起点的路径的期望长度,不难注意到\(f_{ leaf } = 1\)且\(f_u = 1 + \cfrac{ 1 }{ \deg_u } \sum_{ u \rightarrow v \lor v \rightarrow u } f_v\).这个dp转移显然是有后效性的,可以使用高斯消元做,但有一个经典做法:我们求得\(f_u = k_u f_{ fa } + b_u\),然后就可以采取带入化简的方法做了.
如果只有白点,考虑每个点只会贡献一次,所以我们要求出的就是每个点被走到的概率.注意到一个点被走到一定是从它父亲走来的,于是我们需要求出\(g_v\)表示从\(v\)的父亲(假设是\(u\))走到\(v\)的概率,再令\(f_u\)表示从\(u\)走到父亲的概率,类似Example1,我们有:
\[ \begin{aligned} f_u & = \cfrac{ 1 }{ \deg_u } ( 1 + \sum_{ u \rightarrow v } f_v f_u ) \\ g_v & = \cfrac{ 1 }{ \deg_u } ( 1 + g_v g_u + \sum_{ u \rightarrow w , w \ne v } f_w g_v ) \end{aligned} \]
最后把两部分答案合起来就好.
计数与期望的转换
Example(CodeChef Secplayer)
冷静一下,如果我们直接计数的话会发现巨大难做,因为项太多了,直接乘起来也太麻烦了.
这启发我们:当我们注意到一个计数题的各种情况相乘很麻烦的时候,我们不妨只考虑一种情况并计算期望,然后拿期望和总数反推计数.注意到权值最小的人最危险,他不能和其他任何一个人匹配到,不然就死了.那不难求得此时他作为次大值存活的概率为\(\frac{ 1 }{ \binom{ n }{ 2 } }\).
把所有人权值从大到小排序,设\(f_i\)表示只考虑前\(i\)个人的时候的期望,不难发现:\(f_{ i } = \frac{ 1 }{ \binom{ i }{ 2 } } v_i + ( 1 - \frac{ 1 }{ \binom{ i }{ 2 } } ) f_{ i - 1 }\).
一些小技巧
Example1(CF865C)
首先写出转移式子,但是存在后效性.如果我们设\(f_{ i , j }\)表示过了\(i\)关,花费为\(j\)的期望,不难发现所有的\(f\)都需要与\(f_{ 0 , 0 }\)取\(\min\),这咋办?
我们考虑二分这个\(f_{ 0 , 0 }\),做的时候直接取\(\min\),这样最后还会求出一个\(f_{ 0 , 0 }\),比较一下大小然后继续做二分.
等一下,为撒子这样是收敛的呢?
首先,根据这个题,期望肯定是存在的.
我们注意到我们一开始二分的\(f_{ 0 , 0 }\)越大,最后的答案就越大,但是增长的一定会变慢.换句话说,最后的答案关于我们二分的值的关系应该是一个上凸的函数(增长的时候会被取\(\min\)的另一项限制住,但原本应该是没被限制的),于是这个时候得到的答案如果比二分的答案更小,那我们就应该调小一点.
换句话说,当我们二分答案的时候,应该判断函数凸性.wqs二分也是这个道理:二分答案并判断答案是否满足条件.
Example2(猎人杀)
先做一步转化:如果做期望的时候,会有一些操作变得不能做,那我们改为:先随便选,如果选到不合法的操作就跳过,概率和期望都不会变.
offline
Example3(AGC019F)
人类智慧题…
首先注意到策略显然是每次选剩下最多的答案.
我们画一张\(n \times m\)的图(假设\(n \geq m\)),其中格点\(( a , b )\)表示现在还剩\(a\)个Yes,\(b\)个No.我们再把我们的策略用图上的有向边表示.我们先考虑转化为计数问题,那答案显然就是所有从\(( n , m )\)走到\(( 0 , 0 )\)的路径与我们图上有向边的交的大小总和.
然后咧?
我们注意到这张图长得太规律了,换句话说,如果我们把图的左半部分沿着直线\(y = x\)翻折(路径也跟着翻折),注意到对着这张图做仍然是一样的!
所以呢?由于从\(( n , m )\)走到\(( 0 , 0 )\)一定会经过\(n\)条有向边,所以期望贡献一定要加上一个\(n\).而如果我走到了直线\(y = x\)上,那接下来的贡献是\(\frac{ 1 }{ 2 }\).我们只需要枚举一下走到了多少次即可.
一些不等式
Union Bound
即:\(\mathbb{P} [ \bigcup_i X_i ] \leq \sum \mathbb P [ X_i ]\),取等当且仅当所有\(X_i\)互斥.
Markov 不等式
若\(X \geq 0\),则\(\mathbb{P} [ X \geq t \mathbb{ E } [ X ] ] \leq \frac{ 1 }{ t }\).
显然,多的太多的话就会超过\(E\).
Chebyshev 不等式
当\(\sigma(X)>0\)时,有 \[ \mathbb{P}(|X-\mathbb{E}(X)|\geq c\sdot \sigma(X))\leq \frac{1}{c^2} \] 证明的话直接考虑设\(Y=(X-\mathbb E(X))^2\),用Markov不等式得到: \[ \begin{aligned} \mathbb{P}(Y\geq c^2\mathbb E(Y))&\leq \frac{1}{c^2}\\ \mathbb{P}((X-\mathbb E(X))^2\geq c^2\sigma^2(X))&\leq \frac{1}{c^2}\\ \mathbb{P}|(X-\mathbb E(X)|\geq c\sigma(X))&\leq \frac{1}{c^2}\\ \end{aligned} \]
一些分布
泊松分布
取二项分布的极限情况.设此时\(n=\lambda m\),每个东西有\(\frac{1}{m}\)的概率选入,则对于一个固定的常数\(k\),当\(m\to \infty\)的时候,\(P(X=k)=\frac{1}{k!}\lambda^k e^{-\lambda}\),记作\(X\sim \pi(\lambda)\).
欸,虽然我们这里只考虑了\(k\)某种程度上远小于\(m\)的存在,但好在大的部分也不会有什么太大影响,因此: \[ \sum_k P(X=k)=1 \] 原因是\(e^{\lambda}=\sum_k \frac{\lambda^k}{k!}\).
此时来看\(\mathbb E(X)\),留神到无非是上面那个东西转移了一下子,因此\(\mathbb{E}(X)=\lambda\).
来看\(\mathbb{E}(X^2)\),自然有: \[ \begin{aligned} &\sum_k \frac{1}{k!}\lambda^k e^{-\lambda}k^2\\ =&\sum_k \frac{1}{k!}\lambda^k e^{-\lambda}k(k-1)+\sum_k \frac{1}{k!}\lambda^k e^{-\lambda}k\\ =&\lambda^2+\lambda \end{aligned} \] 所以\(\sigma^2(X)=\mathbb{E}(X^2)-(\mathbb E(X))^2=\lambda\).
几何分布
伯努利试验中首次发生结果\(A\)的次数.
显然\(P(X=k)=p(1-p)^{k-1}\),好像没啥可说的…
设\(f(p)=\sum_{k\geq 1}(1-p)^{k-1}\),则\(f(p)=\frac{1}{p}\),\(E(X)=-pf'(p)=\frac{1}{p}\),\(\sigma^2(X)=\frac{1-p}{p^2}\).