Finitely dependent processes are finitary. (English) Zbl 1453.60150

Summary: We show that any finitely dependent invariant process on a transitive amenable graph is a finitary factor of an i.i.d. process. With an additional assumption on the geometry of the graph, namely that no two balls with different centers are identical, we further show that the i.i.d. process may be taken to have entropy arbitrarily close to that of the finitely dependent process. As an application, we give an affirmative answer to a question of A. E. Holroyd [Ann. Inst. Henri Poincaré, Probab. Stat. 53, No. 2, 753–765 (2017; Zbl 1370.60061)].


60J99 Markov processes
60G10 Stationary stochastic processes
28D99 Measure-theoretic ergodic theory
37A35 Entropy and other invariants, isomorphism, classification in ergodic theory


Zbl 1370.60061
Full Text: DOI arXiv Euclid


[1] Aaronson, J., Gilat, D. and Keane, M. (1992). On the structure of \(1\)-dependent Markov chains. J. Theoret. Probab. 5 545-561. · Zbl 0754.60070 · doi:10.1007/BF01060435
[2] Aaronson, J., Gilat, D., Keane, M. and de Valk, V. (1989). An algebraic construction of a class of one-dependent processes. Ann. Probab. 17 128-143. · Zbl 0681.60038 · doi:10.1214/aop/1176991499
[3] Benjamini, I., Lyons, R., Peres, Y. and Schramm, O. (1999). Group-invariant percolation on graphs. Geom. Funct. Anal. 9 29-66. · Zbl 0924.43002 · doi:10.1007/s000390050080
[4] Burton, R. M., Goulet, M. and Meester, R. (1993). On \(1\)-dependent processes and \(k\)-block factors. Ann. Probab. 21 2157-2168. · Zbl 0788.60049 · doi:10.1214/aop/1176989014
[5] Häggström, O. (1997). Infinite clusters in dependent automorphism invariant percolation on trees. Ann. Probab. 25 1423-1436. · Zbl 0895.60098 · doi:10.1214/aop/1024404518
[6] Harel, M. and Spinka, Y. (2018). Finitary codings for the random-cluster model and other infinite-range monotone models. Preprint. Available at arXiv:1808.02333.
[7] Harvey, N., Holroyd, A. E., Peres, Y. and Romik, D. (2007). Universal finitary codes with exponential tails. Proc. Lond. Math. Soc. (3) 94 475-496. · Zbl 1148.37004 · doi:10.1112/plms/pdl018
[8] Holroyd, A. E. (2017). One-dependent coloring by finitary factors. Ann. Inst. Henri Poincaré Probab. Stat. 53 753-765. · Zbl 1370.60061 · doi:10.1214/15-AIHP735
[9] Holroyd, A. E., Hutchcroft, T. and Levy, A. (2017). Mallows permutations and finite dependence. Preprint. Available at arXiv:1706.09526. · Zbl 1456.60081 · doi:10.1214/19-AOP1363
[10] Holroyd, A. E., Hutchcroft, T. and Levy, A. (2018). Finitely dependent cycle coloring. Electron. Commun. Probab. 23 Paper No. 64, 12. · Zbl 1398.60054 · doi:10.1214/18-ECP118
[11] Holroyd, A. E. and Liggett, T. M. (2015). Symmetric 1-dependent colorings of the integers. Electron. Commun. Probab. 20 no. 31, 8. · Zbl 1385.60014
[12] Holroyd, A. E. and Liggett, T. M. (2016). Finitely dependent coloring. Forum Math. Pi 4 e9, 43. · Zbl 1361.60025 · doi:10.1017/fmp.2016.7
[13] Holroyd, A. E., Schramm, O. and Wilson, D. B. (2017). Finitary coloring. Ann. Probab. 45 2867-2898. · Zbl 1385.60048 · doi:10.1214/16-AOP1127
[14] Ibragimov, I. A. and Linnik, Ju. V. (1965). Независимые Сталионарно Связанные Величины. Izdat. “Nauka”, Moscow. · Zbl 0154.42201
[15] Ibragimov, I. A. and Linnik, Yu. V. (1971). Independent and Stationary Sequences of Random Variables. Wolters-Noordhoff, Groningen. · Zbl 0219.60027
[16] Keane, M. and Smorodinsky, M. (1977). A class of finitary codes. Israel J. Math. 26 352-371. · Zbl 0357.94012 · doi:10.1007/BF03007652
[17] Keane, M. and Smorodinsky, M. (1979). Bernoulli schemes of the same entropy are finitarily isomorphic. Ann. of Math. (2) 109 397-406. · Zbl 0405.28017 · doi:10.2307/1971117
[18] Knuth, D. E. and Yao, A. C. (1976). The complexity of nonuniform random number generation. In Algorithms and Complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976) 357-428. · Zbl 0395.65004
[19] Linial, N. (1987). Distributive graph algorithms global solutions from local data. In Foundations of Computer Science, 1987., 28th Annual Symposium on 331-335. IEEE, Los Alamitos.
[20] Lyons, R. (2017). Factors of IID on trees. Combin. Probab. Comput. 26 285-300. · Zbl 1371.05129 · doi:10.1017/S096354831600033X
[21] Lyons, R. and Peres, Y. (2016). Probability on Trees and Networks. Cambridge Series in Statistical and Probabilistic Mathematics 42. Cambridge Univ. Press, New York.
[22] Naor, M. (1991). A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Discrete Math. 4 409-412. · Zbl 0738.68007 · doi:10.1137/0404036
[23] Smorodinsky, M. (1992). Finitary isomorphism of \(m\)-dependent processes. In Symbolic Dynamics and Its Applications (New Haven, CT, 1991). Contemp. Math. 135 373-376. Amer. Math. Soc., Providence, RI. · Zbl 0768.28009
[24] Spinka, Y. (2018). Finitary coding for the sub-critical Ising model with finite expected coding volume. Preprint. Available at arXiv:1801.02529. · Zbl 1441.60088 · doi:10.1214/20-EJP420
[25] van den Berg, J. · Zbl 0968.60091 · doi:10.1214/aop/1022677456
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.