PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficiency--Complexity Tradeoff and Constrained Percolation

Yuliy Baryshnikov, Efe Onaran

arXiv:2610.33864v1math.PRcs.SYeess.SYmath.COq-bio.NC

TL;DR

The paper asks how route efficiency trades off against the representational complexity of constrained path choices. It models this tradeoff with directed first-passage percolation and path-family counts. Under stated assumptions, it establishes deterministic limiting costs, including an entropy-parameterized cost jointly continuous in entropy and direction on its domain.

  • Problem

    The paper studies how physical route cost trades off against the computational resources needed to represent and search a constrained set of paths.

    Source: §1.1 · p. 2, §1.2 · p. 2

  • Method

    It models physical cost by minimum edge-weighted path cost and representational complexity by the growth of constrained path families in directed first-passage percolation.

    Source: §1.2 · p. 2, §1.3 · p. 2, §2 · p. 3

  • Results

    The entropy-parameterized time constant exists almost surely and is jointly continuous in entropy and direction on the corresponding domain for the stated nested families and generating-function conditions.

    Source: §5.3 · pp. 14–15

  • Takeaways & Limitations

    Path-family growth supplies a parameterization linking representational complexity to limiting physical cost within the stated framework.

    Source: §1.2 · p. 2, §1.3 · p. 3

    The results concern directed paths in the nonnegative orthant with nonnegative i.i.d. edge weights having finite second moment, plus feasibility and, for entropy results, additional nested-family generating-function conditions.

    Source: §1.3 · p. 2, §3.2 · p. 6

Abstract

from arXiv · show

We study the efficiency--complexity tradeoff for resource-limited agents through directed first-passage percolation. Nonnegative i.i.d. edge weights represent physical energy expenditure, while the logarithmic size of a constrained path family measures representational complexity. For translation-invariant families, a path-joining property yields deterministic large-distance costs in rational directions and joint convexity in constraint parameter and direction, under suitable moment and feasibility assumptions. Our main result concerns the limiting cost parameterized by path-family entropy. Using techniques from analytic combinatorics in several variables (ACSV), we establish its almost-sure existence and joint continuity in entropy and direction for nested families satisfying additional generating-function conditions, on the corresponding entropy range. Path-count asymptotics supply the change of parameter linking this cost to the constraint-parameterized cost. Two planar examples constrain the number of turns or the number of East-runs of length at least two.

1. Introduction

The paper frames constrained route choice as a tradeoff between physical cost and the representational resources needed to search candidate paths. It develops a directed first-passage percolation framework and states results for deterministic costs, convexity, and entropy-based costs under specified assumptions.

1.1. Motivation.

  • The motivation connects energetic and information-processing constraints to navigation, cognition, and other biological and engineered settings.Examples include animal migration and foraging, spatial cognition, and autonomous robotics and motion planning.Source: §1.1 · pp. 1–2

1.2. Goals.

  • Larger admissible path sets can improve the best route while increasing the information needed to represent and search those paths.The paper treats path-family size as a measure of computational complexity, with approximately log2 N bits needed to specify one of N trajectories.Source: §1.2 · p. 2

1.3. Outline of Results.

  • The model uses nonnegative i.i.d. edge weights for physical energy and logarithmic path-family size for representational complexity.Its stated assumptions include finite second moments and eventual feasibility along each nonzero nonnegative lattice ray.Source: §1.2 · p. 2, §1.3 · p. 2
  • Under the stated assumptions, the paper proves deterministic time constants in rational directions and joint convexity in constraint parameter and direction.For nested feasible filtrations it also establishes a jointly continuous, concave path-count growth rate.Source: §1.3 · pp. 2–3
  • For nested families meeting additional generating-function conditions, entropy parameterizes a limiting cost that is jointly continuous in entropy and direction on its domain.The paper verifies the framework for planar restrictions on turns and on East-runs of length at least two.Source: §1.3 · p. 3

2. A Toy Model

The toy model casts route choice through a layered environment as finding the least-cost path among available options. It uses branching random walk results to describe how the number of options relates to the limiting cost.

