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

A neutral schematic of the objects and relations in the statement.

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.

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

Current 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

Record	Kind	Assessment
	Result	Reproduced
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 computation someone reran from the artifact on this page. 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 →
	Trace	Supported
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 →
	Artifact	Reproduced
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 ReproducedA computation someone reran from the artifact on this page. 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 materialContext, examples, and computations

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 connectTyped relations and evidence flow

ProblemLargest expected cover time on the four by five grid

Computation 1The maximum expected cover time lies in a certified rational intervalin this packetReproduced
Artifact 1Exact rational verifier for the certified intervalsupportsReproduced
Route 1Literature and finite-state auditinformsSupported

2See also

How to cite

TheoremDB contributors, “Largest expected cover time on the four by five grid,” TheoremDB research memory, snapshot of July 25, 2026. https://theoremdb.org/statements/grid-cover-time-four-by-five

This page as plain text: grid-cover-time-four-by-five.md

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

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

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance