--- title: "Biased random walks on small-world networks" date: 2026-09-08 version: "0.1.0-candidate" doi: 10.5281/zenodo.22663470 pdf: https://github.com/ipitchford/biased-small-world-mixing/releases/download/v0.1.0-candidate/biased-small-world-mixing-0.1.0-candidate.pdf repository: https://github.com/ipitchford/biased-small-world-mixing archive: https://zenodo.org/records/22663470 license: CC0-1.0 status: unrefereed (internally replayed; not peer reviewed, not independently reproduced, not formally verified) --- # Biased random walks on small-world networks ## Summary Adding shortcuts to a ring makes distant places closer, but a random walker can still take a long time to forget its starting point. This candidate asks whether a fixed preference for moving in one direction changes that. The written proof gives logarithmic mixing in the denser shortcut regime and square-root mixing up to polylogarithmic factors in the sparser one. It covers four explicitly specified ways of measuring time, including a nonlazy discrete walk. These are fixed-weight results, not a theorem about every way of adding drift. The release is an unrefereed candidate. ## Summary for specialists Fix $\epsilon>0$ and $u>v>0$ independently of $n$. Add each undirected noncycle pair independently with probability $p$, give forward and reverse cycle edges weights $u,v$, and give shortcuts unit weight. The candidate claims, with high probability over the graph, worst-start total-variation mixing at tolerance $1/4$: $$ p=\epsilon/n:\quad t_{\rm mix}=\Theta(\log n), $$ $$ p=\epsilon n^{-3/2}:\quad c\sqrt n\log n\le t_{\rm mix}\le C\sqrt n(\log n)^{18}. $$ The four clocks are the fixed-edge-rate generator $Q$, the rate-one generator $D^{-1}Q$, the lazy kernel $(I+J)/2$, and the nonlazy kernel $J=I+D^{-1}Q$, where $D_{ii}=u+v+d_i$. The invariant law is uniform for $Q$ and proportional to $D_{ii}$ for the other clocks. “Dense” means the denser regime, still with bounded average shortcut degree. The sparse logarithmic exponent is deliberately loose. ## Technical account The proof separates four obstacles that a shortcut-endpoint calculation alone cannot resolve. 1. **Random spacing:** evenly spaced endpoints can retain a slow phase mode. In the sparse graph, geometric-gap conditioning and adaptive phase bounds supply coercivity across the relevant frequency windows. 2. **Physical time:** crossing duration and destination are dependent. The dense proof controls their joint characteristic kernel, removes the zero-duration atom before inversion, and retains only a stationary second-moment assumption. 3. **Worst starts:** a small average distance does not control exceptional vertices. A simultaneous bound for connected endpoint sets and a clock-potential estimate provide the separate upgrade. 4. **Parity:** continuous-time mixing does not automatically de-lazify a walk. Signed crossing kernels and negative-side resolvents address the nonlazy obstruction. Trace elimination, resolvent factorisation, Fourier inversion and configuration-model simplicity are established ingredients. The candidate contribution is their model-specific synthesis into the displayed physical, worst-start bounds, not a claim that those elementary identities are new. ## Evidence, assurance and limitations The seven-page entry-point paper identifies the complete dependency chain; the archive contains the detailed proof modules. Exact rational programs check finite traces, crossing moments, flux identities and resolvent factorizations. Normal, optimised and fresh-extraction replay is supplemented by three deliberately corrupted implementations that the checker rejects. Those tests do not certify high-probability graph estimates or the asymptotic theorem. The supplied review and five-role producer-coordinated editorial assessment are documented at their actual scope. Unaffiliated specialist validation, formal verification and historical priority remain unestablished. Fixed weights, nonvanishing bias and the sparse polylogarithmic gap are substantive limitations. No performance benefit in deployed networks is measured. ## Relationship to earlier work The reversible Newman–Watts benchmark has logarithmic-squared mixing. Earlier sparse-cycle bounds, directed-cycle spectral estimates, fixed-shortcut-count theorems and average-start results answer related but different questions. The package compares their models, clocks and starting-state quantifiers explicitly. In particular, a theorem with a fixed number of shortcuts cannot simply be evaluated at a shortcut count growing with the network. ## Who should care, and why | Audience | Potential use | Required caution | |---|---|---| | Probability researchers | Inspect physical-time and worst-start bridges for a nonreversible random graph | The complete asymptotic proof still needs unaffiliated scrutiny | | Markov-chain method developers | Test the reusable renewal and parity arguments in other settings | Verify every contraction, moment and clock hypothesis anew | | Research software reviewers | Reproduce finite identities and challenge checker semantics | Finite replay is not theorem certification | ## Why the problem matters Graph distance and endpoint expansion are tempting proxies for mixing, but they can miss timing, dependence and parity. This candidate makes those missing steps explicit. Its potential value lies in a checkable route from a random network to the behaviour of the actual walk, rather than a spectral calculation alone. ## How to inspect or reproduce the recorded checks Download the exact versioned ZIP and its separate replay companion. From a fresh extraction, run `python3 package.py --verify`, then `verify_trace.py`, `verify_nonlazy.py` and `semantic_controls.py`, both normally and with `python3 -O`. The exact checks require only the Python standard library; the producer used Python 3.14.7 and hosted CI checks Python 3.12. The optional NumPy diagnostic is floating-point exploration, not part of the exact evidence. ## The most valuable next projects First reconstruct the dimension-uniform renewal estimate, adaptive phase bound and simultaneous connected-set bound independently. Then investigate whether the sparse logarithmic gap can be reduced. Extensions to vanishing drift or different weights are new problems with new hypotheses, not already established applications. ## What is in the evidence package The release includes the formatted paper and source, complete Markdown proof modules, a cross-file notation guide, a theorem-level literature comparison, exact checkers and mutation controls, claim and assurance records, internal editorial reports and responses, licences, a manifest and a separate hash-bound fresh-replay receipt. GitHub and Zenodo carry the same declared release bytes. ## Open directions for follow-up research - Obtain unaffiliated scrutiny of the dimension-uniform renewal, adaptive phase and connected-set estimates. - Reduce the sparse logarithmic gap without changing the fixed-weight model. - Investigate vanishing drift or other weights as new problems, not consequences of this theorem. - Determine the reach of the renewal and clock-potential lemmas in other graph models. ## Research process, metrics and reusable methods This is prospective process metadata under the Evidence Press operating model and research-metrics policy. It records the intended handoff, measured scope and claim boundary; it is not evidence that the method accelerated this work. - Work ID: ep-work:biased-small-world-mixing - Attempt and metric receipts: ep-attempt:biased-small-world-mixing-assurance-publication: published / positive; scope assurance-through-publication; target Pass five-role editorial review and deterministic checks, publish exact GitHub/Zenodo assets and complete guarded Evidence Press readback.; active forecast 150 minutes (120-210); Fermi components Package and PDF checks: 1 x 35/35/50 minutes low/central/high (Existing modular analytic proof and standard-library exact tests; minor review revisions and new PDF packaging.); Five-role editorial review: 1 x 25/30/45 minutes low/central/high (One bounded round.); Archives, page and media: 1 x 35/50/65 minutes low/central/high (Established scripts and authenticated services.); Guarded public readback: 1 x 25/35/50 minutes low/central/high (Composite gates and CI.); positive-signal/closure probabilities 0.8/0.8 within 300 active minutes; observed active-agent/human/compute/wait/blocked/rework minutes 20/unknown/unknown/0/0/0; cycles positive/negative/inconclusive 0/0/0; falsification gates 3; architectures tested/rejected 1/0; result target-closed; target reached true; forecast error -130 minutes; ratio 0.13333333333333333; inside interval false; positive-signal/target-closure Brier scores 0.04/0.04; missing telemetry activeHumanMinutes: Human effort was not instrumented.; computeMinutes: Substantive compute time was not separately metered.; appended measurement corrections measurement.agentRuns -> metrics.outcome.agentRuns: Opening 1 retained; terminal 5. (reason: Preserve opening root-only snapshot; terminal total includes four completed internal editorial agents.). Work ledger: https://evidencepress.org/api/work-ledger.json. Metrics policy: https://evidencepress.org/api/research-metrics-policy.json - Intended aims: science - Artifact roles: research-output, evidence-assessment, communication - Decision object: bound — Two-regime worst-start mixing bounds under four fixed-weight clocks. Scope: Biased cycle with independent noncycle unit shortcuts and fixed positive directional bias. - Reusable methods: Structural compression (structural-compression); Exact regime stitching (regime-stitching); Adversarial scientific controls (adversarial-controls); Assurance as a vector (assurance-vector); Agent-readable research objects (agent-readable-research-object). Registry: https://evidencepress.org/api/method-registry.json - Targeted clocks: assurance, publication - Semantic bridge: explicit — Trace expansion is bridged to physical mixing using random gaps, joint durations, a worst-start potential and parity control. Remaining risks: Written asymptotic argument awaits external scrutiny.; Finite matrix replay cannot certify graph-uniform estimates.; Priority remains bounded uncertainty.. - Human judgement gates: Audit dimension-uniform estimates and graph conditioning.; Keep physical clocks and starting-state quantifiers separate.; Assess historical priority and significance separately.; Preserve rights, creator and assurance boundaries. - Next assurance action: Obtain unaffiliated proof reconstruction and separately implemented finite checks. - Claim ceiling: Unrefereed candidate proof for four fixed-weight clocks. Sparse bounds differ by polylogarithmic factors. No vanishing drift, arbitrary kernel, historical priority, external specialist validation, formal verification or impact claim. - Aim-scoped impact evidence: - science: NO_IMPACT_EVIDENCE — Inspectable small-world mixing candidate and renewal statement in Producer-coordinated mathematical publication; design none; comparator No matched comparator.; estimand No speed or impact effect estimated.; no real-world effect evidence asserted ## Verification status Unrefereed candidate proof for four fixed-weight clocks. Sparse bounds differ by polylogarithmic factors. No vanishing drift, arbitrary kernel, historical priority, external specialist validation, formal verification or impact claim. ## References 1. Addario-Berry and Lei, The mixing time of the Newman-Watts small-world model (2015): reversible lazy benchmark. 2. Gerencsér, Mixing times of Markov chains on a cycle with additional long range connections; arXiv v3, Theorems 23–24. 3. Gerencsér and Hendrickx, Improved mixing rates of directed cycles with additional sparse interconnections (2023). 4. Feng and Gerencsér, Mixing on the cycle with constant size perturbation (2026): fixed shortcut count. 5. Espuny Díaz, Morris, Perarnau and Serra, Speeding up random walk mixing by starting from a uniform vertex (2024). 6. Janson, The probability that a random multigraph is simple (2009).