前置芝士

鞅：

鞅是一類(lèi)特殊的隨機(jī)過(guò)程，假設(shè)我們從一開(kāi)始就在觀(guān)察一場(chǎng)賭博游戲，現(xiàn)在已經(jīng)得到了前t秒的觀(guān)測(cè)值，那么當(dāng)?shù)趖+1 秒觀(guān)測(cè)值的期望等于第t秒的觀(guān)測(cè)值時(shí)，我們稱(chēng)這是一個(gè)公平賭博游戲。

具體來(lái)說(shuō)，對(duì)于一個(gè)隨機(jī)過(guò)程$A_1,A_2,...$,如果$E(A_{n+1}|A_0,A_2,..A_n)=A_n$,我們稱(chēng)該隨機(jī)過(guò)程為鞅。

鞅的停時(shí)定理：

設(shè)時(shí)停時(shí)間（在不知道隨機(jī)過(guò)程的中間狀態(tài)下停止的時(shí)刻）為t，則$E(t)=E(0)$

這個(gè)E到底是什么，由具體的情境而定，但是只要一個(gè)隨機(jī)過(guò)程是一個(gè)鞅，它就有該結(jié)論

勢(shì)函數(shù)

接下來(lái)我們考慮一個(gè)很常見(jiàn)的問(wèn)題：

對(duì)于一個(gè)隨機(jī)過(guò)程$A_1,A_2,...$,如果其終止?fàn)顟B(tài)$A_t$是確定的，求$E[t]$,即時(shí)停時(shí)刻的期望（注意這里我們不要求該隨機(jī)過(guò)程是一個(gè)鞅）

為此，我們引入一個(gè)勢(shì)函數(shù)$?(X)$

并且$?(x)$滿(mǎn)足如下性質(zhì)：

• $?n<t,E(?(A_{n+1})??(A_n)|A_0,A_1,...A_n)=?1$,即勢(shì)能不斷降低
• $E(?(A_t))=C$,是一個(gè)常值

那么如果我們令$X_t=?(A_t)+t$,則$E(X_{n+1}?X_n|x_0,x_1...x_n)=E(?(A_{n+1})??(A_n)+1|x_0,x_1...x_n)=E(?(A_{n+1})??(A_n)|x_0,x_1...x_n)+1=0$

我們發(fā)現(xiàn)隨機(jī)過(guò)程$X_t$就是一個(gè)鞅了

那么由鞅的停時(shí)原理，$E(X_t)=E(X_0)$,即$E(?(A_t)+t)=E(?(A_0)+0)$,也即$E(?(A_t))+E(t)=E(?(A_0))$

所以我們得到$E(t)=E(?(A_0))?E(?(A_t))$,根據(jù)我們之前定義的性質(zhì)，$E(?)A_t$為一個(gè)常值，而$E(?(A_0))$顯然也是一個(gè)常值，所以只要能找到這個(gè)滿(mǎn)足條件的勢(shì)函數(shù)，就能很方便的求出$E(t)$

這里我們只是在隨機(jī)過(guò)程$X_t$中應(yīng)用了停時(shí)定理，對(duì)原本的隨機(jī)過(guò)程$A_t$并沒(méi)有做什么限制

接下來(lái)結(jié)合具體的題目來(lái)討論一下如何構(gòu)造這樣的一個(gè)勢(shì)函數(shù)

CF1349D

大意：

有n個(gè)人在玩?zhèn)髑蛴螒?#xff0c;一開(kāi)始第$i$個(gè)人有$a_i$個(gè)球。每一次傳球，等概率隨機(jī)選中一個(gè)球，設(shè)其當(dāng)前擁有者為$i$，$i$將這個(gè)球等概率隨機(jī)傳給另一個(gè)人$j(j\ne i)$。當(dāng)某一個(gè)人擁有所有球時(shí)，停止游戲。問(wèn)游戲停止時(shí)的期望傳球次數(shù)。

記球的總數(shù)為m

不妨記狀態(tài)$A_t=(a_{t,1},a_{t,2}...a_{t,n})$,一個(gè)n維向量，分別表示 在時(shí)刻t，第i個(gè)人手中球的數(shù)量，顯然它唯一地表示了某一個(gè)時(shí)刻的全局狀態(tài)

