Percolation games, probabilistic cellular automata, and the hard-core model
Percolation games, probabilistic cellular automata, and the hard-core model
复制标题
渗滤游戏、概率细胞自动机和硬核模型
DOI：
10.1007/s00440-018-0881-6
复制
发表时间：
2018
影响因子：
2
通讯作者：
Holroyd A
中科院分区：
文献类型：
--
作者：
Holroyd A
让方形格子的每个位置独立地分配三个状态之一：概率为 p 的陷阱、概率为 q 的目标和概率为开的状态，其中。考虑以下游戏：令牌从原点开始，两个玩家轮流移动，其中移动包括将令牌从当前的 sitex 移动到任意一个。将令牌移至陷阱的玩家将立即输掉游戏，而将令牌移至目标的玩家将立即赢得游戏。比赛以最佳表现平局的正概率是否存在——即双方都无法强行获胜？这相当于一族基本一维概率细胞自动机（PCA）的遍历性问题。这些自动机已经在有向格动物枚举、黄金分割子移和硬核模型的背景下进行了研究，并且它们的遍历性已被几位作者视为一个悬而未决的问题。我们证明这些 PCA 是遍历的，相应地，游戏没有平局。另一方面，我们证明某些类似的游戏确实可以在更高维度的各种有向图上绘制合适的参数值，包括偶数子格的有向版本。这通过降维到硬核晶格气体的维度来证明。我们证明，只要相应的硬核模型具有多个吉布斯分布，就会发生平局。我们推测绘图也发生在面向标准的点阵上，但在这里我们的方法遇到了一个根本性的障碍。
Let each site of the square latticebe independently assigned one of three states: atrapwith probabilityp, atargetwith probabilityq, andopenwith probability, where. Consider the following game: a token starts at the origin, and two players take turns to move, where a move consists of moving the token from its current sitexto eitheror. A player who moves the token to a trap loses the game immediately, while a player who moves the token to a target wins the game immediately. Is there positive probability that the game isdrawnwith best play—i.e. that neither player can force a win? This is equivalent to the question of ergodicity of a certain family of elementary one-dimensional probabilistic cellular automata (PCA). These automata have been studied in the contexts of enumeration of directed lattice animals, the golden-mean subshift, and the hard-core model, and their ergodicity has been noted as an open problem by several authors. We prove that these PCA are ergodic, and correspondingly that the game onhas no draws. On the other hand, we prove that certain analogous gamesdoexhibit draws for suitable parameter values on various directed graphs in higher dimensions, including an oriented version of the even sublattice ofin all. This is proved via a dimension reduction to a hard-core lattice gas in dimension. We show that draws occur whenever the corresponding hard-core model has multiple Gibbs distributions. We conjecture that draws occur also on the standard oriented latticefor, but here our method encounters a fundamental obstacle.
登录
查看更多内容
ℤ 上有吸引力的最近邻自旋系统的正率问题
DOI：
10.1007/bf00539839
发表时间：
1982
期刊：
Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete
影响因子：
--
作者：
L. Gray
通讯作者：
L. Gray
关于 ${mathbb Z}^d$ 上硬核模型中的相变
DOI：
10.1017/s0963548303006035
发表时间：
2004
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
David J. Galvin;J. Kahn
通讯作者：
J. Kahn
随机棋盘上的游戏
DOI：
10.48550/arxiv.1505.07485
发表时间：
2015
期刊：
arXiv e-prints
影响因子：
--
作者：
Basu Riddhipratim
通讯作者：
Basu Riddhipratim
ℤ2 上硬核模型的相位共存和慢速混合
DOI：
10.1007/978-3-642-40328-6_27
发表时间：
2012
期刊：
ArXiv
影响因子：
--
作者：
Antonio Blanca;David J. Galvin;Dana Randall;P. Tetali
通讯作者：
P. Tetali
重新审视定向动物和气体模型
DOI：
10.37236/989
发表时间：
2007
期刊：
Electron. J. Comb.
影响因子：
--
作者：
Y. L. Borgne;J. Marckert
通讯作者：
J. Marckert