pith. sign in

arxiv: 2604.23379 · v1 · submitted 2026-04-25 · 🧮 math.CO

Average Steps until Absorption on Random Walks on Sea Dragon Trees

Lillian Ates , Zachary Chapman , John Estes , Tyler Jackson This is my paper

Pith reviewed 2026-05-08 07:36 UTC · model grok-4.3

classification 🧮 math.CO
keywords sea dragon treesaverage steps until absorptionrandom walksMarkov chainsabsorbing stateshitting timestreesgraph theory
0
0 comments X

The pith

Markov chains yield exact closed-form expressions for average steps to absorption from every vertex on several classes of sea dragon trees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines the average steps until absorption t(G,v,u) as the expected number of steps a random walk on graph G takes to reach a designated absorbing vertex u starting from v. It introduces sea dragon trees as those with a unique path containing every vertex of degree three or higher. Applying the standard equations of absorbing Markov chains to these trees produces explicit formulas for t(G,v,u) across all vertices in multiple families of sea dragons. A reader would care because these formulas supply exact expected hitting times on an infinite family of trees for which no general closed forms were previously available. The work also records several relations that hold for ASUAs on arbitrary graphs.

Core claim

For a sea dragon tree G with distinguished path P and chosen absorbing vertex u, the quantity t(G,v,u) equals the corresponding entry in the fundamental matrix of the absorbing Markov chain obtained by making u absorbing and all other states transient; this matrix is solved explicitly for all vertices v in several parametric families of sea dragons, and auxiliary equations relating ASUAs on general graphs are derived from the same linear system.

What carries the argument

The fundamental matrix of the absorbing Markov chain with sole absorbing state u, whose entries directly give the vector of expected absorption times from each transient vertex.

If this is right

  • Closed-form ASUA values are now available for every vertex in multiple infinite families of sea dragon trees.
  • The same Markov-chain setup produces auxiliary equations that relate absorption times between any pair of vertices on a general graph.
  • The method scales uniformly to all vertices once the tree is identified as a sea dragon.
  • Results on general graphs supply identities that any ASUA computation must satisfy regardless of tree shape.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The formulas could be used to benchmark numerical solvers for hitting times on larger trees that are approximately sea-dragon shaped.
  • Similar path-constrained trees might admit analogous closed forms if their degree restrictions are relaxed slightly.
  • The general equations could be applied to compute absorption times in non-tree graphs that contain a sea-dragon subgraph as a core.
  • Testing the formulas against Monte Carlo simulations on randomly generated sea dragons would provide an independent check.

Load-bearing premise

That the sea dragon trees admit exact closed-form solutions from the ordinary linear equations of absorbing Markov chains without further restrictions on the walk or the tree structure.

What would settle it

Solve the linear system for expected absorption times on a concrete small sea dragon tree with three or four vertices off the main path and compare the numerical values to the closed-form expression claimed for that family; any discrepancy falsifies the exactness claim.

Figures

Figures reproduced from arXiv: 2604.23379 by John Estes, Lillian Ates, Tyler Jackson, Zachary Chapman.

