采特林类库

介绍

在本节中，我们研究一个简单的随机游动（或马尔可夫链），称为 采特林类库 . 它将使我们有机会了解组合数学、线性代数、表示理论和计算机探索之间的相互作用，而不需要太多的理论背景。我希望这能鼓励大家玩这个或类似的系统，并研究它们的属性！形式定理和证明可以在本节末尾的参考文献中找到。

几年来，人们已经知道群表示理论可以帮助研究演化为随机（马尔可夫链）的系统，将其分解为更简单的系统。最近人们认识到，推广这一点（即用其他公理代替群的可逆性公理）解释了其他特别简单的马尔可夫链的行为，例如Tsetlin库。

采特林类库

考虑一个类库的书架 n 独特的书籍。当一个人借了一本书，然后还了它，它就会被放回书架上所有书的右边。这就是我们在衣柜里处理那堆衬衫的自然方式：在使用和清洁之后，衬衫被放在它的上面。因此，最受欢迎的书籍/衬衫将更有可能出现在书架/书堆的右侧/顶部。

这种类型的组织具有自适应的优势：

  • 最常使用的书都堆积在右边，因此很容易找到。

  • 如果用途随时间变化，则系统会自适应。

事实上，这种策略不仅在日常生活中使用，而且在计算机科学中也有使用。出现的自然问题是：

  • 平稳分布 ：系统收敛到哪个状态？除其他外，它还用于评估一本书的平均访问时间。

  • 收敛速度 ：系统适应不断变化的环境的速度有多快。

让我们将描述形式化。Tsetlin库是一个离散马尔可夫链（离散时间，离散状态空间），描述如下：

  • 状态空间 Omega_n 是由 n 书。

  • 转换运算符用 partial_i colon Omega_n to Omega_n . 什么时候？ partial_i 应用于置换 sigma ，号码 i 移到排列的末尾。

  • 我们指定参数 x_i ge 0 为了所有 1le ile n 具有 sum_{{i=1}}^n x_i = 1 . 参数 x_i 指示选择运算符的概率 partial_i .

转移图与矩阵

我们可以描述操作者的行为 partial_i 论状态空间 Omega_n 有向图。下图显示的是 partial_1, partial_2, partial_3 在 Omega_3 ：

thematic_tutorials/algebraic_combinatorics/../media/tsetlin-library.png

以上图片可以在Sage中复制如下：

sage: P = Poset(([1,2,3],[]))

这是反链花冠。它的线性扩展都是 {{1,2,3}} ：：

sage: L = P.linear_extensions()
sage: L
The set of all linear extensions of Finite poset containing 3 elements
sage: L.list()
[[3, 2, 1], [3, 1, 2], [1, 3, 2], [1, 2, 3], [2, 1, 3], [2, 3, 1]]

图形通过以下方式生成：

sage: G = L.markov_chain_digraph(labeling='source'); G
Looped multi-digraph on 6 vertices
sage: view(G)  # not tested

我们现在可以看看转移矩阵，看看我们是否注意到它的特征值和特征向量：

sage: M = L.markov_chain_transition_matrix(labeling='source')
sage: M
[-x0 - x1       x2        0        0       x2        0]
[      x1 -x0 - x2       x1        0        0        0]
[       0        0 -x0 - x1       x2        0       x2]
[      x0        0       x0 -x1 - x2        0        0]
[       0        0        0       x1 -x0 - x2       x1]
[       0       x0        0        0       x0 -x1 - x2]

此矩阵被规范化，以便所有列都添加到0。所以我们需要补充 (x_0 + x_1 + x_2) 乘以 6times 6 得到概率矩阵的单位矩阵：

sage: x = M.base_ring().gens()
sage: Mt = (x[0]+x[1]+x[2])*matrix.identity(6)+M
sage: Mt
[x2 x2  0  0 x2  0]
[x1 x1 x1  0  0  0]
[ 0  0 x2 x2  0 x2]
[x0  0 x0 x0  0  0]
[ 0  0  0 x1 x1 x1]
[ 0 x0  0  0 x0 x0]

自从 x_i 作为形式变量，我们需要计算符号环中的特征值和特征向量 SR ：：

sage: Mt.change_ring(SR).eigenvalues()
[x2, x1, x0, x0 + x1 + x2, 0, 0]

你看到什么图案了吗？事实上，如果你开始玩更大的值 n （基本排列的大小），您可能会发现每个子集都有一个特征值 S 属于 {{1,2,ldots,n}} 多重性由一个混乱数给出 d_{{n-|S|}} . 排列数计算无固定点的排列。对于我们得到的特征向量：

sage: Mt.change_ring(SR).eigenvectors_right()
[(x2, [(1, 0, -1, 0, 0, 0)], 1),
 (x1, [(0, 1, 0, 0, -1, 0)], 1),
 (x0, [(0, 0, 0, 1, 0, -1)], 1),
 (x0 + x1 + x2,
  [(1,
    (x0 + x1)/(x0 + x2),
    x0/x1,
    (x0^2 + x0*x1)/(x1^2 + x1*x2),
    (x0^2 + x0*x1)/(x0*x2 + x2^2),
    (x0^2 + x0*x1)/(x1*x2 + x2^2))], 1),
 (0, [(1, 0, -1, 0, -1, 1), (0, 1, -1, 1, -1, 0)], 2)]

平稳分布是特征值的特征向量 1=x_0+x_1+x_2 . 你看到模式了吗？

Optional exercices: Study of the transition operators and graph

不要使用Sage中已经存在的方法，而是尝试构建状态空间 Omega_n 以及转换运算符 partial_i 你自己如下。

  1. 由于技术原因，在Sage中最实用的方法是将 n 类库里的书 0,1,cdots,n-1 ，并通过集合的置换来表示马尔可夫链中的每个状态 {{0,dots,n-1}} 作为元组。构造状态空间 Omega_n AS：：

    sage: list(map(tuple, Permutations(range(3))))
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]

  2. 编写函数 transition_operator(sigma, i) 它实现了运算符 partial_i 它以元组作为输入 sigma 和整数 i in {{1,2,ldots,n}} 并输出一个新的元组。提取子元组可能有用 (sigma[i:j] )和会议。

  3. 编写函数 tsetlin_digraph(n) 它构造了（多有向图），如上所示。这可以通过使用 DiGraph .

  4. 验证 n 有向图是强连通的（也就是说，你可以沿着箭头的方向从任意一个顶点转到另一个顶点）。这表明马尔可夫链是否不可约。

结论

从类库学的角度来研究 [Bidigare1997] 和 [Brown2000]. 文中给出了概率矩阵的特征值和平稳分布的精确表达式，并给出了证明。从反命题中给出了反命题的一般化 [AKS2013].

Bidigare1997

托马斯·帕特里克·比迪加尔。 超平面排列面代数及其相关Markov链 . ProQuest LLC，密歇根州安阿伯市，1997年。论文（博士），密歇根大学。

Brown2000

肯尼斯·S·布朗。 半群、环和马尔可夫链 . J、 理论。Probab.，13（3）：871-9382000年。

AKS2013

阿文·艾耶，史蒂文·克莱，安妮·席林。 线性扩张上的组合Markov链 J、 代数组合学， :doi:`10.1007/s10801-013-0470-9` ， :arxiv:`1205.7074` .