[#P2724] Largest expected cover time on the four by five grid

Problem. For simple random walk on \(P_4\square P_5\), with the starting vertex counted as visited at time zero, determine the maximum expected cover time over all starting vertices and identify every maximizing symmetry orbit.

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

1Context

Exact dynamic programming on the three by three grid exposes the counterintuitive ordering of starting positions.

2Problem setup

Definition 1. Cover time is the first time by which all twenty vertices have been visited.

Remark 1. The answer for each starting orbit is an exact rational number.

3What counts as a solution

Supply reduced rational expectations for every start orbit or exact linear-system certificates from which all values and the maximizing orbit can be checked.

1Status

Saved packet · July 25, 2026

What counts as a solution

Saved packet status (The maximum expected cover time lies in a certified rational interval). For the maximum expected cover time \(C_{4,5}\), the certified interval is \(19\le C_{4,5}\le8534169769/5542680\); the exact maximum and its maximizing starting-vertex symmetry orbit remain unresolved.^[1]

1Packet records

Show recorded summaries

Record	Kind	Assessment
For the maximum expected cover time \(C_{4,5}\), the certified interval is \(19\le C_{4,5}\le8534169769/5542680\); the exact maximum and its maximizing starting-vertex symmetry orbit remain unresolved.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
claim · Computation 1 For the maximum expected cover time \(C_{4,5}\), the certified interval is \(19\le C_{4,5}\le8534169769/5542680\); the exact maximum and its maximizing starting-vertex symmetry orbit remain unresolved.^[1] Relevance to this problem For Largest expected cover time on the four by five grid, record gct45-claim-certified-interval (“The maximum expected cover time lies in a certified rational interval”) records a bound, answer, status fact, or structural consequence. The record states: For the maximum expected cover time \(C_{4,5}\), the certified interval is \(19\le C_{4,5}\le8534169769/5542680\); the exact maximum and its maximizing starting-vertex symmetry orbit remain unresolved. Evidence ReproducedA replay is recorded for this computation. Inspect the replay record for its procedure and scope. Record state established Scope simple random walk on P_4 square P_5 with the starting vertex visited at time zero, maximized over all twenty starting vertices Sources Reference 1 Details Write \(C_{4,5}\) for the maximum expected cover time. The certified interval is \[ \boxed{19\le C_{4,5}\le \frac{8{,}534{,}169{,}769}{5{,}542{,}680}}. \] The upper endpoint is approximately \(1539.7190\). The grid has 20 vertices, 31 edges, and diameter 7. The commute-time identity and \(R_{\mathrm{eff}}(x,y)\le d(x,y)\) give \(\max_{x,y}E_xT_y\le 2\cdot31\cdot7=434\). Matthews's inequality then gives \(E_xT_{\mathrm{cov}}\le H_{19}\max_{u,v}E_uT_v\), where \(H_{19}=275295799/77597520\). Multiplication and reduction yield the displayed upper endpoint. A walk needs at least nineteen moves to visit the other nineteen vertices, which proves the lower endpoint. The exact maximum and its maximizing symmetry orbit remain unresolved in this record. The six start orbits have representatives \((0,0),(0,1),(0,2),(1,0),(1,1),(1,2)\). Open full record →
General cover-time theory certifies the interval, and the exact connected-set recurrence reduces the finite computation to 116,166 systems.	Trace	Outcome: Open Evidence: Supported Backed by a cited source or by evidence short of a proof.
attempt · Route 1 General cover-time theory certifies the interval, and the exact connected-set recurrence reduces the finite computation to 116,166 systems.^[1][2] Relevance to this problem For Largest expected cover time on the four by five grid, record gct45-attempt-literature-and-state-space-audit (“Literature and finite-state audit”) documents a concrete method, search boundary, or failed route. The record states: General cover-time theory certifies the interval, and the exact connected-set recurrence reduces the finite computation to 116,166 systems. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state in progress Scope connected visited sets and starting symmetry orbits for simple random walk on P_4 square P_5 Sources Reference 1, Reference 2 What happened Matthews proves the harmonic-factor comparison between cover time and maximal hitting time. Chandra, Raghavan, Ruzzo, Smolensky, and Tiwari relate commute time to electrical resistance. On this grid, a shortest path gives an immediate resistance upper bound of 7. The finite-state audit enumerated 116,166 connected nonempty subsets. Reflection in the horizontal and vertical axes gives six starting orbits. Exact rational elimination over every connected-set Dirichlet system was started and exceeded the allotted entry time. No exact value or maximizing orbit is claimed here. Related: Computation 1 Open full record →
Standard-library Python rebuilds the graph and checks every integer and rational used in the interval proof.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 Standard-library Python rebuilds the graph and checks every integer and rational used in the interval proof. Relevance to this problem For Largest expected cover time on the four by five grid, record gct45-artifact-rational-bound-certificate (“Exact rational verifier for the certified interval”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python rebuilds the graph and checks every integer and rational used in the interval proof. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope the exact rational lower and upper certificates for the maximum expected cover time on P_4 square P_5 Entry point `join source_lines with newline and run with python3` Runtime CPython 3, standard library only Details The program constructs the row-major 4 by 5 grid, checks its order, size, connectivity, diameter, and six reflection orbits, and performs the harmonic-number calculation with `Fraction`. Its graph payload lists each undirected edge as `u:v` in lexicographic order. The certificate uses the commute-time identity, the path resistance bound, and Matthews's inequality. The resulting interval is rigorous for every start. For a future exact solve, let \(F(S,v)\) be the expected remaining time when the connected visited set is \(S\) and the walker is at \(v\in S\). Set \(F(V,v)=0\). For each proper connected \(S\), solve the rational Dirichlet system \[ \deg(v)F(S,v)-\sum_{w\sim v,\,w\in S}F(S,w)=\deg(v)+\sum_{w\sim v,\,w\notin S}F(S\cup\{w\},w). \] Processing sets by decreasing size supplies every right-hand side. The exact start values are \(F(\{v\},v)\). There are 116,166 connected nonempty vertex sets, with size histogram `[20,31,70,161,376,859,1870,3794,7028,11641,16872,20809,21090,16702,9692,3894,1050,186,20,1]`. This run reached the state-count check, but the full rational solve exceeded the entry time cap. Related: Computation 1 Open full record →
No records match these filters.

Notes and companion material

Original intake status. UNKNOWN as of 2026-07-25. For the maximum expected cover time \(C_{4,5}\), the certified interval is \(19\le C_{4,5}\le8534169769/5542680\); the exact maximum and its maximizing starting-vertex symmetry orbit remain unresolved. The checked sources do not settle the full acceptance condition.

The dated packet audit checked the exact title, parameter, and the terminology used by the cited primary literature.
The strongest recorded neighboring result is: For the maximum expected cover time \(C_{4,5}\), the certified interval is \(19\le C_{4,5}\le8534169769/5542680\); the exact maximum and its maximizing starting-vertex symmetry orbit remain unresolved.
The controlled TheoremDB corpus was checked for equivalent formulations and contains no duplicate published target.

Recorded example 1. On the three by three grid, corner, edge-midpoint, and center starts form the three symmetry classes.

Computational notes

Exact rational dynamic programming over 217 proper connected visited subsets of P_3 square P_3 gave 140803109038245/4517710919176 for a corner, 275264650510462/8470707973455 for an edge midpoint, and 3978748873082/119305746105 for the center. These are approximately 31.1669143, 32.4960619, and 33.3491806.

How the 3 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemLargest expected cover time on the four by five grid

All 2 recorded relations between these records and the problem

2See also

Monotonicity of consecutive-adjacency avoidance in random permutationsprobability
Eventual monotonicity in a signed subset-sum local limitprobability
Eventual decrease for distinct cycle lengths in random permutationsprobability

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Largest expected cover time on the four by five grid.” TheoremDB. P2724. Problem statement; statement text SHA-256 e39253cc71478d0fe784e65328174b1c9aad38b51044f141652833da258666bb. https://theoremdb.org/statement/?ref=P2724

BibTeX

@misc{theoremdb-problem-e39253cc71478d0fe784e65328174b1c9aad38b51044f141652833da258666bb,
  title = {{Largest expected cover time on the four by five grid}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 e39253cc71478d0fe784e65328174b1c9aad38b51044f141652833da258666bb},
  url = {https://theoremdb.org/statement/?ref=P2724}
}

Plain text: Built Markdown snapshot

This problem includes 3 records joined by 2 typed links, sourced from doi.org^[1], current as of July 25, 2026.

1Lean verification

1References

Packet source. Peter Matthews, “Covering Problems for Markov Chains,” Annals of Probability 16(3) (1988), 1215-1228. DOI 10.1214/aop/1176991686. Peter Matthews, Covering problems for Markov chains, Annals of Probability 16 (1988), 1215-1228, cover-time inequality; commute-time identity and effective-resistance bound as recorded in the literature-audit object; Peter Matthews, Covering problems for Markov chains, Annals of Probability 16 (1988), 1215-1228; A. Chandra et al., The electrical resistance of a graph captures its commute and cover times, STOC 1989, 574-586. ↗journal article · primary source · version of record · checked 2026-07-25Source use: original summary.The maximum expected cover time lies in a certified rational interval. For the maximum expected cover time \(C_{4,5}\), the certified interval is \(19\le C_{4,5}\le8534169769/5542680\); the exact maximum and its maximizing starting-vertex symmetry orbit remain unresolved. Literature and finite-state audit. General cover-time theory certifies the interval, and the exact connected-set recurrence reduces the finite computation to 116,166 systems.Also cited at cover-time comparison theorem, Annals of Probability 16(3), pages 1215-1228.Also cited at Annals of Probability 16 (1988), 1215-1228.Also cited at Peter Matthews, Covering problems for Markov chains, Annals of Probability 16 (1988), 1215-1228, cover-time inequality; commute-time identity and effective-resistance bound as recorded in the literature-audit object.For Largest expected cover time on the four by five grid, this source proves the harmonic-factor comparison between cover time and maximal hitting time used in the packet's upper bound.Source named by the research packet.
A. K. Chandra, P. Raghavan, W. L. Ruzzo, and R. Smolensky, “The electrical resistance of a graph captures its commute and cover times”. Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 (1989), 574-586. DOI 10.1145/73007.73062. Proceedings of STOC 1989, 574-586. ↗journal article · primary source · version of record · checked 2026-07-25Source use: original summary.Literature and finite-state audit. General cover-time theory certifies the interval, and the exact connected-set recurrence reduces the finite computation to 116,166 systems.For Largest expected cover time on the four by five grid: Literature and finite-state audit. General cover-time theory certifies the interval, and the exact connected-set recurrence reduces the finite computation to 116,166 systems.

Original CC0 exact finite random-walk problem.

[#P2724] Largest expected cover time on the four by five grid

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance