期望值
期望值
這個星期惡補了一下期望值，感覺有些題目還是挺靈活的，只要方向正確，基本上都能把公式寫出來。
論文《淺析競賽中一類數學期望問題的解決》
期望值的基本公式
1、如果(X)是一個離散的隨機變量，輸出值為(x_1, x_2, ...) 和輸出值相應的概率為(p_1, p_2, ...)（概率和為 1), 那么期望值(E(X)=sum_i p_ix_i)
2、對于任意隨機變量(X,Y)以及常量(a,b), (E(aX+bY)=aE(X)+bE(Y))
3、檔兩個隨機變量(X,Y)獨立且各自都有一個期望時，有(E(X cap Y)=E(X)E(Y))
problems
聰聰與可可(NOI2005)
題目描述：有一個擁有(n)個點的無向圖，聰聰和可可分別在一個點，可可每個時間單位都會選擇去相鄰的一個點或者不動（概率相等），而聰聰每個時間單位會走到可以縮短他們之間距離的點，如果有多個則選擇編號最小的點，如果這時聰聰和可可不在同一個點，那么聰聰可以再走多一步而不花費時間，聰聰先走，求平均聰聰需要多長時間才能與可可在同一個點。
solution
先預處理出(next[i][j]),表示聰聰在(i), 可可在(j)時，聰聰下一步走哪里，還有每個點的度(d[i])。設(f[i][j])為當聰聰在(i),可可在(j)時的期望時間。則((to[j][k]))表示與(j)相連的第(k)個點。
[nid=next[next[i][j]][j]
]
[f[i][j]=frac{sum_{k=1}^{d[i]} f[nid][to[j][k]]+f[nid][j]}{d[i]+1}+1
]
(f[i][i]=0, f[i][j]=1(if) (nid==j) (or) (next[i][j]==j))
記憶化搜索即可。
Highlander(SGU 385)
題目描述：隨機給出(1)到(n), (n)個數字的一個錯位排列 (a), 對應了一張有向圖(G = (V, E))，其中(V=){(1, 2, …,n)}(, E=){((i, a_i))}。問在最長環上的頂點數的期望值。
solution
首先，這些環都是簡單環且沒有自環。重要的是知道在(m)個數字中取出(k)個數字組成一個環有(frac{A_m^k}{k})種方案，如果有(i)個環長度相同，則需除以(A_i^i)。
設(f[i][j][k])表示錯位排列中(i)個數字已經確定，最長環為(j)， 且有(k)個長度為(j)的環的方案數，為避免重復計算，設定環的長度遞增不下降。
[f[i][j][k]=left{egin{matrix}
frac{A_n^j}{j} (i==j, j>1, k=1)\
f[i-j][j][k-1]*frac{A_{n-i+j}^j}{j}(2 leq j leq i-2, 1 < k < lfloor frac{i}{j} floor)\
sum_{k=2}^{min(j, i-j+1)} g[i-j][k]*frac{A_{n-i+j}^j}{j}(2 leq j leq i-2, k==1)\
0 (else)
end{matrix}ight.
]
[g[i][j]=sum_{k=1}^{lfloor frac{i}{j} floor} f[i][j][k]
]
[ans=frac{sum_{j=2}^{j leq n} sum_{k=1}^{k leq n} j*k*f[n][j][k]}{sum_{j=2}^{j leq n} sum_{k=1}^{k leq n} f[n][j][k]}
]
Red is good (TopCoder SRM420 Div1)
題目描述：有(R)張紅牌和(B)張黑牌， 隨機打亂然后一張一張地翻牌，翻到紅牌得到 1 美元，黑牌則付出 1 美元。可以隨時停止翻牌，在最優策略下平均能得到多少錢。
solution
用(f[i][j])表示剩下(i)張紅牌和(j)張黑牌獲得錢的期望。
[f[i][j]=left{egin{matrix}
max(0, (f[i-1][j]+1)*frac{i}{i+j}+(f[i][j-1]-1)*frac{j}{i+j}) (i>0, j>0)\
f[i-1][j]+1 (i>0, j==0)\
0 (i==0)
end{matrix}ight.
]
(f[R][B])即為所求
收集郵票(bzoj1426)
題目描述：有n種不同的郵票，皮皮想收集所有種類的郵票。唯一的收集方法是到同學凡凡那里購買，每次只能買一張，并且買到的郵票究竟是n種郵票中的哪一種是等概率的，概率均為1/n。但是由于凡凡也很喜歡郵票，所以皮皮購買第k張郵票需要支付k元錢。 現在皮皮手中沒有郵票，皮皮想知道自己得到所有種類的郵票需要花費的錢數目的期望。
solution
設(f[i])表示現有(i)種郵票，期望還要買(f[i])張，(f[n]=0)
(f[i]=f[i]*frac{i}{n}+f[i+1]*frac{n-i}{n}+1)
設(g[i])表示現有(i)種郵票，期望還要(g[i])元，(g[n]=0)
(g[i]=(g[i]+f[i])*frac{i}{n}+(f[i+1]+g[i+1])*frac{n-i}{n}+1)
買一張郵票時已經預支付了后面每張郵票各1元，所以可以看成當前郵票只是1元。(g[0])即為答案。
tribbles(uva11021)
題目描述：一開始有(n)個球，每個球只活1天，在死之前，每個球有(P_i)(最多生(s-1)只)的概率生出(i)個球，問(m)天后全部死亡的概率。
solution
因為每個球都是獨立的，所以只要算出一個球及其后代第(m)天全部死亡的概率(f[m])，答案就是(f[m]^n)
[f[i]=sum_{j=0}^{j<s} P_j * f[i-1]^j
]
(f[i])可理解為剩下(i)天全部死亡的概率，假如生了(j)個球，那么每個球在剩下的(i-1)天全部死亡的概率為(f[i-1])，(j)個球就是(j)次方。
取球游戲(bzoj4204)
題目描述：給出(1)到(n)的標號和(m)個球，每次隨機取一個球，將其標號+1之后放回，如果取出的標號是(n)就置為(1)，求執行(k)次操作之后每種球的期望個數。
solution
設(f[i][j])表示第(i)次操作后，標號為(j)的球的期望個數
(f[i][j]=(1-frac{f[i-1][j]}{m})*f[i-1][j]+frac{f[i-1][j]}{m}*(f[i-1][j]-1)+frac{f[i-1][j-1]}{m})
(=f[i-1][j]-frac{f[i-1][j]}{m}+frac{f[i-1][j-1]}{m})
因為(k)比較大，所以考慮用矩陣乘法，然后發現矩陣是一個循環矩陣，所以矩陣乘法可優化為(O(n^2))
概率充電器(bzoj3566)
題目描述：給出一棵(n)個點的樹，再給出每個點是電源的概率，每條邊導電的概率，問期望有多少個點帶電。
solution
這題求每個點帶電的概率有點麻煩，而求每個點不帶電的概率比較好算。設(f[i])為第(i)個點由它的兒子影響下，不帶電的概率，(g[i])則表示由父親影響。(p_{ij})為(i,j)邊的導電概率，(q_i)為(i)為電源的概率。
[f[i]=prod_{j in son[i]} (1-p_{ij}+p_{ij}f[j])(1-q_i)
]
求(g[i])的時候要求出(i)的父親(fa)不導電的概率，這時要除去(i)對(fa)的影響。設(tmp)為除去(i)后(fa)不導電的概率，
[tmp=frac{f[fa]*g[fa]}{1-p_{ifa}+p_{ifa}*f[i]}
]
[g[i]=tmp+(1-tmp)*(1-p_{ifa})
]
注意判斷(tmp)的分母是否為(0).
以上所講的都是用遞推式來求期望值，如果把這些遞推式看成是一條條方程，在時間允許的條件下，也可以用高斯消元來求答案。
水水的例題
題目描述：給出一張圖，給出每條邊的長度，在一個點走到相鄰的每個點的概率是相等的，問從(1)號點走到(n)號點的期望長度。
solution
如果這時無環有向圖，那么就可以用遞推式的方法來做，問題是這道題是無向有環圖，只有對于每個點列出方程，然后用高斯消元求解。
First Knight(SWERC 2008 Problem B)
題目描述：給出一個(n*m)的矩形棋盤，給出每個格子走到相鄰四個格子分別的概率（每個格子的不同），問從((1, 1))走到((n, m))的期望步數。
solution
貌似方程很容易就可以列出來，但數據范圍是(n,m in [1, 40]).(O(n^3m^3))肯定過不了。但可以對高斯消元進行優化。
首先，讓((1, 1))這一未知數最后消元，這樣就不用回代了。
接著，上圖（取自《淺析競賽中一類數學期望問題的解決方法》ppt）
即與當前未知量有關的方程數只有(m)個，而這(m)的方程涉及的未知量只有(2m+1)個，所以最終的時間復雜度為(O(nm^3))
總結
- 上一篇： SAP Cloud SDK for Ja
- 下一篇： SAP Cloud SDK for Ja