Figure 1
Figure 1. Figure 1: A maze and accompanying graph Such a maze is represented as a simple, undirected graph G = (V, E) with a vertex at each grid coordinate as pictured in view at source ↗
Figure 2
Figure 2. Figure 2: Introductory Example Graph G D =      1 2 0 0 0 0 0 1 2 0 0 0 0 0 1 3 0 0 0 0 0 1 2 0 0 0 0 0 1      A =      0 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 1      T = D · A =      0 1 2 1 2 0 0 1 2 0 0 1 2 0 1 3 0 0 1 3 1 3 0 1 2 1 2 0 0 0 0 0 0 1      view at source ↗
Figure 3
Figure 3. Figure 3: The Diagonal Matrix D, Adjacency Matrix A, and Transition Matrix T of G 1.2 Our Proof Method For a given graph, calculating N = (I − Q) −1 is a standard operation, but calculating N for a class of graphs is not a direct exercise. However, N −1 = I − Q is rather straightforward, and since N is an invertible matrix, the equation N · [1] = [t] has a unique solution as does N −1 · [t] = [1]. 2 view at source ↗
Figure 4
Figure 4. Figure 4: The Matrix N = (I − Q) −1 , and ASUA Matrix [t] of G For Theorems 4.4 and 5.3, we will provide a potential solution [t] and show that this potential solution satisfies N −1 · [t] = [1] in all cases. Since there is a unique solution to this equation, our proposed solution is the true solution. In Section 2, we demonstrate how N −1 · [t] = [1] leads to a set of constraint equations with variables t(v1), t(v2… view at source ↗
Figure 5
Figure 5. Figure 5: Category SD1: T(n, {2, k1, k2}) Definition 4.2. A sea dragon G is in class SD2 if V (G) = {v1, . . . , vn} ∪ {uk1 , uk2 , . . . , ukb }, where each ui is a leaf adjacent to the same spine vertex vk for 1 ≤ i ≤ b. We denote G as T(n,(k, b)). 5 view at source ↗
Figure 6
Figure 6. Figure 6: Category SD2: T(n,(k, b)) v1 v2 vk−1 vk vk+1 vn uc u2 u1 view at source ↗
Figure 7
Figure 7. Figure 7: Category SD3: T(n, k(c) ) Definition 4.3. A sea dragon G is in class SD3 if V (G) = {v1, . . . , vn} ∪ {uk1 , uk2 , . . . , uka }, where {u1, . . . , uc} forms a stem attached to vk, with d(u1) = 1. We denote G as T(n, k(c) ). We can now present ASUA equations for SD1, SD2, and SD3. Theorem 4.4 (ASUAs of SD1 Trees). Let G = T(n, {k1, . . . , ka}), t(vi) = t(G, vi , vn), and, by convention, k0 = 1. Then for… view at source ↗
Figure 4
Figure 4. Figure 4: Type I: vi vi Type II: vi vi Type III: vi vi Type IV: vi vi view at source ↗
Figure 8
Figure 8. Figure 8: Structure types for SD1 The Type I structure is characterized by vi−1, vi , and vi+1 all belonging to the same section. In this case, t(vi) = 1 2 (g(s, i − 1) + g(s, i + 1)) + 1. Thus t(vi) = 1 2 (g(s, i − 1) + g(s, i + 1)) + 1 = n 2 + 2(a − 1)n − 2 Xa j=s+1 kj − (i 2 + 1) + 1 2 (−2(s − 1)(i − 1) − 2(s − 1)(i + 1)) + 1 = n 2 − i 2 − 2(a − 1)n − 2(s − 1)i − 2 Xa j=s+1 kj − 1 + 1 = g(s, i). Type II structure… view at source ↗
read the original abstract

For a graph $G$ and vertices $u,v$, we define the ASUA of $v$, $t(G,v,u)$, to be the average steps until absorption along a random walk terminating at $u$. We define a sea dragon to be a tree with a unique path $P$ such that if $d(u) \geq 3$ for some vertex $u$, then $u \in V(P)$. We use Markov chains to determine $t(G,v,u)$ for all vertices of several classes of sea dragons, a broad subclass of trees. Additionally, we give several results on equations related to ASUAs on general graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 4 minor

Summary. The paper defines the average steps until absorption (ASUA) t(G,v,u) as the expected length of a simple random walk on a finite undirected graph G starting at v and absorbed upon reaching u. It introduces sea dragon trees as trees possessing a unique spine path P containing every vertex of degree at least 3, and derives explicit closed-form expressions for t(G,v,u) at every vertex v for several infinite families of such trees by solving the standard linear system of absorbing Markov-chain equations. Additional identities relating ASUAs on arbitrary graphs are stated.

Significance. If the derivations hold, the explicit formulas supply concrete, parameter-free expressions for mean absorption times on a combinatorially natural subclass of trees whose branch points are linearly ordered. Because the spine-and-legs structure permits recursive solution of the linear system along paths, the results are reproducible by direct substitution and could serve as test cases for general algorithms or as building blocks for more complex graphs. The work applies standard Markov-chain machinery without introducing new parameters or circular reductions.

minor comments (4)
  1. §2, Definition 2.3: the phrase 'unique path P such that if d(u)≥3 then u∈V(P)' should be rephrased to make explicit that P is the unique path containing all branch vertices; the current wording leaves open whether multiple spines could satisfy the condition for some trees.
  2. §4, Theorem 4.2: the closed-form expression for t(G,v,u) on the 'balanced sea dragon' family is stated without an accompanying inductive proof or reference to the recursive relation used to obtain it; a short derivation paragraph would make the result self-contained.
  3. Figure 3: the labeling of vertices on the spine and legs is too small to read comfortably; enlarging the figure or adding a table of vertex labels would improve readability.
  4. §5, Corollary 5.1: the general identity relating t(G,v,u) and t(G,u,v) is presented without a citation to the corresponding property of the fundamental matrix of the absorbing chain; adding the reference would situate the result in the existing literature.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful summary of our work and for the positive evaluation of the results on average steps until absorption on sea dragon trees. The recommendation for minor revision is noted; however, the major comments section contains no specific points, queries, or suggested corrections.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper defines sea dragon trees as a subclass of trees with all high-degree vertices on a unique spine path, then applies the standard absorbing Markov chain equations (t_v = 1 + sum p_vw t_w for transient states, t_u = 0) to compute mean absorption times t(G,v,u). Due to the linear spine-plus-legs structure, the resulting linear system admits direct recursive closed-form solutions along paths without any parameter fitting, self-referential equations, or load-bearing self-citations. All steps are independent applications of classical Markov chain theory to the given graph class, with no reduction of outputs to inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central results rest on the standard theory of absorbing Markov chains applied to the newly defined sea dragon graphs; no free parameters or invented physical entities are introduced.

axioms (1)
  • domain assumption Absorbing Markov chain formulas for mean absorption times apply directly to random walks on finite undirected trees.
    Invoked when using Markov chains to determine t(G,v,u) for sea dragons.
invented entities (1)
  • Sea dragon tree no independent evidence
    purpose: A subclass of trees with all degree >=3 vertices confined to a single path, enabling explicit ASUA calculations.
    Newly defined in the paper to organize the computations.

pith-pipeline@v0.9.0 · 5401 in / 1170 out tokens · 54763 ms · 2026-05-08T07:36:30.734718+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

6 extracted references · 6 canonical work pages

  1. [1]

    A. G. Barto, R. S. Sutton, and P. S. Brouwer. Associative search network: A reinforment learning associative memory.Biological Cybernetics, 40:201–211, 1981

    work page 1981

  2. [2]

    J. A. Bondy and U. S. R. Murty.Graph Theory with Applications. North Holland, 1976

    work page 1976

  3. [3]

    Cheteyan, S

    L. Cheteyan, S. Hengeveld, and M. Jones. Chutes and ladders for the impatient.The College Mathematics Journal, 42(1):2–8, 2011

    work page 2011

  4. [4]

    C. M. Grinstead and J. L. Snell.Introduction to Probability. American Mathematical Society, Providence, 2nd edition, 1998

    work page 1998

  5. [5]

    L. Lovasz. Random walks on graphs: a survey.Yale University: Department of Computer Science, 1994

    work page 1994

  6. [6]

    Russell and P

    S. Russell and P. Norvig.Artificial Intelligence: A Modern Approach. Pearson, 4 edition, 2021. 11

    work page 2021