Given a finite graph $G$, and three vertices $v,s,t$, I am wondering about the probability that simple random walk starting at $v$ will reach $s$ before it reaches $t$. I know this is equal to $\phi(v)$, where $\phi$ is the unique harmonic function on $G$ with boundary $\{s,t\}$ such that $\phi(s) = 1,\phi(t) = 0$. Alternatively, if treat $G$ as an electric network, where current flows into $s$ and out from $t$, we get that $\phi(v)$ is the voltage at $v$.
Is a way to interpret $\phi(v)$ in terms of spanning tree counts? In practice, what are efficient ways to calculate/approximate $\phi(v)$ with a program?
Let $G*$ denote $G$ with an additional edge $e$ connecting $s$ to $t$. Denote by $A$ the collection of spanning trees in $G*$ that contain $e$. Then the voltage $\phi(v)$ is the fraction of trees in $A$ that contain a path from $v$ to $s$ that does not include $e$. This follows from the property of the uniform spanning tree in $G$ with $s,t$ identified, that the random path from $v$ to the conjoined vertex $\{s,t\}$ in the tree is obtained by a loop-erased walk; This result is due to Pemantle, extended by Wilson; see an exposition and detailed references in Chapter 4 of [1].
Let $n$ denote the number of vertices in $G$. While $\phi(v)$ can be estimated via random sampling, and also by relaxation methods the most efficient methods rely on $\phi(\cdot)$ being the unique solution of $n-2$ equations in $n-2$ unknowns. These equations reflect the harmonicity of $\phi$ at all nodes different from $s,t$. There are many linear systems solvers available online. The equations that arise here have a special nature, they are often sparse and specialized algorithms have been developed for them. See e.g. [2] for a masterful 2010 survey and [3] for a more recent algorithm.
[1] Lyons, Russell, and Yuval Peres. Probability on trees and networks. Vol. 42. Cambridge University Press, 2017. Available from
https://rdlyons.pages.iu.edu/prbtree/
[2] Spielman, Daniel A. "Algorithms, graph theory, and linear equations in Laplacian matrices." In Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II–IV: Invited Lectures, pp. 2698-2722. 2010.
[3] Kyng, R., Lee, Y.T., Peng, R., Sachdeva, S. and Spielman, D.A., 2016, June. Sparsified cholesky and multigrid solvers for connection laplacians. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (pp. 842-850).