通过以 p% 的概率抛硬币来打开所有 n 个灯泡所需的预期移动次数？
Expected number of moves needed to turn on all the n bulbs by tossing a baised coin with p% probability?
有n个灯泡。最初，每个灯泡都关闭。在每次移动中，您可以 select 一个随机灯泡（每个灯泡 select 的概率相同）。如果灯泡已经打开，你什么都不做。如果灯泡已关闭，您必须掷硬币。如果它是头，你可以打开灯泡，但如果它是尾巴，灯泡将保持关闭状态。
更无聊的是，这个硬币不是公平的硬币，落尾的几率是p%。
打开所有灯泡所需的预期移动次数是多少？
我想知道它的算法或求解过程，因为这个问题的n是可变的。
天真的方法：Monte-Carlo-Simulation
描述
（您没有提供任何关于您想要哪种解决方案的信息，因此我提出了可能是最简单但仍然强大的方法：模拟）
Monte-Carlo方法允许我们模拟这个stochastic-process并观察需要的步骤数。由于这只是一个嘈杂的估计，我们需要多次这样做。使用无限次运行，此解将收敛到理论解！
代码
这是一些简单的python-based代码：
import random
import matplotlib.pyplot as plt # just for plotting
n = 10
p = 0.7
n_samples = 1000000
def run():
states = [0 for i in range(n)]
steps = 0
while 0 in states:
index = random.randint(0, n-1)
if random.random() < p: # non-fair coin
states[index] = 1
steps += 1
return steps
avg = 0.0
samples = []
for sample in range(n_samples):
steps = run()
avg += steps
samples.append(steps)
print(avg / n_samples)
plt.hist(samples)
plt.show()
代码输出
41.853233
数学方法：吸收马尔可夫链
描述
由于描述 light-bulbs 的 state-change 的概率仅取决于当前状态，因此 Markov-assumption 是有效的，我们可以使用 Markov-Chains 获得所需的平均步数。
因为最终状态将永远 self-loop 并且因为它会在给定无限步数的情况下达到，所以这是一个 吸收马尔可夫链 .
由于所有灯泡都是相同的，因此我们不需要对激活的灯泡的每个组合相互映射的转换进行建模。我们可以将其简化为更简单的形式：0 light-bulbs -> 1 light-bulbs -> ...（当然还有 self-loop）。
discrete-time discrete-state-space 吸收马尔可夫链允许简单而强大的期望值计算。
wikipedia 解释了一些理论。它也是用于以下代码的公式的来源。
代码
再来一些python:
import numpy as np
N = 10
P = 0.7
""" Build transition matrix """
trans_mat = np.zeros((N+1, N+1))
for source_state in range(N):
prob_hitting_next = ((N-source_state) / float(N)) * P
inverse = 1.0 - prob_hitting_next
trans_mat[source_state, source_state] = inverse
trans_mat[source_state, source_state+1] = prob_hitting_next
trans_mat[N, N] = 1.0
""" Will look like this:
[[ 0.3 0.7 0. 0. 0. 0. 0. 0. 0. 0. 0. ]
[ 0. 0.37 0.63 0. 0. 0. 0. 0. 0. 0. 0. ]
[ 0. 0. 0.44 0.56 0. 0. 0. 0. 0. 0. 0. ]
[ 0. 0. 0. 0.51 0.49 0. 0. 0. 0. 0. 0. ]
[ 0. 0. 0. 0. 0.58 0.42 0. 0. 0. 0. 0. ]
[ 0. 0. 0. 0. 0. 0.65 0.35 0. 0. 0. 0. ]
[ 0. 0. 0. 0. 0. 0. 0.72 0.28 0. 0. 0. ]
[ 0. 0. 0. 0. 0. 0. 0. 0.79 0.21 0. 0. ]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0.86 0.14 0. ]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.93 0.07]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. ]]
"""
""" Q: the sub-matrix of trans_mat without
the rows and columns of any absorbing states
N_fund: fundamental matrix
t: expected number of steps before beeing absorved for each start-state
"""
Q_sub = trans_mat[:N, :N]
N_fund = np.linalg.inv(np.eye(N) - Q_sub)
t = np.dot(N_fund, np.ones(N))
print(t)
print(t[0]) # this is the value we want
代码输出
[ 41.84240363 40.4138322 38.82653061 37.04081633
35. 32.61904762 29.76190476 26.19047619 21.42857143 14.28571429]
41.8424036281 # less than 1 second calculation time!
有n个灯泡。最初，每个灯泡都关闭。在每次移动中，您可以 select 一个随机灯泡（每个灯泡 select 的概率相同）。如果灯泡已经打开，你什么都不做。如果灯泡已关闭，您必须掷硬币。如果它是头，你可以打开灯泡，但如果它是尾巴，灯泡将保持关闭状态。
更无聊的是，这个硬币不是公平的硬币，落尾的几率是p%。
打开所有灯泡所需的预期移动次数是多少？
我想知道它的算法或求解过程，因为这个问题的n是可变的。
天真的方法：Monte-Carlo-Simulation
描述
（您没有提供任何关于您想要哪种解决方案的信息，因此我提出了可能是最简单但仍然强大的方法：模拟）
Monte-Carlo方法允许我们模拟这个stochastic-process并观察需要的步骤数。由于这只是一个嘈杂的估计，我们需要多次这样做。使用无限次运行，此解将收敛到理论解！
代码
这是一些简单的python-based代码：
import random
import matplotlib.pyplot as plt # just for plotting
n = 10
p = 0.7
n_samples = 1000000
def run():
states = [0 for i in range(n)]
steps = 0
while 0 in states:
index = random.randint(0, n-1)
if random.random() < p: # non-fair coin
states[index] = 1
steps += 1
return steps
avg = 0.0
samples = []
for sample in range(n_samples):
steps = run()
avg += steps
samples.append(steps)
print(avg / n_samples)
plt.hist(samples)
plt.show()
代码输出
41.853233
数学方法：吸收马尔可夫链
描述
由于描述 light-bulbs 的 state-change 的概率仅取决于当前状态，因此 Markov-assumption 是有效的，我们可以使用 Markov-Chains 获得所需的平均步数。
因为最终状态将永远 self-loop 并且因为它会在给定无限步数的情况下达到，所以这是一个 吸收马尔可夫链 .
由于所有灯泡都是相同的，因此我们不需要对激活的灯泡的每个组合相互映射的转换进行建模。我们可以将其简化为更简单的形式：0 light-bulbs -> 1 light-bulbs -> ...（当然还有 self-loop）。
discrete-time discrete-state-space 吸收马尔可夫链允许简单而强大的期望值计算。
wikipedia 解释了一些理论。它也是用于以下代码的公式的来源。
代码
再来一些python:
import numpy as np
N = 10
P = 0.7
""" Build transition matrix """
trans_mat = np.zeros((N+1, N+1))
for source_state in range(N):
prob_hitting_next = ((N-source_state) / float(N)) * P
inverse = 1.0 - prob_hitting_next
trans_mat[source_state, source_state] = inverse
trans_mat[source_state, source_state+1] = prob_hitting_next
trans_mat[N, N] = 1.0
""" Will look like this:
[[ 0.3 0.7 0. 0. 0. 0. 0. 0. 0. 0. 0. ]
[ 0. 0.37 0.63 0. 0. 0. 0. 0. 0. 0. 0. ]
[ 0. 0. 0.44 0.56 0. 0. 0. 0. 0. 0. 0. ]
[ 0. 0. 0. 0.51 0.49 0. 0. 0. 0. 0. 0. ]
[ 0. 0. 0. 0. 0.58 0.42 0. 0. 0. 0. 0. ]
[ 0. 0. 0. 0. 0. 0.65 0.35 0. 0. 0. 0. ]
[ 0. 0. 0. 0. 0. 0. 0.72 0.28 0. 0. 0. ]
[ 0. 0. 0. 0. 0. 0. 0. 0.79 0.21 0. 0. ]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0.86 0.14 0. ]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.93 0.07]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. ]]
"""
""" Q: the sub-matrix of trans_mat without
the rows and columns of any absorbing states
N_fund: fundamental matrix
t: expected number of steps before beeing absorved for each start-state
"""
Q_sub = trans_mat[:N, :N]
N_fund = np.linalg.inv(np.eye(N) - Q_sub)
t = np.dot(N_fund, np.ones(N))
print(t)
print(t[0]) # this is the value we want
代码输出
[ 41.84240363 40.4138322 38.82653061 37.04081633
35. 32.61904762 29.76190476 26.19047619 21.42857143 14.28571429]
41.8424036281 # less than 1 second calculation time!