一道概率題，塗黑白球？

01-15

有n個白球排成一排。執行以下操作：
在剩餘的白球中等概率選擇一個白球塗黑
直到不存在兩個相鄰的白球。（也就是說任何一個白球左右相鄰的位置要麼是黑球要麼沒有球）
求此時黑球個數的期望。

如評論中 @舒自均提到的，如果在一排白球中求期望，會有很多邊界問題需要處理。不失一般性，我們考慮下面這個問題：

問題：假設有 $n + 1$ 個白球（ $n geq 2$ ），用編號 $1, 2, 3, cdots, n + 1$ 表示。一開始的時候，這 $n + 1$ 個白球排成了一個圓，即 $1 ightarrow 2 ightarrow 3 ightarrow cdots ightarrow n ightarrow n + 1 ightarrow 1$ 。其中， $i ightarrow j$ 表示 $i$ 與 $j$ 相鄰。如果每次我們都隨機地從剩餘白球中挑選一個變成黑色，直到剩餘的白球均不相鄰。問黑球的個數的期望是多少？

在這個問題中，在我們第一次將某個白球變成黑球之後，剩下的 $n$ 個球就相當於變成了一排。因此，這個問題的最終黑球個數的期望等於原問題中最終黑球個數期望加1。我們定義隨機變數 $B$ ，表示結束時黑球的數量；定義隨機變數 $W$ ，表示結束時白球的數量。易知：

$mathbb{E}[W] + mathbb{E}[B] = n + 1$

因此，我們只需要求出 $mathbb{E}[W]$ 即可。下面我們算 $W = k$ 的概率，表示為 $Pr[W = k]$ 。我們另外定義一個隨機變數 $X$ ，表示最後一個被染成黑色的白球的編號。我們有：

$Pr[W = k] = sum_{i=1}^{n+1} Pr[W = k, X = i] = (n + 1) cdot Pr[W = k, X = 1]$

其中第二個等式可以由對稱性得到（我們是在一個圓上）。

下面我們假設 $X = 1$ 。根據 $X$ 的定義，在白球 $1$ 變黑前，球 $2$ 與球 $n + 1$ 中至少有一個是白球。此外，其他白球（除 $1$ ， $2$ 和 $n + 1$ 之外）均兩兩不相鄰。那麼，當球 $1$ 變黑前，只可能有以下三種情況（其他沒顯示的白球均兩兩不相鄰）：

當球 $1$ 變黑後，所有白球均不相鄰，且球 $2$ 和球 $n+1$ 至少一個為白球。滿足這些條件的樣本數量一共有 ${n - k + 1 choose k} - {n - 2 - k + 1 choose k}$ 。這裡， $n - k + 1 choose k$ 是球 $1$ 是黑球的情況下，其他 $n$ 個球中有 $k$ 個不相鄰的白球的數量； $n - 2 - k + 1 choose k$ 是球 $n + 1$ ， $1$ ， $2$ 是黑球的情況下，其他 $n - 2$ 個球中有 $k$ 個不相鄰的白球的數量。這兩個式子相減就是滿足以上條件的樣本的數量。這些樣本中，每個樣本的概率都是一樣的：前面 $n - k$ 次都必須只抽到最終的黑球中除 $1$ 以外的編號；在第 $n - k + 1$ 次抽到編號1。因此，每個的概率均為 $frac{1}{{n + 1 choose n - k}} imes frac{1}{k+1}$ 。其中， $frac{1}{{n + 1 choose n - k}}$ 是先抽到那 $n - k$ 個黑球的概率； $frac{1}{k+1}$ 是在第 $n - k + 1$ 次抽到球 $1$ 的概率。我們最終得到：

$egin{align} Pr[W = k] = (n + 1)cdot Pr[W = k, X = 1] = (n + 1) cdot frac{{n + 1 - kchoose k} - {n - 1 -kchoose k}}{{n + 1 choose n - k} cdot (k + 1)} end{align}$

從而有：

