由“赛尔号超阴间BOSS”关卡引来的思考，通过马尔可夫链计算通关的期望天数

之前看评论区觉得很难算，先用模拟值跑了一遍。今天受到启发，发现也没那么难算。
首先亮python代码：

import math

import numpy as np

from scipy.special import comb

def transition_probability(current_on, num_toggled):

    """计算给定当前开启的开关数量和操控的开关数量后的转移概率分布"""

    prob_dist = [0] * 10

    # 每种情况下，计算有多少种方式选择开和关的开关

    for k in range(num_toggled + 1):

        num_on = k

        num_off = num_toggled - k

       

        if num_on <= current_on and num_off <= 9 - current_on:

            ways_to_pick_on = comb(current_on, num_on)

            ways_to_pick_off = comb(9 - current_on, num_off)

           

            total_ways = ways_to_pick_on * ways_to_pick_off

           

            prob = total_ways / comb(9, num_toggled)

           

            if current_on - num_on + num_off <= 9:

                prob_dist[current_on - num_on + num_off] += prob

    return prob_dist

def build_matrix():

    matrix = np.zeros((10, 10))

    for current_on in range(10):

        for num_toggled in range(1, 4):

            transitions = transition_probability(current_on, num_toggled)

            matrix[current_on] += transitions

    return matrix / 3  # 除以3是因为我们随机选择操控1到3个开关

matrix = build_matrix()

print(matrix)

# 使用前面得到的转移矩阵

matrix = build_matrix()

def expected_days_to_all_on():

    # 初始化一个9x9的矩阵，对应从0到8个开关打开的状态

    A = np.eye(9) - matrix[:-1, :-1]

   

    # 我们从所有状态要加1天到下一个状态，所以初始化为1

    b = np.ones(9)

   

    # 解Ax = b的方程组来得到期望值

    E = np.linalg.solve(A, b)

   

    # 我们只关心从0个开关打开的状态开始所需的期望天数

    return E[0]

average_days = expected_days_to_all_on()

average_days_required = math.ceil(average_days / 10)

print(f"通关的期望天数：{average_days_required}")

运行结果：
[[0.         0.33333333 0.33333333 0.33333333 0.         0.
  0.         0.         0.         0.        ]
 [0.03703704 0.07407407 0.40740741 0.25925926 0.22222222 0.
  0.         0.         0.         0.        ]
 [0.00925926 0.10185185 0.12962963 0.42592593 0.19444444 0.13888889
  0.         0.         0.         0.        ]
 [0.00396825 0.02777778 0.18253968 0.16666667 0.40079365 0.13888889
  0.07936508 0.         0.         0.        ]
 [0.         0.01587302 0.05555556 0.26719577 0.18518519 0.34391534
  0.09259259 0.03968254 0.         0.        ]
 [0.         0.         0.03968254 0.09259259 0.34391534 0.18518519
  0.26719577 0.05555556 0.01587302 0.        ]
 [0.         0.         0.         0.07936508 0.13888889 0.40079365
  0.16666667 0.18253968 0.02777778 0.00396825]
 [0.         0.         0.         0.         0.13888889 0.19444444
  0.42592593 0.12962963 0.10185185 0.00925926]
 [0.         0.         0.         0.         0.         0.22222222
  0.25925926 0.40740741 0.07407407 0.03703704]
 [0.         0.         0.         0.         0.         0.
  0.33333333 0.33333333 0.33333333 0.        ]]
通关的期望天数：53

思考过程：
以下把翻牌替换成开关

对于这个问题，我们有9个开关，每个开关可以处于两种状态：开或关。因此，总共有2^9=512种可能的配置。

当我们谈论转移矩阵时，我们要考虑从每种配置（当前状态）转移到每种其他配置（下一个状态）的概率。

所以，我们的矩阵有512行和512列：

• 512行：代表所有可能的当前配置。

• 512列：代表从当前配置可能转移到的所有其他配置。

因此，完整的转移矩阵是一个2^9×2^9，也就是512×512的矩阵。

简单地说，矩阵的每一行代表一种可能的初始配置，而该行的每一列则代表从那个初始配置转移到每种其他配置的概率。

换一个思路

如果我们只考虑开关为开的状态的数量，那么我们可以将状态简化为一个从0到9的整数，其中整数表示当前为开的开关的数量。这样，我们只需要一个10×10的转移矩阵，求解出概率就可以计算天数了。

由ChatGPT3.5协作完成，优化思路灵感来源@xzip7775

以上。