×

zbMATH — the first resource for mathematics

A proof of the transfer-current theorem in absence of reversibility. (English) Zbl 1405.05169
Summary: The transfer-current theorem is a well-known result in probability theory stating that edges in a uniform spanning tree of an undirected graph form a determinantal process with kernel interpretable in terms of flows. Its original derivation due to R. Burton and R. Pemantle [Ann. Probab. 21, No. 3, 1329–1371 (1993; Zbl 0785.60007)] is based on a clever induction using comparison of random walks with electrical networks. Several variants of this celebrated result have recently appeared in the literature. In this paper we give an elementary proof of an extension of this theorem when the underlying graph is directed, irreducible and finite. Further, we give a characterization of the corresponding determinantal kernel in terms of flows extending the kernel given by Burton-Pemantle [loc. cit.] to the non-reversible setting.
MSC:
05C81 Random walks on graphs
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C05 Trees
15A15 Determinants, permanents, traces, other special matrix functions
05C85 Graph algorithms (graph-theoretic aspects)
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Benjamini, I.; Lyons, R.; Peres, Y.; Schramm, O., Uniform spanning forests, Ann. Probab., 29, 1-65, (2001) · Zbl 1016.60009
[2] Burton, R.; Pemantle, R., Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances, Ann. Probab., 21, 1329-1371, (1993) · Zbl 0785.60007
[3] Chang, Y., Contribution à l’étude des lacets markoviens, vol. tel-00846462, (2013), Université Paris Sud - Paris XI
[4] Doyle, P. G.; Snell, J. L., Random walks and electrical networks, (1984), Mathematical Association of America Washington DC · Zbl 0583.60065
[5] Forman, R., Determinants of Laplacians on graphs, Topology, 32, 35-46, (1993) · Zbl 0780.05041
[6] Grimmett, G. R., Probability on graphs, (2012), Cambridge University Press
[7] Hough, J. B.; Krishnapur, M.; Peres, Y.; Virag, B., Determinantal processes and independence, Probab. Surv., 3, 206-229, (2006) · Zbl 1189.60101
[8] Kassel, A.; Wu, W., Transfer current and pattern fields in spanning trees, Probab. Theory Related Fields, 163, 1-2, 89-121, (2015) · Zbl 1328.60216
[9] Kenyon, R., Spanning forests and the vector bundle Laplacian, Ann. Probab., 39, 5, 1983-2017, (2017) · Zbl 1252.82029
[10] Kirchhoff, G., Über di auflösung der gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer ströme geführt wird, Ann. Phys. Chem., 72, 497-508, (1847)
[11] Le Jan, Y., (Markov Paths, Loops and Fields, Lecture Notes in Mathematics, vol. 2026, (2011), Springer Heidelberg), Lectures from the 38th Probability Summer School held in Saint-Flour, 2008, Ecole d’Été de Probabilités de Saint-Flour
[12] Levin, D. A.; Peres, Y.; Wilmer, E. L., Markov chains and mixing times, (2008), American Mathematical Society
[13] Lyons, R.; Peres, Y., Probability on trees and networks, (2017), Cambridge University Press
[14] Pitman, J.; Tang, W., Tree formulas, mean first passage times and kemenys constant of a Markov chain, Bernoulli, 24, 3, 1942-1972, (2018) · Zbl 06839256
[15] D. Wilson, 1996. Generating random spanning trees more quickly than the cover time. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pp. 296-303. · Zbl 0946.60070
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.