Abstract
This paper introduces a novel algorithm for calculating "escape probabilities" in random walks on graphs with high precision. By utilizing floating-point arithmetic and a recursive Schur complement approach, the authors achieve multiplicative (entrywise) error guarantees. This allows for the accurate computation of even exponentially small probabilities in $\tilde{O}(n^3)$ bit operations, addressing a significant limitation of traditional norm-wise solvers in the high-precision regime.
Introduction
Imagine a random walk on a graph starting at vertex $s$. A fundamental question in Markov chain theory is determining the "escape probability": the probability that the walk hits a target vertex $t$ before it hits a set of boundary vertices $P$. This problem is central to understanding graph connectivity, electrical networks, and various randomized algorithms.
The primary challenge in computing these probabilities is that they can often be exponentially small (e.g., $2^{-n}$). Standard linear solvers—including the well-known near-linear time Laplacian solvers—typically provide "norm-wise" error guarantees. In such cases, the error is small relative to the largest entry in the solution vector. If the target probability is $10^{-20}$ and the norm-wise error is $10^{-5}$, the resulting value is essentially noise. To obtain a meaningful answer for such tiny values using traditional methods, one would need $n$ bits of precision, causing the "bit complexity" (the actual computational work) to explode.
The Problem of Exponential Decay
Figure 1: A graph structure where the escape probability from $s$ to $t$ (avoiding $p$) decays exponentially with the path length. Source, p. 4
As illustrated in the figure above, certain graph structures naturally lead to these vanishingly small probabilities. In a path-like graph where every node is also connected to a "sink" node $p$, the probability of traversing the entire path to reach $t$ without hitting $p$ decreases geometrically. Traditional solvers fail to distinguish these values from zero unless the precision is set extremely high.
Methodology
The authors move away from fixed-point arithmetic and "real-RAM" models to use floating-point arithmetic, which is better suited for handling numbers across vastly different scales. Their primary tool is a recursive algorithm called RecInvert.
Key Technical Components:
- Schur Complements: The algorithm decomposes the matrix recursively. Unlike standard Gaussian elimination, which may involve subtractions that destroy precision in floating-point (catastrophic cancellation), this method leverages the structure of Row Diagonally Dominant L-matrices (RDDL) to ensure numerical stability.
- Multiplicative Error Guarantees: The method ensures that the computed value $Z_{ij}$ is within an $e^\epsilon$ factor of the true value, rather than just an additive offset.
- Matrix-Tree Theorem: The authors use a combinatorial approach to prove the stability of their inversion method, linking the entries of the matrix inverse to the weighted counts of spanning trees in the graph.
- Repeated Squaring: For graphs with weights in a polynomial range, a simpler algorithm based on the power series of the transition matrix is provided, which is more efficient for practical implementation.
Key Insights and Results
A major contribution of this work is the distinction between bit complexity and arithmetic complexity. While some algorithms might run in $O(m \log^c n)$ arithmetic operations, they may require a massive number of bits per operation to maintain accuracy for small values, making them slower in practice for this specific problem.
Theorem 1.1
The authors present an algorithm to compute escape probabilities for all starting vertices within a multiplicative factor of $e^\epsilon$ in $\tilde{O}(n^3 \cdot (L + \log \frac{1}{\epsilon}))$ bit operations, where $L$ is the number of bits in the input.
This $\tilde{O}(n^3)$ bit complexity outperforms previous state-of-the-art methods like Spielman-Teng or fast matrix multiplication, which would require roughly $O(mn^2)$ or $O(n^{\omega+1})$ bit operations respectively to achieve the same entrywise accuracy.
Limitations and Future Work
While $\tilde{O}(n^3)$ is an improvement in bit complexity for high-precision regimes, it remains slower than near-linear time in terms of raw arithmetic operations. Achieving entrywise precision in near-linear time is a significant open challenge. Additionally, the current results are tailored to RDDL matrices; extending these guarantees to more general linear systems or directed graphs is a potential area for future research. Finally, empirical benchmarks against standard numerical libraries like LAPACK would help identify the practical crossover points where this specialized algorithm becomes superior.
Summary updated