2. A Toy Model

  • The agent seeks the least-cost route from layer 0 to layer n through a tree with edge durations that are positive i.i.d. random variables.The toy setup illustrates that the number of options at each step depends on the agent’s computational resources.Source: §2 · p. 3
  • The minimum cost over paths from layer 0 to layer n is the optimization objective, with each edge carrying an i.i.d. duration.The caption’s example uses n = 3 and branching factor b = 2; the red path is the assumed least-cost path.Source: §2 · p. 3, Figure 2.1 · p. 4
  • The Biggins–Hammersley–Kingman theorem gives an almost-sure deterministic limiting cost depending on the branching factor and edge-duration distribution [3,4,6].The stated heuristic counts paths whose total duration is at most nµ.Source: §2 · p. 3
  • As the branching factor b grows, the limiting cost µ decreases, matching the text’s interpretation that more computational resources yield better solutions.For unit-mean exponential edge costs, the text also gives a cumulant-generating-function characterization and an asymptotic expansion in b^-1.Source: §2 · pp. 4–5

3. Main Model

The main model restricts directed first-passage percolation to translation-invariant families of permissible paths. Constraints represent limits on computational affordances, while path counts and constrained passage costs track complexity and physical cost.

3.1. Percolation.

  • The model assigns i.i.d. nonnegative weights with finite first and second moments to nearest-neighbor edges of the lattice.It considers directed paths in the nonnegative orthant and compares permissible paths from y to z > y.Source: §3.1 · p. 5, §3.2 · p. 6

3.2. Constrained Percolation.

  • A constrained distance is the minimum passage cost among permissible paths between the specified endpoints.Path families are translation invariant when translating a path and its endpoints by a lattice vector preserves membership.Source: §3.2 · p. 6
  • The constraint parameter models computational affordances: allowing more paths improves the available route but requires more resources to explore them.For fixed endpoints, constrained passage cost measures physical cost, while log2 of the number of permitted paths measures representational complexity.Source: §3.2 · p. 6, §3.3 · p. 7
  • A filtration combines translation invariance with a path-joining property that preserves permissibility at the length-weighted average constraint parameter.Feasibility requires that paths exist eventually along each nonzero nonnegative lattice ray.Source: §3.2 · pp. 6–7

3.3. Examples.

  • The examples constrain either the number of turns or the number of maximal East-runs of length at least two.Turn counts are almost subadditive because concatenation can add at most one turn; East-run counts can likewise increase by at most one at the join.Source: §3.3 · pp. 7–8

4. Limits for Filtrations

For feasible path filtrations, the paper establishes large-distance costs and then derives convexity in the constraint and direction variables. The convexity result extends to continuous directions on the stated domain.

4.1. Subadditive Ergodic Theorem.

  • The existence proof applies Liggett’s subadditive ergodic theorem to constrained passage costs along integer multiples of a rational direction.The proof checks subadditivity, finite expectation, and stationarity and ergodicity using feasibility, translation invariance, and edge-weight symmetry.Source: §4.1 · pp. 8–9

4.2. Convexity.

  • The time constant is jointly convex in constraint parameter and direction for feasible families in the filtration.The lemma states the inequality for rational directions and rational mixing weights.Source: §4.2 · p. 10
  • The time constant has a unique continuous extension from rational directions to nonnegative real directions of unit norm.The text derives continuity from a local estimate for convex functions and the bound 0 ≤ µC ≤ Eτ.Source: §4.2 · p. 11
  • The convexity statement also yields convexity separately in the constraint parameter and in direction.The text obtains these cases by setting the directions equal or the constraint parameters equal, respectively.Source: §4.2 · p. 11

5. Reparameterization by the class size

The section reparameterizes path costs by family size, showing that the constraint-parameterized cost function g is strictly concave and increasing and connects it to the entropy-indexed time constant. Under additional conditions, it establishes the time constant’s existence and joint continuity in entropy and direction.

5.1. Entropic Parameterization.

  • Entropy parameterization indexes permissible paths by the size of their path families, and its resulting class need not be a filtration.Consequently, the preceding results for filtrations do not directly apply to this class.Source: §5.1 · p. 12

5.2. Analytic Combinatorics in Several Variables.

  • The ACSV framework derives path-count asymptotics from generating-function properties, with the main results assuming rational generating functions and suitable smooth minimal critical points.The paper calls a path class nice when its generating function is rational and the specified directional critical points are smooth and minimal.Source: §5.2 · pp. 12–14

5.3. Entropy–Cost Tradeoff.

  • For a nice nested feasible filtration, the entropy-parameterized time constant exists and is jointly continuous in entropy and rational direction on the stated domain.The domain consists of ζ ∈ g(Γ_q, q), for directions q ∈ Q^d with |q| = 1.Source: §5.3 · p. 14
  • For nested feasible filtrations, the path-count growth rate extends to a finite, continuous, concave, one-homogeneous function, and positive critical points evaluate that rate for nice classes.Nestedness also extends the path-count limit from rational to real constraint parameters.Source: §5.3 · pp. 15, 17

5.3. Entropy–Cost Tradeoff

  • Equality (5.4), first established for rational R0, extends to real R0 by continuity of the finite concave functions on the open positive cone.Source: §5.3 · p. 18
  • For a nice nested feasible filtration, g(γ, q) is strictly concave and strictly increasing in γ on Γq.Nestedness makes g non-decreasing, and strict concavity yields strict increase.Source: §5.3 · pp. 18–19
  • Setting ζ = g(γ, q) gives the parameter exchange between the time constants of the entropy-parameterized family H and the filtration C.The resulting identity is µH(ζ, q) = µC(g−1(ζ, q), q).Source: §5.3 · p. 19
  • The entropy-indexed time constant µH(ζ, q) is jointly continuous in entropy and direction on the stated domain.The proof uses continuity of g−1 and the identity relating µH to µC, which is jointly continuous.Source: §5.3 · p. 19

6. Examples

The examples verify the generating-function conditions for two planar path constraints: limiting turns and counting East-runs of length at least two. Both yield nice path classes, with convergence regions that differ because the two constraints permit different paths when the count is zero.

6.1. Constrained by Number of Turns.

  • The turn-constrained path class has a rational generating function and satisfies the paper’s nice-path-class conditions.The constraint counts turns.Source: §6.1 · pp. 20–21

6.2. Consecutive Runs.

  • The consecutive-East-run constraint also has a generating function and defines a nice path class for each rational direction q in (0, 1), with some positive feasible range ι(q).The counted runs have length at least two.Source: §6.2 · p. 22
  • The convergence-region comparison reflects different zero-count path families: zero turns permits only straight paths, while zero counted East-runs permits paths without consecutive East steps.For fixed 0 < y, z < 1, sufficiently small x > 0 gives convergence for turns; for East-runs this holds exactly when z(1 + y) < 1.Source: Figure 6.2 · p. 23
  • The point (u−, v−1, v−2) is the unique smooth critical point with positive real entries, provided u− ≠ 1.For q = 1/2, the expressions are positive for γ < 1/4.Source: §6.2 · p. 24

7. Conclusion

The conclusion presents constrained directed first-passage percolation as a model linking physical path cost with path-family complexity. Under the stated conditions, it establishes deterministic costs, convexity, and an entropy-parameterized cost that is jointly continuous in entropy and direction.

7. Conclusion

  • The model defines physical cost as minimum total edge cost over constrained directed paths and representational complexity through growth of the admissible path family.The path-joining property supports deterministic large-distance costs, convexity, and a concave path-count growth rate under the stated assumptions.Source: §7 · p. 25
  • For classes meeting additional generating-function conditions, path-count growth parameterizes the limiting cost, which is jointly continuous in entropy and direction on the corresponding domain.Source: §7 · p. 25
  • A next problem is to quantify the cost penalty of path restrictions and how it changes as turn or run constraints are relaxed.The conclusion also proposes extensions incorporating more realistic biological constraints.Source: §7 · pp. 25–26

AI tool disclosure

The disclosure describes the second author’s use of language models during mathematical and editorial work. The authors state that suggestions were reviewed and that they take responsibility for the final mathematical content.

AI tool disclosure

  • The second author used OpenAI’s large language models through Codex to review arguments, develop and simplify proofs, check calculations, and revise exposition and source.Source: AI tool disclosure · p. 26
  • The second author reviewed and revised AI-generated suggestions.Source: AI tool disclosure · p. 26
  • The authors take responsibility for the mathematical content and final text.Source: AI tool disclosure · p. 26
Loading 2610.33864v1…