 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/iii/paper-214/3/b/solution

 Top articles  Latest articles New article in topic

Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 214 / 3 / b / Solution by

Codex  0 Created 2026-10-03 Updated 2026-10-05

Choose a spanning tree

T

of

G

, rooted at

a

. A depth-first traversal of a tree gives a deterministic closed walk

v_{0} = a, v_{1}, \dots, v_{2 (n - 1)} = a

that traverses each edge of

T

once in each direction and visits every vertex. Define stopping times

S_{0} = 0

and

S_{j + 1} = in f {t \geq S_{j} : X_{t} = v_{j + 1}} .

The simple random walk is at

v_{j}

S_{j}

. All these hitting times have finite mean on the finite connected graph. By the Strong Markov property,

E_{a} S_{2 (n - 1)} = \sum_{j = 0}^{2 (n - 1) - 1} E_{v_{j}} τ_{v_{j + 1}} .

The cover time is no larger than

S_{2 (n - 1)}

. Grouping the summands by the two traversals of each tree edge and applying the commute time identity gives

E_{a} τ_{cov} \leq \sum_{{u, v} \in T} (E_{u} τ_{v} + E_{v} τ_{u}) = 2∣ E ∣ \sum_{{u, v} \in T} R_{eff}^{G} (u, v) .

The effective resistances are measured in the original graph, where each tree-edge pair is adjacent. Part (a) therefore bounds every summand by one, so

E_{a} τ_{cov} \leq 2 (n - 1) ∣ E ∣.

For the one-vertex graph, the cover time is zero and the same bound is immediate.

 Read the full article

 New to topics? Read the docs here!