也就是說(shuō)，我們現(xiàn)在就把這個(gè)游戲過(guò)程抽象成了一個(gè)隨機(jī)過(guò)程$A_0,A_1....$,并且其停時(shí)為t。那么按照之前所說(shuō)，我們需要去定義一個(gè)勢(shì)函數(shù)$?(A_t)$,為了計(jì)算方便，我們可以將$?$具體到A的每一維向量，不妨記為$?(A_t)={\sum }_{i=1}^{n}f(a_{t,i})$,這里f是什么我們并不知道，但是如果我們知道了f，其實(shí)也就是相當(dāng)于構(gòu)造出了這個(gè)勢(shì)能函數(shù)

這里再把我們定義的$?$的性質(zhì)再放一下

---

$?(x)$滿(mǎn)足如下性質(zhì)：

• $?n<t,E(?(A_{n+1})??(A_n)|A_0,A_1,...A_n)=?1$,即勢(shì)能不斷降低
• $E(?(A_t))=C$,是一個(gè)常值

---

那么我們首先來(lái)考慮第一個(gè)性質(zhì)，為了方便，不妨先考慮$E(?(A_{n+1})|A_0,A_1,...A_n)$

發(fā)現(xiàn)傳球過(guò)程就是一個(gè)$Markov$過(guò)程，并且該時(shí)刻的狀態(tài)只與上一個(gè)時(shí)刻的狀態(tài)有關(guān),所以$E(?(A_{n+1})|A_0,A_1,...A_n)=E(?(A_{n+1})|A_n)$

考慮一次轉(zhuǎn)移的所有可能

i傳球給j的概率是$\frac{a_{t,i}}{m}\frac{1}{n?1}$

$E(?(A_{n+1})|A_n)={\sum }_{i=1}^n{\sum }_{j\ne i}\frac{a_{t,i}}{m}\frac{1}{n?1}[f(a_{t,i}?1)+f(a_{t,j}+1)+{\sum }_{k\notin (i,j)}f(a_{t,k})]$

$={\sum }_{i=1}^n\frac{a_{t,i}}{m}f(a_{t,i}?1)+\frac{m?a_{t,i}}{m(n?1)}f(a_{t,i}+1)+\frac{(m?a_{t,i})(n?2)}{m(n?1)}f(a_{t,i})$

根據(jù)我們定義的性質(zhì)$E(?(A_{n+1})??(A_n)|A_0,A_1,...A_n)=?1$

$E(?(A_{n+1})??(A_n)|A_0,A_1,...A_n)=E(?(A_{n+1})??(A_n)|A_n)$

$=({\sum }_{i=1}^n\frac{a_{t,i}}{m}f(a_{t,i}?1)+\frac{m?a_{t,i}}{m(n?1)}f(a_{t,i}+1)+\frac{(m?a_{t,i})(n?2)}{m(n?1)}f(a_{t,i}))?\sum f(a_{t,i})=?1$

所以$\sum f(a_{t,i})=({\sum }_{i=1}^n\frac{a_{t,i}}{m}f(a_{t,i}?1)+\frac{m?a_{t,i}}{m(n?1)}f(a_{t,i}+1)+\frac{(m?a_{t,i})(n?2)}{m(n?1)}f(a_{t,i}))+1$

那么我們可以把末尾的1分配到每一個(gè)和式里面去，這樣左右的形式就統(tǒng)一了

所以$\sum f(a_{t,i})={\sum }_{i=1}^n[\frac{a_{t,i}}{m}f(a_{t,i}?1)+\frac{m?a_{t,i}}{m(n?1)}f(a_{t,i}+1)+\frac{(m?a_{t,i})(n?2)}{m(n?1)}f(a_{t,i})+\frac{a_{t,i}}{n}]$

那么不妨記$f(a)=\frac{a}{m}f(a?1)+\frac{m?a}{m(n?1)}f(a+1)+\frac{(m?a)(n?2)}{m(n?1)}f(a)+\frac{a}{n}$

這樣和式還是成立的，我們也成功抽象出了f函數(shù)

再轉(zhuǎn)化一下，$f(a+1)=\frac{m+an?2a}{m?a}f(a)?\frac{a(n?1)}{m?a}(f(a?1)+1)$

