概率与期望
离散概率
基本定义
概率空间\(\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 }\).我们只需要枚举一下走到了多少次即可.
数据随机下的性质
树
随机树树高为\(\sqrt{ n }\).
点的度数期望为\(\log n\).
数
- 数字的期望因数个数为\(\log V\).
序列
- 随机序列的LIS长度期望为\(O ( \sqrt{ n } )\).
随机化算法的分类
数值概率算法
即通过随机选取元素从而求得在数值上的近似解.较之于传统算法,其运行速度更快,而且随着运行时间的增加,近似解的精度也会提高.在不可能或不必要求出问题的精确解时,可以使用其得到相当满意的近似解,如随机撒点法(近似求难以计算的图形面积).
Monte Carlo算法
总是能在确定的运行时间内出解,但是得到的解有一定概率是错的.通常出错的概率比较小,因此可以通过反复运行算法来得到可以接受的正确率.
求解最优化问题的Monte Carlo算法
事实上,大部分最优化问题都可以转化为判定性问题:也就是判定一个解是否是最优解,因此我们接下来基本都是讨论的求解判定性问题的Monte Carlo算法.
求解判定性问题的Monte Carlo算法
假倾向的Monte Carlo算法:当这类算法的返回值为假的时候,结果一定正确,但返回值为真的时候则有一定概率错误.
真倾向的Monte Carlo算法:当这类算法的返回值为真的时候,结果一定正确,但返回值为假的时候则有一定概率错误.
产生双侧错误的Monte Carlo算法:无论返回值为什么都有概率出错.基本不会使用.
以下讨论的Monte Carlo算法均为产生单侧错误的Monte Carlo算法.
正确率与复杂度
显然,如果我们有一个单词正确率为\(p\),时间复杂度为\(O ( f ( n ) )\)的算法,我们运行其\(k\)次,则正确率为\(1 - ( 1 - p )^k\),时间复杂度为\(O ( kf ( n ) )\).
算法设计思路1
我们来总结一下通常的Monte Carlo算法的设计思路:
设计一个能解决问题的确定性算法
这个算法需要枚举一些元素.
设这个算法的复杂度为\(O ( f ( n ) g ( n ) )\),其中\(f ( n )\)为枚举部分的复杂度,\(g ( n )\)为单词枚举中计算所需的复杂度.大部分情况下应保证\(g ( n )\)不会很大.
向算法引入随机化优化复杂度
随机化寻找元素来降低复杂度.
计算随机化情况下的正确率以及复杂度.
算法设计思路2
设计一个能解决问题的确定性算法
这个算法需要用到一个或多个传入的元素.
这个元素的值不应该依赖于输入数据.
我们可以通过check这个元素来得到与答案有关的信息.
向算法引入随机化优化复杂度
随机这个元素.
计算随机化情况下的正确率以及复杂度
Example
Example 1(Millar-Rabin算法)
略
Example2(CodeChef MSTONE)
平面上有\(n\)个互不重合的点,已知存在不超过\(7\)条直线可以覆盖全部的点,问在平面上作一条直线,最多能覆盖多少个点.\(n \leq 10000\).
考虑一个朴素的暴力:枚举两个点,确定一条直线,然后判断多少个点在这条直线上.但是这样复杂度是\(O ( n^3 )\)的.
考虑加入随机化.我们不妨每次随机两个点,注意到存在七条直线覆盖全部的点,那覆盖点最多的直线覆盖的点数一定不少于\(\lceil \frac{ n }{ 7 } \rceil\)个点.换句话说,我们随机一个点,这个点在这条直线上的概率是\(\frac{ 1 }{ 7 }\),因此随机两个点确定这条直线的概率为\(\frac{ 1 }{ 49 }\).随机\(1000\)次,错误概率为\(1 - ( \frac{ 48 }{ 49 } )^{ 1000 }\),是很小的.
Example3(CF364D Ghd)
给定一个长度为\(n\)的序列,要求找出一个长度大于等于\(\frac{ n }{ 2 }\)的子序列,使这个子序列中所有数的\(\gcd\)最大,求最大的\(\gcd\).\(n \leq 10^6\),\(a_i \leq 10^{ 12 }\).
注意到我们随机一个数,这个数在最终答案中的概率是\(\frac{ 1 }{ 2 }\).我们不妨直接随机这个数,然后枚举它的因子,判断每个因子在序列中的出现次数即可.但是这样单次复杂度\(O ( n \sqrt{ a } )\),好像不太能过.
冷静一下,我们不妨将这\(\sqrt{ a }\)个质因子全都存下来,然后将\(n\)个数也全都存下来,做狄利克雷后缀和即可.不过直接做可能还需要离散化/map,我们考虑先把所有数与我们随机到的那个数取一个\(\gcd\),这样所有数就都是这个数的因子,可以使用大小因子分别编号来实现.
Example4([POI2014]Couriers)
给定长度为\(n\)的序列\(a\),有\(m\)次询问,每次给定一个区间\([ l , r ]\),问\(a [ l , r ]\)中是否存在出现次数严格大于其它所有数出现次数之和的数,如果存在请输出.\(( n , m \leq 500000 , 1 \leq a_i \leq n )\).
先存下来每个位置的数是第几次出现,我们就可以利用二分快速找到一个区间内某个数出现次数.接下来只需要随机化找这个区间内某个数并判断是否满足条件即可.
Example5([NOI2013] 向量内积)
先考虑\(k = 2\)的情况:
首先,我们自然可以枚举一个向量\(A\)并判断它与其它向量的内积,这样复杂度为\(O ( n^2 d )\).
冷静一下,这个过程其实就是一个矩阵乘法的过程:我们设\(A = \begin{bmatrix}\vec{ a_1 } , \vec{ a_2 } , . . . , \vec{ a_n }\end{bmatrix}\),那我们要验证的无非是\(B = AA^T\)中是否存在一个不在主对角线上的元素\(B_{ i , j }\)在\(\mod 2\)意义下为\(0\).
这咋做啊?我们冷静一下,构造一个矩阵\(C\),其中\(C\)的主对角线元素与\(B\)相同,而其他元素全是\(1\).接下来我们要做的无非是找到\(B\)和\(C\)不同的地方.
这咋办呢?我们考虑这么一点:如果\(B = C\),那么对于任意一个\(X_{ m \times n }\)都应该满足\(XB = XC\),取\(m = 1\),我们的问题就转化为:是否能找到一个\(X\),使得\(XB \ne XC\)?这显然可以随机化.计算前者的复杂度为\(O ( nd )\),后者由于\(C\)很特殊,可以在\(O ( n )\)的时间内求出.这样我们就保证了算法复杂度上的合理性.
接下来,我们要证明其正确率上的合理性.这个算法显然是单侧错误的Monte Carlo算法.问题在于正确率:
令\(D = B - C\),若返回相等但实际上不相等,则\(D\)中至少存在一个不为\(0\)的数字,假设\(D_{ i , j } \ne 0\).我们令\(E = X \times D\),那么只有当\(E\)是零向量时才会错误.而\(E_j = \sum_{ k } X_k D_{ k , j }\),不难解得:\(E_i = - \frac{ 1 }{ D_{ i , j } } \sum_{ k \ne i } X_k D_{ k , j }\),也就是说如果\(X\)的其它位置都确定了,那么\(E\)只有一种取值会返回错误.由于\(k\)一共就俩取值,所以正确率至少\(\frac{ 1 }{ 2 }\).
至于找到答案:我们找到一个不为\(0\)的\(E_i\),那么一定存在一组解包含了第\(i\)个向量,只需枚举另一个向量检验就行,复杂度\(O ( nd )\).
\(k = 3\)的话,我们注意到\(\mod 3\)意义下,\(1\)和\(2\)的平方都是\(1\).考虑\(\sum_{ j } B_{ i , j }^2 X_j = \sum_{ j } B_{ i , j } X_j B_{ h , i }^T\),大概做做.
Las Vegas算法(Sherwood算法)
总是能返回正确的结果,但是其运行时间不确定.对于一些平均时间复杂度优秀,但是最坏情况下复杂度较高的确定性算法,通过引入随机函数,尝试减小最坏情况的可能性,以在期望意义下达到优秀的时间复杂度.
算法设计思路
设计一个能解决问题的确定性算法
这个算法需要枚举全排列.
通常,问题问的是要么只是可行解而不是最优解,要么最优方案特别多,总之要保证有用的排列个数不会太少
向算法引入随机化优化复杂度
随机化寻找排列来降低复杂度.
通常证明复杂度和正确率巨大麻烦,这里建议直接实践证明.
Example
快速排序算法
我们试图计算它的期望时间复杂度:
不妨设\(T ( n )\)表示对长度为\(n\)的序列运行快速排序算法所需的期望时间,我们有:
\[ \begin{aligned} T ( 0 ) & = 0 \\ T ( n ) & = n + \frac{ 1 }{ n } \sum_{ i = 0 }^{ n - 1 } ( T_i + T_{ n - i - 1 } ) \end{aligned} \]
做放缩(可能有些地方需要\(+ 1\)或者\(- 1\)或者加取整,但是问题不大,反正是期望):
\[ \begin{aligned} T ( n ) & = n + \frac{ 1 }{ n } \sum_{ i = 0 }^{ n - 1 } ( T_i + T_{ n - i - 1 } ) \\ & = n + \frac{ 2 }{ n } \sum_{ i = \frac{ n }{ 2 } }^{ n - 1 } ( T_i + T_{ n - i - 1 } ) \\ & = n + \frac{ 2 }{ n } \sum_{ i = \frac{ n }{ 2 } }^{ \frac{ 3 n }{ 4 } } ( T ( i ) + T ( n - i - 1 ) ) + \frac{ 2 }{ n } \sum_{ i = \frac{ 3 n }{ 4 } }^{ n } ( T ( i ) + T ( n - i - 1 ) ) \end{aligned} \]
由于\(T ( n ) \geq n\),所以对于\(\frac{ n }{ 2 } \leq i \leq j\),我们显然有:\(T ( i ) + T ( n - i ) \leq T ( j ) + T ( n - j )\).
因此:
\[ \begin{aligned} T ( n ) & \leq n + \frac{ 2 }{ n } \sum_{ i = \frac{ n }{ 2 } }^{ \frac{ 3 n }{ 4 } } ( T ( \frac{ 3 n }{ 4 } ) + T ( \frac{ n }{ 4 } ) ) + \frac{ 2 }{ n } \sum_{ i = \frac{ 3 n }{ 4 } }^{ n } ( T ( n - 1 ) + T ( 0 ) ) \\ & \leq n + \frac{ 1 }{ 2 } ( T ( \frac{ 3 n }{ 4 } ) + T ( \frac{ n }{ 4 } ) + T ( n - 1 ) ) \end{aligned} \]
我们要证明\(\exists c\),\(T ( n ) \leq cn \log n\),考虑使用数学归纳法,则:
\[ \begin{aligned} T ( n ) & \leq n + \frac{ 1 }{ 2 } ( \frac{ 3 cn }{ 4 } \log ( \frac{ 3 n }{ 4 } ) + \frac{ cn }{ 4 } \log ( \frac{ n }{ 4 } ) + c ( n - 1 ) \log ( n - 1 ) ) \\ & \leq n + c ( \frac{ 3 n }{ 8 } \log n - \frac{ 3 n }{ 8 } \log \frac{ 4 }{ 3 } + \frac{ n }{ 8 } \log n - \frac{ n }{ 4 } + \frac{ n }{ 2 } \log n ) \\ & = cn \log n + n ( 1 - \frac{ 3 c }{ 8 } \log ( \frac{ 4 }{ 3 } ) - \frac{ c }{ 4 } ) \end{aligned} \]
于是显然存在,假设成立.
一类由Monte Carlo算法改造而成的算法
对于一类一定有解的构造性问题,假设我们有一个正确率为\(p\),时间复杂度为\(O ( f ( n ) )\)的产生单侧错误的Monte Carlo算法,我们时图将其改造为Las Vegas算法,我们现在想知道它的期望复杂度.
设其期望运行\(k\)次,则:
\[ \begin{aligned} k & = \sum_{ i = 1 }^{ \infty } p ( 1 - p )^{ i - 1 } i \\ ( 1 - p ) k & = \sum_{ i = 1 }^{ \infty } p ( 1 - p )^i i \\ pk & = \sum_{ i = 2 }^{ \infty } p ( 1 - p )^{ i - 1 } = p \sum_{ i = 0 }^{ \infty } ( 1 - p )^i \\ k & = \frac{ 1 }{ p } \end{aligned} \]
则期望复杂度为\(O ( \frac{ f ( n ) }{ p } )\).
Example3(CF329C Graph Reconstruction)
Example4([Petrozavodsk Summer-2015. Moscow IPT Contest B]Game With A Fairy)
首先注意到一个问题:操作能得到的信息太少了,应该是没有什么确定性算法.因此考虑随机化,那就肯定要先将整个序列random_shuffle一下.
然后呢?我们考虑之后随机选取新序列的一个前缀询问,只要有大致的正确性/复杂性估计应该就是很正确的.
这里有一种方式:考虑这个前缀中第一个有宝藏的位置\(x_1\)和第二个位置\(x_2\),显然只要问到\([ x_1 , x_2 )\)是正确的.
考虑因为是随机,所以\(x_1 \times 2 \leq x_2\)的概率应当是不低的(事实上约为\(\frac{ 1 }{ 2 }\)),而此时的\([ x_1 , x_2 )\)中必有一个位置是二的整数幂,因此我们查询一个等比数列:\(1 , 2 , 4 , . . .\).每次random_shuffle后就查一次,就可以得到一个正确性较高的Las Vegas算法.
爬山与模拟退火
爬山
也就是随机一个起始的解,然后走向与其相邻的较大的解.
但是这样会卡在一个局部最优解上而得不到全局最优解.
于是我们就有了模拟退火算法.
模拟退火
简而言之,模拟退火就是以一定的概率跳到随机的不优秀的点,这样就避免卡在了局部最优解上.不妨设我们想找到最大解,如果要最小解那就稍微改改.
下面给出这个概率的公式:
\[ P = \begin{cases} 1 & E_{ t + 1 } > E_t \\ e^{ \frac{ E_{ t + 1 } - E_t }{ T } } & E_{ t + 1 } \leq E_t \end{cases} \]
具体流程是,先设定一个初始温度\(T_0\),降温速度\(k \in ( 0 , 1 )\),以及终止温度\(T_k\),每次操作后让\(T = kT\),直到其小于终止温度.