Skip to main content
Log in

Martin Boundary of Killed Random Walks on Isoradial Graphs

  • Published:
Potential Analysis Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

Notes

  1. This is inspired by the Darboux covering for tetrahedral hypergeometric equations of the Schwarz type (1/3, 1/3, 2/3) [53, §6.1], see also [54]. Note that the same change of variables has been used in [9, §4].

References

  1. Abramowitz, M., Stegun, I.A.: Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. National Bureau of Standards Applied Mathematics Series, 55 (1964)

  2. Almkvist, G., Zeilberger, D.: The method of differentiating under the integral sign. J. Symbolic Comput. 10, 571–591 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  3. Babillot, M.: Théorie du renouvellement pour des chaînes semi-markoviennes transientes. Ann. Inst. H. Poincaré, Probab. Statist. 24, 507–569 (1988)

    MathSciNet  MATH  Google Scholar 

  4. 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)

    Article  MATH  Google Scholar 

  5. Biane, P.: Théorème de Ney-Spitzer sur le dual de SU(2). Trans. Amer. Math. Soc. 345, 179–194 (1994)

    MathSciNet  MATH  Google Scholar 

  6. Bobenko, A.I., Suris, Y.B.: Discrete Differential Geometry Integrable Structure Graduate Studies in Mathematics, vol. 98. American Mathematical Society, Providence, RI (2008)

    Book  Google Scholar 

  7. Bodini, O., Fernique, T., Rémila, É.: A characterization of flip-accessibility for rhombus tilings of the whole plane. Inform. Comput. 206, 1065–1073 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  8. 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)

  9. Bostan, A., Kurkova, I., Raschel, K.: A human proof of Gessel’s lattice path conjecture. Trans. Amer. Math Soc. 369, 1365–1393 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  10. 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)

  11. Boutillier, C., de Tilière, B.: The critical Z-invariant Ising model via dimers: locality property. Comm. Math. Phys. 301, 473–516 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  12. 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)

  13. Boutillier, C., de Tilière, B., Raschel, K.: The Z-invariant massive Laplacian on isoradial graphs. Invent. Math. 208, 109–189 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  14. Boutillier, C., de Tilière, B., Raschel, K.: The Z-invariant Ising model via dimers. Probab. Theory Related Fields 174, 235–305 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  15. de Bruijn, N.G.: Algebraic theory of Penrose’s nonperiodic tilings of the plane. I. Nederl. Akad. Wetensch. Indag. Math. 43, 39–52 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  16. Chelkak, D., Smirnov, S.: Discrete complex analysis on isoradial graphs. Adv. Math. 228, 1590–1630 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  17. Choquet, G., Deny, J.: Sur l’équation de convolution μ = μσ. C. R. Acad. Sci. Paris 250, 799–801 (1960)

    MathSciNet  MATH  Google Scholar 

  18. 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)

    Article  MathSciNet  MATH  Google Scholar 

  19. Doob, J.L.: Discrete potential theory and boundaries. J. Math. Mech. 8, 433–458 (1959)

    MathSciNet  MATH  Google Scholar 

  20. 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)

    Google Scholar 

  21. Duffin, R.J.: Potential theory on a rhombic lattice. J. Combinatorial Theory 5, 258–272 (1968)

    Article  MathSciNet  MATH  Google Scholar 

  22. Duminil-Copin, H., Li, J.-H., Manolescu, I.: Universality for the random-cluster model on isoradial graphs. Electron. J. Probab. 23(96), 70 (2018)

    MathSciNet  MATH  Google Scholar 

  23. Dussaule, M.: The Martin boundary of a free product of abelian groups. Ann. Inst. Fourier (Grenoble) 70, 313–373 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  24. Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press (2009)

  25. Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V.: Discriminants Resultants and Multidimensional Determinants. Birkhäuser (1994)

  26. Godefroy, L.: Martin boundary of polynomial random walks on the d-dimensional lattice of nonnegative integers. J. Theoret. Probab. 17, 111–129 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  27. Grimmett, G.R., Manolescu, I.: Bond percolation on isoradial graphs: criticality and universality. Probab. Theory Related Fields 159, 273–327 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  28. 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)

    Article  MathSciNet  MATH  Google Scholar 

  29. Hennequin, P.-L.: Processus de Markoff en cascade. Ann. Inst. H. Poincaré 18, 109–195 (1963)

    MathSciNet  MATH  Google Scholar 

  30. Hunt, G.A.: Markoff chains and Martin boundaries. Illinois J. Math. 4, 313–340 (1960)

    Article  MathSciNet  MATH  Google Scholar 

  31. Ignatiouk-Robert, I., Loree, C.: Martin boundary of a killed random walk on a quadrant. Ann. Probab. 38, 1106–1142 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  32. Ignatiouk-Robert, I.: Martin boundary of a killed random walk on a half-space. J. Theoret. Probab. 21, 35–68 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  33. Ignatiouk-Robert, I.: Martin boundary of a reflected random walk on a half-space. Probab. Theory Related Fields 148, 197–245 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  34. Ignatiouk-Robert, I.: T-martin boundary of reflected random walks on a half-space. Electron. Commun. Probab. 15, 149–161 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  35. Ignatiouk-Robert, I.: Harmonic functions of random walks in a semigroup via ladder heights. J. Theoret. Probab. (to appear)

  36. Kauers, M.: The guess-and-prove paradigm in action. Internationale Mathematische Nachrichten 237, 1–15 (2018)

    Google Scholar 

  37. 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)

  38. Kenyon, R.: The Laplacian and Dirac operators on critical planar graphs. Invent. Math. 150, 409–439 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  39. Kenyon, R.: Determinantal spanning forests on planar graphs. Ann. Probab. 47, 952–988 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  40. Koutschan, C: Creative telescoping for holonomic functions. In: Computer Algebra in Quantum Field Theory. Texts Monogr. Symbol. Comput., pp. 171–194. Springer, Vienna (2013)

  41. Kurkova, I.A., Malyshev, V.A.: Martin boundary and elliptic curves. Markov Process. Related Fields 4, 203–272 (1998)

    MathSciNet  MATH  Google Scholar 

  42. Lawden, D.: Elliptic Functions and Applications. Applied Mathematical Sciences, vol. 80. Springer-Verlag, New York (1989)

    Book  Google Scholar 

  43. Mercat, C.: Discrete Riemann surfaces and the Ising model. Comm. Math. Phys. 218, 177–216 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  44. Martin, R.S.: Minimal positive harmonic functions. Trans. Amer. Math. Soc. 49, 137–172 (1941)

    Article  MathSciNet  MATH  Google Scholar 

  45. Mustapha, S.: Gaussian estimates for spatially inhomogeneous random walks on \(\mathbb Z^{d}\). Ann. Probab. 34, 264–283 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  46. Ney, P., Spitzer, F.: The Martin boundary for random walk. Trans. Amer. Math. Soc. 121, 116–132 (1966)

    Article  MathSciNet  MATH  Google Scholar 

  47. Nica, A., Speicher, R.: Lectures on the Combinatorics of Free Probability. London Mathematical Society Lecture Note Series, 335. Cambridge University Press (2006)

  48. Pemantle, R., Wilson, M.: Analytic Combinatorics in Several Variables. Cambridge Studies in Advanced Mathematics (2013)

  49. 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)

    Google Scholar 

  50. Sokal, A.D.: The Euler and Springer numbers as moment sequences. Expo. Math. 38, 1–26 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  51. Spitzer, F.: Principles of Random Walk. The University Series in Higher Mathematics D. Van Nostrand Co., Inc. Princeton, N.J.-Toronto-London (1964)

    Google Scholar 

  52. Stanley, R.P.: Differentiably finite power series. European J. Combin. 1, 175–188 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  53. Vidūnas, R.: Transformations of algebraic Gauss hypergeometric functions. arXiv:0807.4808 (2008)

  54. Vidūnas, R.: Algebraic transformations of Gauss hypergeometric functions. Funkcial. Ekvac. 52, 139–180 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  55. Woess, W.: Random Walks on Infinite Graphs and Groups. Cambridge Tracts in Mathematics, vol. 138. Cambridge University Press, Cambridge (2000)

    Book  Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to Kilian Raschel.

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

$$ s(k) =\frac{1}{2}+\frac{3}{32}k^{2}+\frac{3}{64}k^{4}+\frac{123}{4096}k^{6}+\frac{177}{8192}k^{8}+\frac{34887}{2097152}k^{10}+\cdots, $$

be the unique power series solution of the algebraic equation

$$ k^{2}s^{4}-2k^{2}s^{3}+2s-1=0. $$
(30)

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

$$ \begin{array}{@{}rcl@{}} 9 {k}^{3} \left( k-1 \right)^{2} \left( k+1 \right)^{2}&& s^{\prime\prime\prime} \left( k \right) +9 {k}^{2} \left( k-1 \right) \left( k+1 \right) \left( 5 {k}^{2}-1 \right) s^{\prime\prime} \left( k \right) \\ &&+k \left( 35 {k}^{4}-14 {k}^{2}-13 \right) s^{\prime} \left( k \right) -4 \left( {k}^{2}-2 \right) s \left( k \right) = 4-2 {k}^{2}, \end{array} $$
(31)

from which a coefficient extraction proves that \((s_{n})_{n \geqslant 0}\) satisfies the linear recurrence

$$ \begin{array}{@{}rcl@{}} \left( 3 n+10 \right) \left( 3 n+14 \right) \left( n+2 \right) s_{n+4} + n \left( 3 n+2 \right) \left( 3 n+4 \right) s_{n} \\ = 2 \left( 9 {n}^{3}+54 {n}^{2}+106 n+70 \right) s_{n+2}. \end{array} $$
(32)

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):

$$ s(k)=\frac{1}{2}+ \frac{3}{2} \cdot \left( \frac{k}{4} \cdot {}_{2}F_{1}\left[\begin{array}{cc}\frac{1}{2} \frac{5}{6}\\\frac{5}{3} \end{array}; k^{2}\right] \right)^{2}, $$
(33)

