为什么马尔可夫链会重演？

Question

我正在尝试使用 Python 中的类来模拟马尔可夫链。这是我的代码：

import random

...

class Chain:

  def __init__(self, probabilities, start):

    self.probs = probabilities

    self.start = start

    self.names = list(self.probs.keys())

  def __iter__(self):

    self.pos = self.start

    return self

  def __next__(self):

    self.random_num = random.randrange(100)

    prob_l = self.probs[self.pos]

    for ind, prob in enumerate(prob_l):

      self.prob_sum += prob

      if self.random_num < self.prob_sum:

        exclude_names = self.names[:ind] + self.names[ind + 1 :]

        self.prob_sum = 0

        self.pos = exclude_names[ind]

        return self.pos

    return self.pos

chain = Chain({"A": [50, 25], "B": [50, 25], "C": [50, 50]}, "A")

chain_iter = iter(chain)

for k in range(100):

    print(next(chain_iter))

它按预期工作，但有时会重复字母 C。由于字典中的两个 50，它应该有 50/50 的机会转到 A 或 B。它不应该重复。

Answer 1

您会看到重复的 C，因为当前节点的索引未正确计算。这是带有注释的更新代码：class Chain:&nbsp; def __init__(self, probabilities, start):&nbsp; # only called once&nbsp; &nbsp; self.probs = probabilities&nbsp; &nbsp; self.start = start&nbsp; &nbsp; self.names = list(self.probs.keys())&nbsp; &nbsp;&nbsp;&nbsp; def __iter__(self):&nbsp; # only called once&nbsp; &nbsp; return self&nbsp; &nbsp;&nbsp;&nbsp; def __next__(self):&nbsp; # each iteration&nbsp; &nbsp; import random&nbsp; &nbsp; self.pos = self.start&nbsp; # next step&nbsp; &nbsp; self.random_num = random.randrange(100) # choice percentile must be in here&nbsp; &nbsp; i = self.names.index(self.pos) # get index of this node in big list&nbsp; &nbsp; prob_l = self.probs[self.pos]&nbsp; # get probs&nbsp; &nbsp; self.prob_sum = 0&nbsp; # start prob scan&nbsp; &nbsp; for ind, prob in enumerate(prob_l): # probs of going to another node&nbsp; &nbsp; &nbsp; self.prob_sum += prob&nbsp; # until 100%&nbsp; &nbsp; &nbsp; if self.random_num < self.prob_sum:&nbsp; # passed percentile, go to another node&nbsp; &nbsp; &nbsp; &nbsp; exclude_names = self.names[:i] + self.names[i + 1:]&nbsp; # big list without this node&nbsp; &nbsp; &nbsp; &nbsp; self.start = exclude_names[ind]&nbsp; # for next iteration&nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp;# found percentile in probs&nbsp; &nbsp; return self.pos # add current pos to chain&nbsp; &nbsp;&nbsp;chain = Chain({"A": [50, 25], "B": [50, 25], "C": [50, 50]}, "A")chain_iter = iter(chain)for k in range(100):&nbsp; &nbsp;print(next(chain_iter), end=" ")输出（包装）A B A A B B C B A B A C A B C B A C B A B C B B C&nbsp;B A B C B A C A B A A B C B B A B B A B A C B C B&nbsp;B C A B A C A C B A C A B A B A C A B B C B A B A&nbsp;C A C A C B A A C B A A B B B A A A C A A B A B B