代入邊界條件$a=0$時(shí)，有$f(1)=f(0)$,所以我們可以設(shè)$f(1)=f(0)=0$,畢竟勢(shì)函數(shù)的初值并不重要

這樣就得到了f，也就是相當(dāng)于得到了勢(shì)函數(shù)$?(x_t)={\sum }_{i}f(x_{t,i})$

然后考慮勢(shì)函數(shù)的第二個(gè)性質(zhì)：$E(?(A_t))=C$是一個(gè)常值

顯然$E(?(A_t))={\sum }_{i}f(a_{t,i})=f(m)+(n?1)f(0)$是一個(gè)常值

所以根據(jù)我們的結(jié)論，$E(t)=E(?(A_0))?E(?(A_t))={\sum }_{i}f(a_{0,i})?f(m)?(n?1)f(0)={\sum }_{i}f(a_{0,i})?f(m)$

這樣我們就非常方便的得到了停時(shí)的期望

不妨來(lái)看一個(gè)近一點(diǎn)的例子

杭電多校09 Coins

大意：

n個(gè)人，每個(gè)人手中初始有$a_i$個(gè)硬幣，每次隨機(jī)選擇兩個(gè)人，第一個(gè)人給第二個(gè)人一個(gè)硬幣，如果某個(gè)人手中沒(méi)有硬幣了，則立即退出游戲，不再回來(lái)。當(dāng)某一個(gè)人擁有全部硬幣時(shí)，游戲結(jié)束

問(wèn)停時(shí)的期望

題意與上一題十分相像，但是該題存在人數(shù)不固定的情況，所以我們描述游戲局面的時(shí)候要稍微改變一下

還是令$m=\sum a_i$

令$A_t=(a_{t,1},a_{t,2}...a_{t,h_t})$來(lái)描述第t個(gè)時(shí)刻的局面，其中$h_t$表示當(dāng)前的剩余人數(shù)，顯然它不是一個(gè)固定的值。但是我們能保證$?i\le h_t,a_{t,i}>0$

仿照上一題的思路，我們令$?(A_t)={\sum }_{i=1}^{n}f(a_{t,i})$作為勢(shì)函數(shù)，嘗試確定f

$E(?(A_{n+1})|A_n)={\sum }_{i=1}^{h_t}{\sum }_{j\ne i}\frac{1}{h_t(h_t?1)}[f(a_{t,i}?1)+f(a_{t,j}+1)+{\sum }_{k\notin (i,j)}f(a_{t,k})]$

$={\sum }_{i=1}^{h_t}\frac{1}{h_t}f(a_{t,i}?1)+\frac{1}{h_t}f(a_{t,i}+1)+\frac{h_t}{h_t?2}f(a_{t,i})$

代入$E(?(A_{n+1})??(A_n)|A_0,A_1,...A_n)=?1$,也就是$E(?(A_{n+1})??(A_n)|A_n)=?1$(顯然這里當(dāng)前局面也只與上一個(gè)局面有關(guān))，有

${\sum }_{i=1}^{h_t}f(a_{t,i})=[{\sum }_{i=1}^{h_t}\frac{1}{h_t}f(a_{t,i}?1)+\frac{1}{h_t}f(a_{t,i}+1)+\frac{h_t}{h_t?2}f(a_{t,i})]+1$

$={\sum }_{i=1}^{h_t}(\frac{1}{h_t}f(a_{t,i}?1)+\frac{1}{h_t}f(a_{t,i}+1)+\frac{h_t}{h_t?2}f(a_{t,i})+\frac{1}{h_t})$

抽象出$f(a)=\frac{1}{h}f(a?1)+\frac{1}{h}f(a+1)+\frac{h}{h?2}f(a)+\frac{1}{h}$

$f(a+1)?f(a)=f(a)?f(a?1)?1$

令$g(a)=f(a)?f(a?1),有g(a)=g(0)?a$，則$f(a)=f(0)+ag(0)?\frac{a(a+1)}{2}$

取$f(0)=g(0)=0$,則$f(a)=?\frac{a(a+1)}{2}$

所以$E(t)=E(?(A_0))?E(?(A_t))={\sum }_{i=1}^{n}f(a_{0,i})?f(m)$

未完待續(xù)