25个方块着色连通分量期望：理论与Python模拟结果不符问题排查

问题背景 #

现有25个相邻无色方块，每个独立以3/4概率染黑、1/4概率染白。连通分量指同色相邻方块的最大序列，例如BBWBWWWBBW有6个连通分量。需要求该序列中连通分量的期望数量。

用户自行推导结果为10，公式逻辑为(24种变化可能)*2*(3/4)*(1/4) + 1 =10，且其他来源结果也为10，但使用Python代码模拟后得到约13的结果。

原代码内容 #

RUNS = 100000

sums = 0
for j in range(RUNS):
    x = []
    for i in range(25):
        x.append(randint(0,1))
    s = 1
    for i in range(1,25):
        if x[i] != x[i-1]:
            s += 1
    sums += s

print(sums/RUNS)

错误分析 #

代码核心错误 #

代码的问题在于颜色生成的概率不符合题目要求：randint(0,1)生成的是等概率的0和1（各1/2概率），但题目明确要求3/4概率染黑、1/4概率染白。

当颜色等概率时，相邻方块颜色不同的概率为(1/2)*(1/2)+(1/2)*(1/2)=1/2，24个相邻对的期望变化次数是24*(1/2)=12，连通分量期望就是1+12=13，这和代码运行结果完全匹配。

推导的正确逻辑 #

用户的推导核心逻辑是对的（利用期望线性性），只是公式写法存在排版笔误。正确推导过程：

• 设连通分量总数为X，则X = 1 + Y，其中Y是相邻方块颜色不同的次数（每出现一次颜色变化，连通分量数+1）
• 每个相邻对颜色不同的概率为：P(黑→白)+P(白→黑) = (3/4)*(1/4)+(1/4)*(3/4) = 3/8
• 24个相邻对的期望变化次数E[Y] = 24*(3/8)=9
• 因此连通分量的期望E[X] =1+9=10，该结果正确。

修正后的模拟代码 #

调整颜色生成逻辑以符合题目概率，使用random.choices指定权重：

import random

RUNS = 100000

sums = 0
for j in range(RUNS):
    # 0代表黑（3/4概率），1代表白（1/4概率）
    x = random.choices([0,1], weights=[3,1], k=25)
    s = 1
    for i in range(1,25):
        if x[i] != x[i-1]:
            s += 1
    sums += s

print(sums/RUNS)

运行这段代码会得到接近10的结果。

内容的提问来源于stack exchange，提问作者Leen