Abstract
We consider killed planar random walks on isoradial graphs. Contrary to the lattice case, isoradial graphs are not translation invariant, do not admit any group structure and are spatially non-homogeneous. Despite these crucial differences, we compute the asymptotics of the Martin kernel, deduce the Martin boundary and show that it is minimal. Similar results on the grid \(\mathbb {Z}^{d}\) are derived in a celebrated work of Ney and Spitzer.
Similar content being viewed by others
References
Abramowitz, M., Stegun, I.A.: Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. National Bureau of Standards Applied Mathematics Series, 55 (1964)
Almkvist, G., Zeilberger, D.: The method of differentiating under the integral sign. J. Symbolic Comput. 10, 571–591 (1990)
Babillot, M.: Théorie du renouvellement pour des chaînes semi-markoviennes transientes. Ann. Inst. H. Poincaré, Probab. Statist. 24, 507–569 (1988)
Beffara, V., Duminil-Copin, H., Smirnov, S.: On the critical parameters of the \(q\leqslant 4\) random-cluster model on isoradial graphs. J. Phys. A 48, 484003, 25pp. (2015)
Biane, P.: Théorème de Ney-Spitzer sur le dual de SU(2). Trans. Amer. Math. Soc. 345, 179–194 (1994)
Bobenko, A.I., Suris, Y.B.: Discrete Differential Geometry Integrable Structure Graduate Studies in Mathematics, vol. 98. American Mathematical Society, Providence, RI (2008)
Bodini, O., Fernique, T., Rémila, É.: A characterization of flip-accessibility for rhombus tilings of the whole plane. Inform. Comput. 206, 1065–1073 (2008)
Bostan, A., Chyzak, F., Salvy, B., Lecerf, G., Schost, É.: Differential equations for algebraic functions. In: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, pp 25–32 (2007)
Bostan, A., Kurkova, I., Raschel, K.: A human proof of Gessel’s lattice path conjecture. Trans. Amer. Math Soc. 369, 1365–1393 (2017)
Bostan, A., Dumont, L., Salvy, B.: Efficient algorithms for mixed creative telescoping. In: Proceedings of the 2016 International Symposium on Symbolic and Algebraic Computation, pp 127–134 (2016)
Boutillier, C., de Tilière, B.: The critical Z-invariant Ising model via dimers: locality property. Comm. Math. Phys. 301, 473–516 (2011)
Boutillier, C., de Tilière, B.: Statistical mechanics on isoradial graphs. In: Deuschel, J.-D., et al. (eds.) Probability in Complex Physical Systems, vol. 11, pp 491–512. Springer Proceedings in Mathematics (2012)
Boutillier, C., de Tilière, B., Raschel, K.: The Z-invariant massive Laplacian on isoradial graphs. Invent. Math. 208, 109–189 (2017)
Boutillier, C., de Tilière, B., Raschel, K.: The Z-invariant Ising model via dimers. Probab. Theory Related Fields 174, 235–305 (2019)
de Bruijn, N.G.: Algebraic theory of Penrose’s nonperiodic tilings of the plane. I. Nederl. Akad. Wetensch. Indag. Math. 43, 39–52 (1981)
Chelkak, D., Smirnov, S.: Discrete complex analysis on isoradial graphs. Adv. Math. 228, 1590–1630 (2011)
Choquet, G., Deny, J.: Sur l’équation de convolution μ = μ ∗ σ. C. R. Acad. Sci. Paris 250, 799–801 (1960)
de Tilière, B.: Scaling limit of isoradial dimer models and the case of triangular quadri-tilings. Ann. Inst. H. Poincaré Sect. B. 43, 729–750 (2007)
Doob, J.L.: Discrete potential theory and boundaries. J. Math. Mech. 8, 433–458 (1959)
Doob, J.L., Snell, J.L., Williamson, R.E.: Application of Boundary Theory to Sums of Independent Random Variables. Contributions to Probability and Statistics, pp 182–197. Stanford Univ. Press, Stanford (1960)
Duffin, R.J.: Potential theory on a rhombic lattice. J. Combinatorial Theory 5, 258–272 (1968)
Duminil-Copin, H., Li, J.-H., Manolescu, I.: Universality for the random-cluster model on isoradial graphs. Electron. J. Probab. 23(96), 70 (2018)
Dussaule, M.: The Martin boundary of a free product of abelian groups. Ann. Inst. Fourier (Grenoble) 70, 313–373 (2020)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press (2009)
Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V.: Discriminants Resultants and Multidimensional Determinants. Birkhäuser (1994)
Godefroy, L.: Martin boundary of polynomial random walks on the d-dimensional lattice of nonnegative integers. J. Theoret. Probab. 17, 111–129 (2004)
Grimmett, G.R., Manolescu, I.: Bond percolation on isoradial graphs: criticality and universality. Probab. Theory Related Fields 159, 273–327 (2014)
Imamoglu, E., van Hoeij, M.: Computing hypergeometric solutions of second order linear differential equations using quotients of formal solutions and integral bases. J. Symbolic Comput. 83, 254–271 (2017)
Hennequin, P.-L.: Processus de Markoff en cascade. Ann. Inst. H. Poincaré 18, 109–195 (1963)
Hunt, G.A.: Markoff chains and Martin boundaries. Illinois J. Math. 4, 313–340 (1960)
Ignatiouk-Robert, I., Loree, C.: Martin boundary of a killed random walk on a quadrant. Ann. Probab. 38, 1106–1142 (2010)
Ignatiouk-Robert, I.: Martin boundary of a killed random walk on a half-space. J. Theoret. Probab. 21, 35–68 (2008)
Ignatiouk-Robert, I.: Martin boundary of a reflected random walk on a half-space. Probab. Theory Related Fields 148, 197–245 (2010)
Ignatiouk-Robert, I.: T-martin boundary of reflected random walks on a half-space. Electron. Commun. Probab. 15, 149–161 (2010)
Ignatiouk-Robert, I.: Harmonic functions of random walks in a semigroup via ladder heights. J. Theoret. Probab. (to appear)
Kauers, M.: The guess-and-prove paradigm in action. Internationale Mathematische Nachrichten 237, 1–15 (2018)
Kauers, M., Pillwein, V.: When can we detect that a P-finite sequence is positive?. In: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, pp 195–201 (2010)
Kenyon, R.: The Laplacian and Dirac operators on critical planar graphs. Invent. Math. 150, 409–439 (2002)
Kenyon, R.: Determinantal spanning forests on planar graphs. Ann. Probab. 47, 952–988 (2019)
Koutschan, C: Creative telescoping for holonomic functions. In: Computer Algebra in Quantum Field Theory. Texts Monogr. Symbol. Comput., pp. 171–194. Springer, Vienna (2013)
Kurkova, I.A., Malyshev, V.A.: Martin boundary and elliptic curves. Markov Process. Related Fields 4, 203–272 (1998)
Lawden, D.: Elliptic Functions and Applications. Applied Mathematical Sciences, vol. 80. Springer-Verlag, New York (1989)
Mercat, C.: Discrete Riemann surfaces and the Ising model. Comm. Math. Phys. 218, 177–216 (2001)
Martin, R.S.: Minimal positive harmonic functions. Trans. Amer. Math. Soc. 49, 137–172 (1941)
Mustapha, S.: Gaussian estimates for spatially inhomogeneous random walks on \(\mathbb Z^{d}\). Ann. Probab. 34, 264–283 (2006)
Ney, P., Spitzer, F.: The Martin boundary for random walk. Trans. Amer. Math. Soc. 121, 116–132 (1966)
Nica, A., Speicher, R.: Lectures on the Combinatorics of Free Probability. London Mathematical Society Lecture Note Series, 335. Cambridge University Press (2006)
Pemantle, R., Wilson, M.: Analytic Combinatorics in Several Variables. Cambridge Studies in Advanced Mathematics (2013)
Sawyer, S.A.: Martin Boundaries and Random Walks. Harmonic Functions on Trees and Buildings (New York, 1995). Contemp Math., vol. 206, pp 17–44. Amer. Math. Soc., Providence, RI (1997)
Sokal, A.D.: The Euler and Springer numbers as moment sequences. Expo. Math. 38, 1–26 (2020)
Spitzer, F.: Principles of Random Walk. The University Series in Higher Mathematics D. Van Nostrand Co., Inc. Princeton, N.J.-Toronto-London (1964)
Stanley, R.P.: Differentiably finite power series. European J. Combin. 1, 175–188 (1980)
Vidūnas, R.: Transformations of algebraic Gauss hypergeometric functions. arXiv:0807.4808 (2008)
Vidūnas, R.: Algebraic transformations of Gauss hypergeometric functions. Funkcial. Ekvac. 52, 139–180 (2009)
Woess, W.: Random Walks on Infinite Graphs and Groups. Cambridge Tracts in Mathematics, vol. 138. Cambridge University Press, Cambridge (2000)
Acknowledgments
We warmly thank Béatrice de Tilière for interesting discussions. We also thank an anonymous referee for his/her reading and comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Alin Bostan authored the Appendix section of this paper.
This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under the Grant Agreement No. 759702 and from the ANR DIMERS (ANR-18-CE40-0033).
Appendix: Some thoughts on a positivity question (by Alin Bostan)
Appendix: Some thoughts on a positivity question (by Alin Bostan)
We consider the following question: let \(s(k)={\sum }_{n \geqslant 0} s_{n} k^{n}\), starting
be the unique power series solution of the algebraic equation
We want to prove that all the coefficients of s(k) are non-negative, and more precisely that all the coefficients s2n are positive.
Note that the sequence \((s_{n})_{n \geqslant 0}\) satisfies various types of recurrences, either non-linear, obtained by extracting the coefficient of kn in both sides of Eq. (30), or even linear, obtained by using a linear differential equation (with polynomial coefficients in k) satisfied by s(k). However, these recurrences cannot be used directly to solve our positivity question. For instance, from the algebraic Eq. (30), Cockle’s algorithm (see [8] and the references therein) proves that s(k) satisfies the 3rd order linear inhomogeneous differential equation
from which a coefficient extraction proves that \((s_{n})_{n \geqslant 0}\) satisfies the linear recurrence
It is not obvious from this recurrence how to derive a non-negativity proof because of the plus sign in front of the coefficient of sn. In principle, two quite general methods might be applied to this kind of question (alone, or combined): one relying on (effective) asymptotics for the coefficients of algebraic functions [24, p. 504–505], the other relying on the approach of [37, §4.2]. Instead, we present two different proofs.
The first one is based on the following hypergeometric expression for s(k):
where the Gauss�� hypergeometric series with parameters \(\frac 12, \frac 56\) and \(\frac 53\) is defined by
and (x)n denotes the Pochhammer symbol (x)n = x(x + 1)⋯(x + n − 1) for \(n\in \mathbb {N}\).
Once found (e.g., using algorithmic tools for automated guessing [36], or for differential equation solving [28]), equality Eq. (33) can easily be proved using closure properties of D-finite functions [52]: from the 2nd order linear differential equation satisfied by \({}_{2}F_{1}\left [\begin {array}{cc}\frac {1}{2} \frac {5}{6}\\\frac {5}{3} \end {array}; k^{2}\right ]\), one computes a 3rd order differential equation satisfied by the right-hand side of Eq. (33), which appears to coincide with the differential Eq. (31) satisfied by the left-hand side of Eq. (33). Therefore, the coefficients sequences of both right-hand side and left-hand side of Eq. (33) satisfy the recurrence relation Eq. (32), hence they are equal since their initial terms coincide.
A shorter proof of equality Eq. (33), with a different (more geometric) flavor, goes as follows: on the one hand, the hypergeometric function in Eq. (34) satisfies the algebraic transformationFootnote 1
On the other hand, it is easy to prove, starting from the polynomial Eq. (30), that the algebraic function s(k) satisfies
Denoting \(\displaystyle {{\varphi }(x) = { {x \left (x+2 \right )^{3}} / { \left (2 x+1 \right )^{3}}}}\), identity Eq. (33) becomes trivial in the new variable x:
Now that Eq. (33) is proved, the positivity of the coefficients s2n of s(k) is a direct consequence of the obvious fact that the hypergeometric power series in Eq. (34) has positive coefficients.
The second proof is based on the so-called Stieltjes inversion formula [47, Lecture 2], that allows to express in some cases the n-th term of a sequence as the n-th moment of a positive density. Using this formula, one can deduce the following expression:
where H1(k) and H2(k) are the hypergeometric functions
At this point, positivity is not yet apparent. However, using the change of variables k = φ(x), and using the fact that H1(φ(x)) and H2(φ(x)) become the simple algebraic functions 2(x + 1)1/3(2x + 1)1/2/(x + 2) and (2x + 1)− 1/2, the previous expression simplifies to:
Once found, equality Eq. (35) can again be proved automatically using algorithmic tools, notably the method of “creative telescoping” [2, 10, 40].
Note that Lagrange inversion is a tempting alternative to the previous moment approach; however, in our case, it gives that for all n > 0,
and positivity is not clear on any of these expressions.
In contrast, identity Eq. (35) obviously proves that the sequence \((s_{2n})_{n\geqslant 0}\) is positive. And it actually proves much more, namely that \((s_{2n})_{n\geqslant 0}\) is a Stieltjes-Hausdorff moment sequence, and in particular that it is log-convex, i.e., \( s_{2n+2}s_{2n-2} \geqslant s_{2n}^{2}\) for all \(n\geqslant 1\) [50, §2] and \({\Delta }^{k} s_{2n} \geqslant 0\) for all \(k\geqslant 0\) [51, p. 338], where Δ is the difference operator Δ(cn) = (cn − cn+ 1).
We also consider the following related question: let \(t(k)={\sum }_{n \geqslant 0} t_{n} k^{n}\), starting
be the unique power series solution of the algebraic equation
We want to prove that all the coefficients tn are non-negative.
First, we remark that \(t({\varphi }(x)^{\frac 12}) = { {({x}^{2}+x+1)}/{(1+x-2x^{2})}}\). Since \(s({\varphi }(x)^{\frac 12}) = (2x+1)/(x+2)\), this implies that t(k) = R(s(k)), where R is the rational function
As a consequence of this and of identity Eq. (33), we get that
where H is the hypergeometric function with non-negative coefficients
therefore all the coefficients of t(k) are non-negative.
Rights and permissions
About this article
Cite this article
Boutillier, C., Raschel, K. Martin Boundary of Killed Random Walks on Isoradial Graphs. Potential Anal 57, 201–226 (2022). https://doi.org/10.1007/s11118-021-09912-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11118-021-09912-5