where the Gauss�� hypergeometric series with parameters \(\frac 12, \frac 56\) and \(\frac 53\) is defined by

$$_{2}F_{1}\left[\begin{array}{cc}\frac{1}{2} \frac{5}{6}\\\frac{5}{3} \end{array}; k^{2}\right] = \sum\limits_{n=0}^{\infty} \frac{(\frac12)_{n}(\frac56)_{n}}{(\frac53)_{n}} \frac {k^{n}} {n!} = 1+{\frac{1}{4}}k+{\frac{33}{256}}{k}^{2}+{\frac{85}{1024}}{k}^{3} +\cdots , $$
(34)

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

$${~}_{2}F_{1}\left[\begin{array}{cc}\frac{1}{2} \frac{5}{6}\\\frac{5}{3} \end{array}; \frac{x(x+2)^{3}}{(2x+1)^{3}}\right] =4 {\frac { \left( 2 x+1 \right)^{\frac32}}{ \left( x+2 \right)^{2}}}.$$

On the other hand, it is easy to prove, starting from the polynomial Eq. (30), that the algebraic function s(k) satisfies

$$ s \left( {\frac{x^{\frac12} \left( x+2 \right)^{\frac32}}{ \left( 2 x+1 \right)^{\frac32}}} \right) = {\frac {2 x+1}{x+2}}.$$

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:

$${\frac {2 x+1}{x+2}}=\frac12+\frac{3}{2} \cdot {\varphi}(x) \cdot \left( {\frac { \left( 2 x+1 \right)^{3/2}}{ \left( x+2 \right)^{2}}}\right)^{2}.$$

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:

$$ s_{2n}= \frac{\sqrt{3}}{\pi}\cdot {{\int}_{0}^{1}} k^{n}\cdot H_{1}(k) \cdot \left( \frac{1}{{2}^{4/3}}\cdot {\frac {H_{2}(k)}{{k}^{2/3}}} -\frac{1}{{2}^{8/3}} \cdot \frac {H_{1}(k)}{{k}^{1/3}} \right)\mathrm{d} k, $$

where H1(k) and H2(k) are the hypergeometric functions

$$H_{1} = {}_{2}F_{1}\left[\begin{array}{cc}\frac{1}{6} \frac{5}{6}\\\frac{4}{3} \end{array}; k\right] = 1+{\frac{5}{48}}k+\cdots, \quad H_{2} = {}_{2}F_{1}\left[\begin{array}{cc}-\frac{1}{6} \frac{1}{2}\\\frac{2}{3} \end{array}; k\right] =1-{\frac{1}{8}}k-{\frac{3}{64}}{k}^{2}-\cdots. $$

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:

$$ s_{2n} = \frac{\sqrt {3} \cdot \sqrt [3]{2}}{\pi} \cdot {{\int}_{0}^{1}} {\frac { \left( x-1 \right)^{2} \left( \sqrt [3]{2}-\sqrt [3]{x^{2}+x} \right) \sqrt [3]{x+1}}{ \left( x+2 \right) \left( 2 x+1 \right)^{2}{x}^{2/3}}} {\varphi}(x)^{n}\mathrm{d} x. $$
(35)

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,

$$ s_{2n} = \frac{1}{2n} \cdot [z^{-1}] \left( {\frac { \left( z+1 \right)^{3} \left( 3-z \right) }{16 z}} \right)^{n} = \frac{(-1)^{n}}{{n\cdot {2}^{4n+1}}} \cdot \sum\limits_{i=0}^{n}{3 n\choose i}{n\choose i+1} \left( -3 \right)^{i+1}, $$

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) = (cncn+ 1).

We also consider the following related question: let \(t(k)={\sum }_{n \geqslant 0} t_{n} k^{n}\), starting

$$ t(k)=1+\frac{3}{64}k^{4}+\frac{3}{64}k^{6}+\frac{711}{16384}k^{8}+\frac{327}{8192}k^{10}+\cdots, $$

be the unique power series solution of the algebraic equation

$$ -27(1-k^{2})t^{4}+18(1-k^{2})t^{2}+2(2-k^{2})^{2}t+1-k^{2}+k^{4}=0. $$
(36)

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

$$R(z) = {\frac {{z}^{2}-z+1}{3 z \left( 1-z \right) }}. $$

As a consequence of this and of identity Eq. (33), we get that

$$ t(k) = (1+3 H^{4})/(1-9 H^{4}) = (1+3 H^{4}) \cdot \sum\limits_{n \geqslant 0} (9H^{4})^{n}, $$
(37)

where H is the hypergeometric function with non-negative coefficients

$$ H = \frac{k}{4} \cdot {}_{2}F_{1}\left[\begin{array}{cc}\frac{1}{2} \frac{5}{6}\\\frac{5}{3} \end{array}; k^{2}\right] = {\frac{1}{4}}k+{\frac{1}{16}}{k}^{3}+{\frac{33}{1024}}{k}^{5}+\cdots,$$

therefore all the coefficients of t(k) are non-negative.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11118-021-09912-5

Keywords

Mathematics Subject Classification (2010)

Navigation