“标记”难题的任务是排列编号的图块。 今天，数学家们已经解决了反问题-如何混淆难题。您可能玩过标签。 这是一款令人沮丧但令人上瘾的游戏，由15个磁贴和一个空白区域组成，并按4 x 4网格排列，其任务是移动磁贴并按数字的升序排列，或者在某些版本中，从中组合图像。
在1870年代问世后，它进入了标准游戏系列。 此外，它吸引了研究了一个多世纪的各种尺寸和初始形状的难题的数学家的注意力。
今天，
有新的证据表明解决“ 15点游戏”的方法相反。 石溪大学的数学家Yoon Chu和
Robert Howe确定了将有序场变成随机场所需的移动次数。
Percy Deaconess在1988年提出了带有随机化的“标签”问题的一种形式。 他建议将任何大小的拼图随机化大约需要
n 3个动作。 也就是说，对于4 x 4场，将需要4
3或64个移动，对于10 x 10场，将需要10
3或1,000个移动。 （尽管它们仍被称为“十五”，但字段可以具有任意数量的空格，以构成正确的正方形。）
斯坦福大学女执事学院的数学家表示，他的“ 15博弈”问题的版本代表了一大类类似的随机问题。 其中许多任务与自然的基本特征有关，例如，与引起基因突变的DNA碱基对的位置变化有关，以及与分子彼此分离并变得无序的方式有关-当冰融化时就会发生这种情况。
Deaconess希望了解了“斑点”的缠结问题之后，我们将能够理解整个有序系统是如何变成均匀混合状态的。
在类似“标签”的情况下，随机性一次发展一个步骤。 想象一个完全有序的字段，在左上角有一个单位，在右下角有空白。 我们移动图块，以使空白区域在四个可能的方向中的任何一个上移动一个正方形：向上，向下，向左或向右。 （出于数学上的优雅考虑，Chu和Howe考虑了一个其边缘相互成环形连接的字段，因此，这些图块永远不会卡在角落中。）让我们随机选择。 现在，该字段处于新配置中-不是完全按顺序排列，但距离它并不远。 重复此过程。 如果您继续移动空的正方形，该字段将越来越多地远离原始订购位置。
此过程的重要特征是，在每个步骤中，后续字段配置仅取决于当前配置。 这让人联想到《大富翁》中的游戏：掷骰子并将两个方块从公园广场移至木板路的可能性并不取决于导致我们进入公园广场笼子的掷骰。
十五蠕虫逐渐向疾病蔓延，每次一步。 许多其他系统（例如融冰）也以相同的方式随机分配。 数学家使用称为“马尔可夫链”的模型研究这种现象。 马尔可夫链是研究任何随机过程的正式方法，其中后续系统配置仅取决于当前配置。 他们站在对机会的数学理解的最前沿。
数学家尤瓦尔·佩雷斯（Yuval Perez）说：“马尔可夫链条是千篇一律的，一方面，我们仍然可以对其进行分析，另一方面，它们描述了许多我们感兴趣的现象。”
在他们的新工作中，Chu和Howe与“马尔可夫链”一样，对“标签”进行了随机化处理。 特别是，他们考虑了一组称为马尔可夫链的“过渡矩阵”。 过渡矩阵是一组广泛的数字，用于确定如果我们决定随机移动空白空间，“ 15点游戏”将从一种配置移动到另一种配置的可能性。
了解过渡矩阵是计算随机或随机排列有序字段所需的移动次数的关键。 特别是，Chu和Hou专注于定义表征过渡矩阵的数字集-称为“特征值”的数字。
“通过收集有关特征值的足够信息，我们可以获得非常准确的混合信息，” Howe说。
“点”的转换矩阵包含大量信息，这些信息反映了数以万计的不同配置，即使是很小的4 x 4字段也可以创建，这比数学家可以直接处理的信息更多。 因此，Chu和Howe并未分析现场路径随机化的每一步的过渡矩阵，而是发现了如何表征整个过渡矩阵的平均行为。
他们的方法类似于如何在掷出1000次骰子后找出我们最有可能出现在“垄断”领域的位置：您实际上可以掷骰子很多次，或者仅取平均数次掷骰子就可以推断出来。
Chu和Howe使用这项技术计算了转换矩阵的特征值，该矩阵告诉他们需要进行多少移动才能使“斑点”随机化。 他们甚至根据两个不同的随机性定义收到了两个答案。
首先，他们考虑了一个随机字段，在该字段上，具有相同概率的每个图块可以位于该字段的任何正方形中。 有了这个定义，他们发现为了将字段
n随机化为
n，需要 n 4次移动（即，对于4 x 4的字段为256步，对于10 x 10的字段为10,000步）。 这超出了Diaconis的预测（我们记得，他建议
n 3个步骤）。
楚和侯对机会的第二个定义更为严格。 他们考虑了一个随机字段，该字段具有相同的概率，可能处于其多种可能的配置中。 他们证明，要实现对随机性的定义，还需要采取一些步骤-最多不超过
n 4 log
n个移动。
Chu和Howe证明，随机化“ 15的游戏”比Diaconis预测的困难。 从某种意义上讲，这表明完全消除系统中的顺序比预期花费更多的时间。 由于他们的工作，“标签”现已成为为数不多的随机化任务之一，据Howe称，“事实上，随机化所需的步骤数是已知的。”
豪和佩雷斯目前正在努力扩大证据。 除其他事项外，他们对磁场是否随着大小急剧增加而达到随机状态感兴趣。 具有这种行为的系统看起来根本不是随机的，而仅一步之遥，它们突然变得如此。
佩雷斯说：“我们还不完全了解哪些马尔可夫链表现出这种突然性。” “这是该领域最大的谜团之一。”