Can Stationary Distributions of Conditioned Directed Graphs Be Approximated in Small Space?

κ-Conditioning Pins Down Both Mixing and Stationary Mass

The algorithm does not work on arbitrary directed graphs. It requires the walk matrix W to be κ-conditioned, which bundles two separate promises. First, the stationary distribution s(W) must be close to uniform: 1/(κn) ≤ s(W)_i ≤ κ/n for every vertex i. Second, the chain must be κ-mixing, meaning every entry of W^κ differs from the rank-one matrix s(W)1ᵀ by at most n⁻¹⁰.

Those two conditions do different jobs. The stationary-mass bound keeps the target vector from concentrating on a few vertices, so relative error is a meaningful target. The mixing bound guarantees that after κ steps the walk has forgotten its start, which is what lets the construction replace long walks with a short, well-behaved matrix chain. The paper treats this setting as an intermediate problem on the way toward the open question of whether randomized logarithmic space equals deterministic logarithmic space.

The Space Bound Depends on log²κ, Not on Walk Length

Theorem 1.1 states that for every fixed constant c > 0 there is a deterministic algorithm that, given n, an integer 1 < κ ≤ n, and adjacency-list access to an n-vertex constant-degree out-regular directed graph whose walk matrix is κ-conditioned, outputs estimates ŝ₁, …, ŝₙ satisfying |ŝᵢ − s(W)ᵢ| ≤ n⁻ᶜ s(W)ᵢ for every vertex i, using O((log n + log²κ) log log n) bits of work space.

The error is relative, not additive: each estimate is compared against that vertex's own stationary probability, scaled by n⁻ᶜ. The space cost is dominated by log n and log²κ, multiplied by a log log n factor. When log κ ≤ √log n, the bound collapses to O(log n log log n), the same order as the Eulerian walk-estimation result the paper builds on. The dependence on κ is what separates this result from algorithms for general directed graphs, where the walk length enters the space bound directly.

The Improvement Applies Only in a Specific κ Regime

The comparison the paper draws is with the best-known bound for approximating κ-step random walks in general directed graphs, due to Hoza (RANDOM 2021), which uses O(log n √log κ / √log log n) space. The new bound improves on that only in the regime κ = exp(Θ(log^α n)) for any α in (0, 2/3).

Outside that regime the comparison does not automatically favor the new algorithm, and the paper does not claim it does. The gain also comes with added assumptions: the general-graph algorithms of Saks–Zhou and Hoza apply without any mixing or stationary-distribution promise, whereas this result requires both halves of κ-conditioning. The paper states this trade-off explicitly, so the improvement should be read as conditional on the graph satisfying the κ-conditioned promise, not as a general speed-up for directed graphs.

Trimming Keeps Row Mass Bounded During Squaring

The construction combines derandomized squaring with a trimming process. Derandomized squaring repeatedly replaces the walk matrix with a lifted, expander-averaged square, which drives the approximation error down geometrically across levels. The problem is that the ℓ₂-style approximation error does not control row sums: the in-degree mass of the squared matrix can blow up, and once it does, plain derandomized squaring fails.

Trimming fixes this by deleting mass from rows that exceed a budget and returning the deleted mass to the diagonal, which preserves column stochasticity. The one-dimensional analysis shows the trimmed matrix keeps row mass bounded by (α + β)1 and introduces only a bounded one-sided error. The paper's stated difficulty is that trimming naively needs squared logarithmic space because it runs over many rounds; the authors address this by trimming only partially and synchronizing the squaring and trimming steps, which is what brings the overall space back down.

Stabilization Takes O(log_κ n + log κ) Rounds

The two-dimensional chain is analyzed through a stabilization round r_max, the smallest round after which every level's raw, deletion, and trimmed matrices stop changing. Lemma 5.4 bounds this by O(log_κ n + log κ). A conservative argument first gives O(log n log κ) rounds by showing that heavy rows shrink by a factor of κ per round until none remain.

The sharper bound comes from a recurrence on the number of unstable rows, u(t, r) ≤ poly(κ, log n) u(t−1, r) + κ⁻¹ u(t, r−1), with initial condition u(t, 0) ≤ n|L_t|. Solving it yields u(t, r) ≤ n(4K)^t κ^{−r/2}, which drops below one at every level once r exceeds roughly 2 log_κ n plus a term in log κ. This round count is what feeds the final space accounting: the recursion depth is O(log n + (T + r_max)h), and substituting T = O(log κ) and the stabilization bound produces the O((log n + log²κ) log log n) total.

Walk Probabilities Follow Through an Eulerian Reduction

Corollary 1.2 extends the stationary result to individual walk probabilities. Given vertices i and j and an integer 1 ≤ k ≤ poly(n), it outputs an estimate p̂ with |p̂ − (W^k)_{ij}| ≤ n⁻ᶜ, using the same O((log n + log²κ) log log n) bits of work space.

The reduction works by reweighting. The approximate stationary vector ŝ is used to build an imbalance vector b = Wŝ − ŝ, and a correction term is added to form a weighted adjacency matrix F whose row sums and column sums coincide, making it Eulerian. The perturbation between the resulting transition matrix and W is bounded by 8δ in the ℓ₁ norm, and telescoping over k steps keeps the total walk-probability error within budget. The Eulerian walk-estimation algorithm of Ahmadinejad et al. then supplies the estimate. Note that this corollary inherits the κ-conditioned assumptions of Theorem 1.1; it is not a statement about arbitrary directed graphs.

The Preliminary Release Limits What Can Be Checked

The paper is released as a preliminary version, and the author states the reason directly: recent rumors of LLM-based progress on related problems and uncertainty about when those results may appear. The author also notes that further implementation details will be provided in a subsequent version, so the current text should be read as a statement of the algorithmic ideas and their analysis rather than a fully specified implementation.

The LLM usage statement records that on September 7 the author prompted GPT-6 Astra with the main theorem statement and initial proof ideas, and that the model provided key algorithmic ideas including the trimming process and the synchronized analysis. The manuscript was developed by the author based on his own interpretation of the resulting algorithm, with assistance from GPT Codex and Devin.AI in checking, reformatting, drafting, and revising portions of the exposition and proofs. For a reader weighing the result, the practical consequence is that the space bound and the improvement regime are the parts to scrutinize against the proofs, while implementation-level claims remain deferred.

The Decisive Question Is Whether κ-Conditioning Holds

The most useful way to read this paper is as a conditional trade. If a directed graph satisfies both halves of κ-conditioning — stationary probabilities within a factor κ of uniform, and κ-step mixing to within n⁻¹⁰ entrywise — then the stationary distribution is approximable to inverse-polynomial relative error in space that grows with log²κ rather than with the walk length. If the graph does not satisfy those promises, the result does not apply, and the relevant comparison returns to the general directed-graph bounds.

Within the κ-conditioned setting, the specific threshold to check is the regime κ = exp(Θ(log^α n)) with α in (0, 2/3). That is where the new O((log n + log²κ) log log n) bound beats the O(log n √log κ / √log log n) bound for κ-step walks in general directed graphs. The paper's own framing places the result as an intermediate step toward resolving whether randomized logarithmic space equals deterministic logarithmic space, so the value of the improvement should be judged by whether a given application's graphs actually fall inside that κ regime.

Sources used in this answer