$egin{align} mathbb{E}[W] = -1 +sum_{k=1}^{lfloor(n + 1)/2 floor} Pr[W = k]cdot (k + 1) \ = -1 + (n + 1)cdot sum_{i=1}^{lfloor(n + 1) / 2 floor}frac{{n + 1 - k choose k} - {n - 1 - k choose k}}{{n + 1 choose k + 1}} end{align}$

這個式子目前我不知道能不能進一步化簡成很簡單的形式。對於比較小的 $n$ ，利用這個公式可以得到：（注意原題中的期望為 $mathbb{E}[B] - 1$ ）

當 $n = 2$ ，有 $mathbb{E}[W] = 1$ 和 $mathbb{E}[B] = n + 1 - mathbb{E}[W] = 2$ ；
當 $n=3$ ，有 $mathbb{E}[W] = frac{4}{3}$ 和 $mathbb{E}[B] = 4 - frac{4}{3} = frac{8}{3}$ ；
當 $n = 4$ ，有 $mathbb{E}[W] = frac{3}{2}$ 和 $mathbb{E}[B] = frac{7}{2}$ ；
當 $n = 5$ ，有 $mathbb{E}[W] = frac{17}{10}$ 和 $mathbb{E}[B] = frac{43}{10}$ 。

設 $P(x)$ $(0le xle n)$ 為染了 $x$ 次色後遊戲依然沒有結束的概率，顯然答案為 $sum_{i=0}^{n}P(x)$ ，現在要計算每個 $P(x)$ 。

方便起見，我們去計算染了 $x$ 次色後遊戲已經結束的概率 $E(x)$ ，則 $P(x)=1-E(x)$ 。

在計算 $E(x)$ 時，設 $dp(i,~j,~0/1)$ 表示前 $i$ 個球中放了 $j$ 個球，前 $i$ 個球中不存在兩白球相鄰，並且第 $i$ 個球是白/黑球（ $0$ 表示白， $1$ 表示黑）的放法數量，則

$E(x)=frac{dp(n,~x,~0)+dp(n,~x,~1)}{C_n^x}$

現考慮 $dp$ 的轉移。

$dp(i,~j,~0)=dp(i-1,j,1)$

$dp(i,~j,~1)=dp(i-1,j-1,0)+dp(i-1,j-1,1)$

邊界條件為 $dp(0,0,1)=1$ ， $dp(0,i,j)=0$ $(i e 0或 j e 1)$

時間複雜度 $O(n^2)$ ，我很慚愧，一開始看錯題了

HINT：在 $dp$ 過程中將所有 $dp(i,~j,~k)$ 以 $frac{dp(i,~j,~k)}{C_i^j}$ 存儲可避免高精度計算。

#include & int N; double dp[1001][1001][2], ANS; int main() { scanf("%d", N); dp[0][0][1] = 1; for (int i = 1; i &<= N; i++) { for (int j = 0; j &<= i; j++) dp[i][j][0] = dp[i - 1][j][1] / i * (i - j); for (int j = 1; j &<= i; j++) dp[i][j][1] = (dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1]) / i * j; } for (int i = 0; i &<= N; i++) ANS += 1 - dp[N][i][0] - dp[N][i][1]; printf("%.10lf ", ANS); return 0; }

如 @K-ZhY大神提到，當n不大時情況已經很複雜了，精確求解越來越困難。

但是我發現，如果當N很大時，這個問題能夠精確地與複雜網路中的percolation問題對應起來。

相當於一個網路（這裡網路是由白球組成的一條長鏈），隨機attack其中的節點（塗黑），在攻擊一定數量的節點之後（塗黑小球的平均值），網路崩塌（最大連通集大小=1，即白球沒有相鄰）

關於解這個問題的數學方法在我組一篇文章的SI有講

http://www-levich.engr.ccny.cuny.edu/webpage/hmakse/wp-content/uploads/sites/2/2015/06/nature14604-s1.pdf

由於是長鏈，因此裡面的non-backtracking matrix的形式簡單，直覺告訴我應該可以比較精確地求解。等我有時間再填坑把（x

希望有幫助～～

手機不方便但好像就是個等可能的遞歸問題吧只要算2個白和1個白的情況接下來那之前的數學期望就可以算出來了

幾年級的題目啊

Ew(n)=2/n + (1-2/n) *Ew(n-1) + 2(n-2)/n/(n-1)*Ew(n-2)

其中，n&>=3,Ew(1)=1,Ew(2)=1

E(n)= n - Ew(n)

-------------------我找不到解析解，期待大神關注------------

反其道行之

n個黑球排成一排，

隨機將黑球打白，如果出現兩個相鄰白球就停止。

立即恢復到上一個時刻，就是原問題的終止狀態。

求此時白球個數的期望。預計可以打多少次白炮，不會出現連續的白球。

假設元問題的答案是Eb(n)，這個問題的答案是Ew(n)，易知Eb(n)+Ew(n)=n (n&>=2時才成立）

上圖為第一個球打白時的情況。

下一球，如果落在粗線框範圍內（下簡稱禁區），即上一個白球的旁邊，流程就結束了，最終成績是1。如果不在禁區內，那還有的玩。

第一種情況下，還可以打次白？

0* 1/(n-1) + Ew(n-2) (n-2)/(n-1)

有 1/(n-1)的概率打在禁區內，遊戲結束，成績被鎖定在上一回合，這一炮白打，額外預期是0；

有 (n-2)/(n-1)概率打在禁區外，那麼接下來的打法與連續n-2個黑球是一樣的，預期可以再打Ew(n-2)炮。

第二種情況下，還可以打次白？

0* 2/(n-1) + Ew(n-3)*(n-3)/(n-1)

第三種情況下，還可以打次白？

Ew(1)*1/(n-1)+0* 2/(n-1) +Ew(n-4)*(n-4)/(n-1)

累積起來

Ew(n)=1+ {1/(n-1) *sum{ Ew(1)*1 , Ew(2)*2 , ... ,Ew(n-2)*(n-2) )*2}/n (第一炮每個位置都是1/n的概率,加上第一炮)

Ew(1)=1

Ew(2)=1

Ew(3)=4/3=1+1/3

Ew(4)=1.5=1+1/2

Ew(5)=1/4*(1*1+2*1+3*4/3)*2/5+1=34/20=1+7/10

Ew(6)=1/5*(1*1+2*1+3*4/3+4*1.5)*2/6+1=28/15=1+13/15

Ew(7)=1/6*(1*1+2*1+3*4/3+4*1.5+5*34/20)*2/7+1=1+21.5/21

Ew(8)=1/7*(1*1+2*1+3*4/3+4*1.5+5*34/20+6*28/15)*2/8+1

Ew(9)=1/8*(1*1+2*1+3*4/3+4*1.5+5*34/20+6*28/15+7*42.5/21)*2/9+1

...

為了簡化,令S(n-2)=sum{ Ew(1)*1 , Ew(2)*2 , ... ,Ew(n-2)*(n-2) )*2}

Ew(n)-Ew(n-1)

=S(n-2)*2/n/(n-1) - S(n-3)*2/(n-2)/(n-1)

=- S(n-3)*4/n/(n-1)/(n-2) + Ew(n-2)*(n-2)*2/n/(n-1)

同時有

Ew(n-1)=1+ S(n-3)*2/(n-1)/(n-2)

S(n-3)=(Ew(n-1)-1) *(n-1)/(n-2)/2

Ew(n)-Ew(n-1)

= -(Ew(n-1)-1)*(n-1)*(n-2)/2*4/n/(n-1)/(n-2) + 2(n-2)/n/(n-1)*Ew(n-2)

=-2/n*(Ew(n-1)-1)+2(n-2)/n/(n-1)*Ew(n-2)

Ew(n)=2/n + (1-2/n) *Ew(n-1) + 2(n-2)/n/(n-1)*Ew(n-2)

=2/n+ (n-2)*{ 1/n*Ew(n-1) +2/n/(n-1)*Ew(n-2) }

=2/n+(n-2)/n*{ Ew(n-1)+2/(n-1)*Ew(n-2)}

n*Ew(n)=2+ (n-2)*Ew(n-1)+2*(n-2)/(n-1)*Ew(n-2)

令U(n)=n*Ew(n)

U(n)= 2+ U(n-1)-Ew(n-1)+2/(n-1)* U(n-2)

U(n-1)=(n-1)*Ew(n-1)

Ew(n-1)=U(n-1)/(n-1)

U(n)= 2+ U(n-1)-U(n-1)/(n-1)+2/(n-1)* U(n-2)

= 2+ {(n-2)*U(n-1) +2* U(n-2)}/(n-1)

=2+ (n-2)/(n-1) *U(n-1) + 2/(n-1)* U(n-2)

令D(n)= U(n)-U(n-1)

D(n)=2-U(n-1)/(n-1)+2/(n-1)* U(n-2)

D(n)=2+1/(n-1)*(2*U(n-2)-U(n-1))

D(n)=2+1/(n-1)*(U(n-2)-D(n-1))

(D(n)-2)=1/(n-1)*(U(n-2)-D(n-1))

(D(n)-2)*(n-1)=U(n-2)-D(n-1)

U(n-2)=(D(n)-2)*(n-1)+D(n-1)

U(n)=(D(n+2)-2)*(n+1)+D(n+1)

U(n-1)=(D(n+1)-2)*(n)+D(n)

D(n)=(n+1)*D(n+2)-2*(n+1)+D(n+1)-n*D(n+1)+2n-D(n)

D(n)=(n+1)/2*D(n+2)- (n-1)/2*D(n+1)-1

D(n+2)=2/(n+1)*D(n)+ (n-1)/(n+1)*D(n+1) +2/(n+1)

D(n)= 2/(n-1)*D(n-2)+ (n-3)/(n-1)*D(n-1) +2/(n-1)

令T(n)=D(n)-D(n-1)

T(n)= 2/(n-1)*D(n-2)-2/(n-1)*D(n-1) +2/(n-1)

= 2/(n-1)*(D(n-2)-D(n-1))+2/(n-1)

=-2/(n-1)*T(n-1)+2/(n-1)

=(1-T(n-1))*2/(n-1) （n&>4)

T(n+1)=(1-T(n))*2/n

看到希望了，只有一項迭代了

驗證一下，沒錯

T(4)=0

T(5)=2/4

T(6)=(1-1/2)*2/5=1/5

T(7)=(1-1/5)*2/6=4/15

T(8)=(1-4/15)*2/7=22/105

通項中看來會有n！

Vn=1-（2-2v）*2/n

--------找不到規律啊---------

下圖是前1000項Ew(n)的樣子，估計解析解會是形如 a(n)/b(n）+ ln(c(n)) ，a(n),b(n),c(n)是關於n的多項式。

上圖是Ew(n)第3至20項的增量

上圖是Ew(n)第3至1000項增量的倒數

看起來會是調和級數的變種

============原答案，以下推導是錯誤的，謝謝題主提醒========================

第n個球時，有1/n的概率，第一個黑球在左邊第一個，這樣剩下的就是n-1個白球了，

同樣，有1/n的概率，第一個黑球在左邊第二個，這樣剩下的就是1個和n-2個白球了，

同樣，有1/n的概率，第一個黑球在左邊第三個，這樣剩下的就是2個和n-3個白球了，

以此類推，可以得到n個白球的期望E(n)遞推公式

E(0)=0

E(1)=0

E(2)=1

E(3)=5/3

E(4)=7/3

E(5)=9/3

....

E(n)=1/n*(E(n-1)+1）+1/n*((E(1)+E(n-2)+1）+....+1/n*(E(n-1)+1）

=1+{E(n-1)+E(1)+E(n-2)+E(2)+E(n-3)+E(3)+....+E(i)+E(n-i-1)+....+E(n-1)+E(0)}/n

=1+sum(E(0),E(1),E(2),...,E(n-1))*2/n

不知道對不對，反正我是搞不定了

當操作完全後，白球最多時，應該是白黑白黑白黑～～～～白黑白連續n

個。其它的情況有很多種白黑黑白黑白黑黑黑白黑黑白黑黑黑黑黑白～～～～不可記的。