* [17] Drazin, P. and Davey, A.: Shear layer instability of an inviscid compressible fluid. part 3. J. Fluid Mech.  82 (2), 255–260, (1977).
  * [18] Drazin, P. and Reid, W.: Hydrodynamic stability, Cambridge Math. Library, Cambridge University Press, Cambridge, 2nd ed., 2004.
  * [19] Grenier, E.: On the nonlinear instability of Euler and Prandtl equations. Comm. Pure Appl. Math. 53, 1067–1091, (2000).
  * [20] Grenier, E., Nguyen, T. Rousset, F. and Soffer, A.: Linear inviscid damping and enhanced viscous dissipation of shear flows by using the conjugate operator method. J. Funct. Anal.  278 (3), 108339, (2020).
  * [21] Grenier, E., Guo, Y. and Nguyen, T.: Spectral instability of general symmetric shear flows in a two-dimensional channel. Adv. Math. 292, 52–110, (2016).
  * [22] Grenier, E., Guo, Y., and Nguyen, T.: Spectral instability of characteristic boundary layer flows. Duke Math. J. 165, 3085–3146, (2016).
  * [23] Gérard-Varet, D., Maekawa, Y. and Masmoudi, N.: Gevrey stability of Prandtl expansions for 2D Navier-Stokes flows. Duke Math. J. 167(13), 2531-2631, (2018).
  * [24] Heisenberg, W.: On the stability of laminar flow.  Proceedings of the International Congress of Mathematicians, Cambridge, Mass., 1950, Vol.2 292–296. Amer. Math. Soc., Providence, R.I., 1952.
  * [25] Ionescu, A. and Jia, H.: Nonlinear inviscid damping near monotonic shear flows. Acta Math., 230, 321–399, (2023).
  * [26] Jia, H.: Linear inviscid damping in Gevrey spaces. Arch. Ration. Mech. Anal. 235 (2), 1327–1355, (2020).
  * [27] Kagei, Y. and Nishida, T.: Instability of Plane Poiseuille flow in viscous compressible gas. J. Math. Fluid Mech.  17, 129–143, (2015).
  * [28] Kagei, Y. and Nishida, T.: Traveling waves bifurcating from plane Poiseuille flow of the compressible Navier-Stokes equation, Arch. Ration. Mech. Anal. 231, 1–44, (2019).
  * [29] Kelvin, L.: Stability of fluid motion-rectilinear motion of viscous fluid betwwen two plates. Philos. Mag.  24, 188 (1887).
  * [30] Lees, L and Lin, C.C.: Investigation of the stability of the laminar boundary layer in a compressible fluid, NACA Technical note 1115, 1946.
  * [31] Li, H., Masmoudi, N. and Zhao, W.: A dynamical approach to the study of instability near Couette flow. arXiv. 2203. 10894.
  * [32] Lees, L. and Reshotko, E.: Stability of the compressible laminar boundary layer. J. Fluid Mech. 12(4), 555-590, 1962.
  * [33] Lin, C.C.: The theory of hydrodynamic stability. Cambridge, at the University Press, 1955.
  * [34] Lin, Z.: Instability of some idea plane flows. SIAM J. Math. Anal. 35, 318–356, (2003).
  * [35] Lin, Z. and Zeng, C.: Inviscid dynamical structures near Couette flow. Arch. Ration. Mech. Anal. 200, no. 3., 1075–1097, (2011).
  * [36] Liu, C.-J., Yang T. and Zhang, Z.: Analysis on Tollmien-Schlichting wave in the Prandtl-Hartmann regime. J. Math. Pures Appl. 165, 58–105, (2022).
  * [37] Mack, L. M.: The inviscid stability of the compressible Laminar Boundary layer. Space Programs Summary, No. 37-23, Jet Propulsion Library, Pasadena, CA, 1963, p. 297.
  * [38] Masmoudi, N., Wang, Y., Wu, D. and Zhang, Z.: Tollmien-Schlichting waves in the subsonic regime. arXiv. 2305. 03229.
  * [39] Masmoudi, N. and Zhao, W.: Stability threshold of the 2D Couette flow in Sobolev spaces. Ann. Inst. H. Poincaré Anal. Non Linéaire 39 (2), 245–325, (2022).
  * [40] Masmoudi, N. and Zhao, W.: Nonlinear inviscid damping for a class of monotone shear flows in finite channel. arXiv. 2010. 01612.
  * [41] Mucha, P. B. and Piasecki, T.: Compressible perturbations of Poiseuille type flow. J. Math. Pures Appl. 102, 338–363, (2014).
  * [42] Orr, W.: The stability or instability of the steady motions of a perfect liquid and of a viscous liquid, I, Proc. R. Irish Acad. Sect. A, Math. Astron. Phys. Sci. 27 (1907).
  * [43] Reshotko, E.: Stability of the compressible laminar boundary layer, GALCIT Memo. No. 52, California Institute of Technology, Pasadena, CA. (1962).
  * [44] Rayleigh, L.: On the stability or instability of certain fluid motions. Proc. Lond. Math. Soc. S1-11, 57, (1880).
  * [45] Romanov, V.: Stability of plane-parallel Couette flow, Funct. Anal. Appl. 7 (1973) 137-146.
  * [46] Schlichting, H. and Gersten, K.: Boundary layer theory. Ninth edition. With contribution from Egon Krause and Herbert Oertel Jr. Translated from German by Katherine Mayea. Springer-Verlag, Berlin, 2017.
  * [47] Wasow, W.: The complex asymptotic theory of a fourth order differential equations of hydrodynamics. Ann. of Math. (2), 49, 852–871, (1948).
  * [48] Wei. D., Zhang, Z. and Zhao, W.: Linear inviscid damping and vorticity depletion for shear flows. Ann. PDE 5 (3), (2019).
  * [49] Wei. D., Zhang, Z. and Zhao, W.: Linear inviscid damping and enhanced dissipation for the Kolmogorov flow. Adv. Math.  362, 106963, (2020).
  * [50] Yang, T. and Zhang, Z.: Linear instability analysis on compressible Navier-Stokes equations with strong boundary layer. Arch. Ration. Mech. Anal. 247, 83, (2023).
  * [51] Zillinger, C.: Linear inviscid damping for monotone shear flows. Trans. Am. Math. Soc. 369, 8799–8855, (2017).
  * [52] Zillinger, C.: Linear inviscid damping for monotone shear flows in finite periodic channel, boundary effects, blow-up and critial Sobolev regularity, Arch. Ration. Mech. Anal.  221(3), 1449–1509, (2016).
  * [53] Zeng, L., Zhang, Z. and Zi, R.: Linear stability of the Couette flow in 3D isentropic compressible Navier-Stokes equations. SIAM J. Math. Anal.  54 (5), 5698–5741, (2022).


# Random walks on edge colored random graphs

Colin Cooper
Department of Informatics
King’s College
London WC2B 4BG
England Research supported at the University of Hamburg, by a Mercator
fellowship from DFG - Project 491453517 Alan Frieze
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh PA 15213
USA Research supported in part by NSF grant DMS1952285

###### Abstract

We consider random walks on edge coloured random graphs, where the colour of
an edge reflects the cost of using it. In the simplest instance, the edges are
coloured red or blue. Blue edges are free to use, whereas red edges incur a
unit cost every time they are traversed.

##  1 Introduction

The cover time of a connected graph is the maximum over the start vertex of
the expected time for a simple random walk to visit every vertex of the graph.
There is a large literature on this subject see for example [1], [13],
including [4]–[8] which give precise estimates of cover time for various
models of random graphs.

We consider the following scenario: There is a connected graph $G$ in which
the edges are colored red and blue. We study the cover time of such a graph
when there is a bound on the number red edges that can be used. We can think
of blue edges as free to use, whereas red edges represent toll roads, the
bound being the maximum budget. The decision to use, or not to use, a toll
road can be made in various ways, which we characterize as congestion
charging, flip walks, oblivious walks and smooth walks. In the simplest case,
the oblivious model, the random walk uses edges of $G$ regardless of colour
until the budget is used up, after which it will be restricted to the blue
sub-graph.

##### Models of red-blue regular graphs.

Let $G$ be a connected $n$-vertex graph, and let
${\mathcal{W}}={\mathcal{W}}(R,B)$ be a simple random walk on $G$ subject to
the given constraints on the use of red and blue edges. We use
$C_{G}=C_{G}(R,B)$ for the constrained cover time of $G$ by the walk
${\mathcal{W}}(R,B)$, and use $\widehat{C}_{G}$ for the corresponding
unconstrained cover time of $G$.

Let

$\sigma_{RB}=\frac{r+b-1}{r+b-2},\qquad\sigma_{B}=\frac{b-1}{b-2}.$ (1)

One simple model is to take $G$ as the union of a random $n$-vertex
$r$-regular graph with red edges and a random $n$-vertex $b$-regular graph
with blue edges. For such graphs, w.h.p. the unconstrained cover time of $G$
(see [4]) is asymptotic to $\widehat{C}_{G}=\sigma_{RB}n\log
n=(r+b-1)/(r+b-2)n\log n$, whereas for $b\geq 3$, the cover time of a walk
restricted to the blue edges is asymptotic to $C_{G}(B)=\sigma_{B}n\log
n=(b-1)/(b-2)n\log n$.

Another simple model is to take $G$ as the union of a blue Hamilton cycle and
a random $r$-regular graph with red edges. This model, based on short cutting
a Hamilton cycle, is one of the original Watts-Strogatz type small world
models [17]. For $r=1$ (the union of a Hamilton cycle and a random 1-factor)
the diameter was studied by Bollobás and Chung [3]. Subsequently, the fact
that 3-regular graphs are Hamiltonian w.h.p. was established by Robinson and
Wormald [16]. Thus almost all 3-regular graphs have a decomposition into a
blue Hamilton cycle and a random red 1-factor.

##### Smooth walks.

The walk alternates in phases between using edges of either colour (a red/blue
phase) and edges of colour blue only (a blue phase). In a red/blue phase the
walk is on $G$, and in a blue phase the walk is on $G_{B}$, the subgraph
induced by the blue edges. The length of the phases can vary, but to analyse
the model, we require that the length of each phase is at least $\omega
T_{G}\log n$ where $T_{G}$ is a mixing time given by (2), and
$\omega\to\infty$ with $n$. We call such a walk smooth. We say that such a
random walk is $\alpha$-constrained if in total, it is only allowed to use a
red edge at most $\gamma(\alpha)n\log n$ times, where $\gamma(\alpha)$ is
given in Theorem 1(a) below.

The congestion pricing model fits naturally as a special case of smooth walks.
Peak and off-peak periods alternate as in the smoothed model. The length $C,F$
(charged, free) of the peak and off peak periods are fixed and in constant
proportion. The walk uses the red (charged) edges only in off-peak periods
when they are free to use. In peak periods the walk uses only blue (free)
edges. We assume there are at most $n^{\theta}$ distinct phases of equal
length $C+F$, for some small $\theta>0$ constant.

######  Theorem 1.

(Smooth walks) Let $G$ be the union of a random $r$-regular graph with red
edges and a $b$-regular graph with blue edges where $r\geq 1$ and $b\geq 2$.

  1. (a)

If $b\geq 3$ and $\alpha<1$ constant, then w.h.p. the cover time of an
$\alpha$-constrained smooth random walk on $G$ with budget
$\gamma(\alpha)=(\alpha\sigma_{RB}r)(r+b)n\log n$ is asymptotically equal to
$C_{G}(R,B)=(\alpha\sigma_{RB}+(1-\alpha)\sigma_{B})n\log n$.

  2. (b)

If $b=2$, $r\geq 1$, and the blue edges span a Hamilton cycle then in the
congestion pricing model with periods $C,F$, the cover time of a random walk
on $G$ is asymptotically equal to $C_{G}=(1+C/F)((r+1)/r)\,n\log n$.

##### Flip walks.

In a flip walk there is no hard bound on the number of times we use a red
edge, only a stochastic one. At any step, let $\rho_{R}$ be the probability of
transition down a given red edge adjacent to the current vertex and $\rho_{B}$
the probability of transition down a given blue edge. Thus the probability the
next transition is red is $r\rho_{R}$ etc. Examples include the following. Let
$\rho_{R}=\alpha/r$, and $\rho_{B}=(1-\alpha)/b$ in which case the probability
of transition down a red edge at any step is $\alpha$, and a blue edge is
$1-\alpha$.

######  Theorem 2.

(Flip walks)

  1. (a)

Simplest case. If $r=1$, $b=2$, and $q=2\rho_{B}=1-\rho_{R}$, where
$0<\rho_{R}\leq\rho_{B}$, the cover time of a flip walk on $G$ is
asymptotically equal to $C_{G}\sim\theta n\log n$ where

$\theta=\frac{2}{q(5-q+\sqrt{9-10q+q^{2}})}+\frac{2}{q(1-q+\sqrt{9-10q+q^{2}})}.$

This cover time is minimized at $2n\log n$ when $\rho_{R}=\rho_{B}=1/3$, and
all edges have the same transition probability.

  2. (b)

If $r=1$, $b\geq 2$ and $0<\rho_{R}\leq\rho_{B}$ then w.h.p. the cover time of
a flip walk on $G$ is asymptotically equal to $C_{G}\sim(1/(1-f))n\log n$.
Here $f$ is the smallest solution in $[0,1]$ to $F(z)=0$ where $F(z)$ is given
by (24).

Theorem 2(a) confirms that for the simplest case, the cover time cannot be
improved by biassing the walk probabilities. The general solution $r\geq
2,b\geq 2$ seems difficult to obtain.

##### Oblivious walks.

The simplest case. The random walk uses edges of $G$ regardless of colour
until the budget is used up, after which it is be restricted to the blue
subgraph. In the case where $b=2$, $r\geq 1$ and the budget is less than the
unconstrained cover time $C_{G}\sim(r+1)/r\,n\log n$, things go seriously
wrong for the walk; see Theorem 3(b)–(c) below.

######  Theorem 3.

(Oblivious walks) Let $\varepsilon>0$ constant.

  1. (a)

Suppose $b\geq 3$. and the budget is $(1-\varepsilon)\sigma_{RB}n\log n$.The
cover time of an oblivious walk on $G$ is asymptotically equal to
$(\alpha\sigma_{RB}+(1-\alpha)\sigma_{B})n\log n$ w.h.p., as given in (1)
where $\alpha=\tfrac{1-\varepsilon}{r(r+b)}$.

  2. (b)

Suppose that $b=2$, $r\geq 1$, the blue edges span a Hamilton cycle, and the
budget be at most $(1-\varepsilon)(r+1)/rn\log n$. The cover time of an
oblivious walk on $G$ is asymptotic to $C_{G}(R,B)\sim n^{2}/2$, w.h.p.

  3. (c)

If $b=2$ and the blue edges span a random 2-factor then w.h.p. an oblivious
walk with budget of at most $(1-\varepsilon)(r+1)/rn\log n$ steps will fail to
cover $G$.

##### Related models.

The underlying graph of the random walk we consider varies structurally over
time (temporally) in a predictable fashion; but within the constraint of a
fixed budget. Many authors have considered aspects of this, or related
problems. We mention a few below.

For a survey on temporal networks, see Holme [10]. Random walks whose
transition probability alters depending on structural condition have been
studied extensively. An early model by Kemperman [12], the oscillating random
walk, remains one of the simplest and most attractive. Citing from [12]: Let
$\\{Y_{n},n=0,1,...\\}$ denote a stationary Markov chain taking values in
$\mathbb{R}^{d}$. As long as the process stays on the same side of a fixed
hyperplane $E$, it behaves as a ordinary random walk with jump measure $\mu$
or $\nu$, respectively.

As a general instance of an application of random walks with edge costs,
Coppersmith, Doyle, Raghavan and Snir, [9], use random walks on graphs with
positive real costs on all edges to study the design and analysis of
randomized on-line algorithms. Two recent papers by Majumdar et al., [14],
[15], which study variable charges for walk transitions, have some bearing on
the model we consider. In [14], [15], a one-dimensional walker’s position
$X_{t}$ at discrete time $t$ is a positive random variable evolving according
to $X_{t}=X_{t-1}+\eta_{t}$. Transitions are priced according to their length
$\eta$, there being one price for short distances and another for longer ones.
This reflects how taxi fares are calculated in congested cities111[15] The
municipality prescribes a threshold speed $\eta_{c}$ derived from statistical
analyses of local traffic patterns. If the taxi surpasses $\eta_{c}$, the
meter tallies the fare based on the distance covered, while a slower pace
results in time-based fare computation. This approach ensures that drivers are
compensated even when they face prolonged periods of slow progress.. The
authors compute the average and variance of the distance covered in $n$ steps
when the total budget $C$ is fixed.

##### Proof outline.

Our main tool will be the First Time Visit Lemma. This technique, introduced
in [4], allows us to make very precise estimates of cover time in certain
classes of graphs. The technique was subsequently refined in [7], and in [8]
where various technical conditions were removed. In outline, the approach is
to bound the cover time above and below using (4) of Lemma 4. Much of the work
is in constructing the lower bound on the cover time. On regular graphs the
walks we consider have uniform stationary distribution, and are rapidly
mixing. The unvisit probability (4) has a parameter $p_{v}\sim\pi_{v}/R_{v}$
(see (3)) where $R_{v}$ is the expected number of returns to vertex $v$ during
the mixing time.

##  2 Background material

##### Notation.

We use $A_{n}\sim B_{n}$ to denote $A_{n}=(1+o(1))B_{n}$ and thus
$\lim_{n\rightarrow\infty}A_{n}/B_{n}=1$. We use $\omega$ to denote a quantity
which tends to infinity with $n$ more slowly than any other variables in the
given expression. The expression $f(n)\ll g(n)$ indicates $f(n)=o(g(n))$. The
inequality $A\lesssim B$ which stands for $A\leq(1+o(1))B$ is used to
unclutter notation in some places.

###  2.1 First Time Visit Lemma

Let $G$ denote a fixed connected graph, and let $u$ be some arbitrary vertex
from which a walk ${\mathcal{W}}_{u}$ is started. Let ${\mathcal{W}}_{u}(t)$
be the vertex reached at step $t$, let $P$ be the matrix of transition
probabilities of the walk, and let
$P_{u}^{(t)}(v)=\mathbb{P}({\mathcal{W}}_{u}(t)=v)$. Let $\pi$ be the steady
state distribution of the random walk ${\mathcal{W}}_{u}$. For an unbiased
ergodic random walk on a graph $G$ with $m=m(G)$ edges,
$\pi_{v}=\frac{d(v)}{2m}$, where $d(v)$ denotes the degree of $v$ in $G$.

We denote the steady state probability of a simple random walk on $G=(V,E)$
being at $v\in V$ is $\pi_{G}(v)$. We let $\mathbb{P}_{u,G}^{(t)}(v)$ denote
the probability that a simple random walk on $G$ started at $u$ is at $v$
after $t$ steps. We then define a mixing time $T_{G}$ by

$T_{G}=\min\left\\{\tau:\max_{u,v}\left\\{\frac{|\mathbb{P}_{u,G}^{(t)}(v)-\pi(v)|}{\pi(v)}\right\\}=o(1)\text{
for }t\geq\tau\right\\}.$ (2)

For $t\geq 0$, let ${\mathcal{A}}_{t}(v)$ be the event that
${\mathcal{W}}_{u}$ does not visit $v$ in steps $T_{G},T_{G}+1,\ldots,t$. The
vertex $u$ will have to be implicit in this definition. We will use the
following version:

######  Lemma 4.

Let $R_{v}\geq 1$ is the expected number of visits by ${\mathcal{W}}_{v}$ to
$v$ in the time interval $[0,T_{G}]$. Suppose that $T_{G}\pi_{v}=o(1)$ and
$R_{v}=O(1)$. Let

$p_{v}=\frac{\pi_{v}}{R_{v}(1+O(T_{G}\pi_{v}))}.$ (3)

Then for all $t\geq T_{G}$,

$\mathbb{P}({\mathcal{A}}_{t}(v))=\frac{(1+O(T_{G}\pi_{v}))}{(1+p_{v})^{t}}+O(T_{G}^{2}\pi_{v}e^{-\mu
t/2}),$ (4)

where $\mu=\Omega(1/T_{G})$.

###  2.2 Properties of random regular graphs

The use of (4) will require us to verify some facts about random regular
graphs. These will by and large be taken from [4]. Let

$\sigma={\left\lfloor\log^{1/2}n\right\rfloor}.$ (5)

Say a cycle $C$ is small if $|C|\leq\sigma$. A vertex of $G$ is locally tree-
like if $v$ is at distance at least $\sigma$ from the nearest small cycle.

######  Theorem 5.

Let $s\geq 3$ be a constant and let $G$ be chosen uniformly from the set
${\cal G}_{s}$ of $s$-regular graphs with vertex set $[n]$. Then w.h.p.

P1.

$G$ is connected.

P2.

$T_{G}=O(\log n)$.

P3.

If $v$ is locally tree-like then $R_{v}=\frac{s-1}{s-2}+o(\sigma^{-1})$.

P4.

There are at most $s^{3\sigma}$ non locally-tree-like vertices and if $v$ is
not locally-tree-like then $R_{v}\leq 3$.

P5

The second eigenvalue $\lambda$ of $G$ is positive and $\lambda\leq 1-\theta$
for some positive constant $\theta$.

##  3 Proof of Theorem 1

###  3.1 Proof of Theorem 1(a)

In this section we prove that if $b\geq 3$ then w.h.p. the cover time of an
$\alpha$-constrained smooth random walk on $G$ with budget
$\gamma(\alpha)=(\alpha\sigma_{RB}r)/(r+b)\,n\log n$ is asymptotically equal
to $C_{G}=(\alpha\sigma_{RB}+(1-\alpha)\sigma_{B})\,n\log n$. It was shown in
[4] that the unconstrained cover time of $G$ is
$\widehat{C}_{G}\sim\sigma_{RB}\,n\log n$ w.h.p. Without any constraint on the
choice of the next edge, a walk of length $\widehat{C}_{G}$ would cross a red
edge $\sim\frac{r}{r+b}\sigma_{RB}\,n\log n$ times. It follows that w.h.p. we
will not be able to complete the walk within the budget without having to
avoid red edges a significant number of times.

If the phases are $o(T_{G})$ in length then there are some technical
difficulties that we have not yet managed to overcome, see Remark 1 below.

######  Remark 1.

There does not seem to be a compelling reason for us to only consider smooth
walks. If we allow the walk to switch between allowing red edges and not
allowing them, then we have no problems with mixing. This is because the
steady state probabilities are $1/n$ regardless. The problem arises because
$R_{v}$ will depend heavily on how we switch between the two possibilities.

####  3.1.1 Upper bound

Suppose now that we start a walk at vertex $u$ and that we alternate between
red/blue phases and blue phases. Take $t_{0}=0$, and suppose we change phase
at times $t_{1},t_{2},\ldots,t_{i},\ldots$. Assume that whenever $i$ is even
we start a red/blue phase at $t_{i}$ and switch to a blue phase when $i$ is
odd. At each step in a red/blue phase there is an $r/(r+b)$ chance of using a
red edge. We also know that this walk will finish at least as early as one
that only uses blue edges. This follows from Lemma 4 and the fact that
$s/(s-1)$ decreases as $s$ increases. We will assume
$t_{i}-t_{i-1}\geq\omega\log^{2}n\gg T_{G}$ for $1\leq i<m$, so that

$t_{RB}=\sum_{i\geq 0}(t_{2i+1}-t_{2i})\leq\left(1-\Theta\left(\frac{\log
n}{n^{1/2}}\right)\right)\alpha\sigma_{RB}n\log n.$ (6)

Multiplying the RHS of (6) by $r/(r+b)$ and applying the Chernoff bounds
yields an upper bound of $\gamma(\alpha)n\log n$ on the number of times a red
edge is used.

Let $T_{G}(u)$ be the time taken to visit every vertex of $G$ by the random
walk ${\mathcal{W}}_{u}$. Let $U_{t}$ be the number of vertices of $G$ which
have not been visited by ${\mathcal{W}}_{u}$ at step $t$. We note the
following:

$\displaystyle C_{u}=\mathbb{E}T_{G}(u)$ $\displaystyle=$
$\displaystyle\sum_{t>0}\mathbb{P}(T_{G}(u)\geq t),$ (7)
$\displaystyle\mathbb{P}(T_{G}(u)>t)$ $\displaystyle=$
$\displaystyle\mathbb{P}(U_{t}>0)\leq\min\\{1,\mathbb{E}U_{t}\\}.$ (8)

It follows from (7), (8) that for all $t$

$C_{u}\leq t+\sum_{s\geq t}\mathbb{E}U_{s}=t+\sum_{v\in V}\sum_{s\geq
t}\mathbb{P}(\mbox{\boldmath$A$}_{s}(v)).$ (9)

In both phases the random walk is on a regular graph and so $\pi_{v}=1/n$
throughout.

We are stopping the RB walk at $t^{*}\sim\sigma_{RB}n\log n$ when the budget
runs out. At that time the walk has made $t_{RB}\sim\alpha\sigma_{RB}n\log n$
RB steps, and $t_{B}\sim(1-\alpha)\sigma_{B}n\log n$ B steps, consisting of
$m$ phases each of B and RB up to $t^{*}$. This is followed by a final ’blue
forever’ phase of length $t^{\prime}_{B}=t-t^{*}$.

So,

$\mathbb{P}(\mbox{\boldmath$A$}_{t}(v))=\left(1+O\left(\frac{\log
n}{n}\right)\right)^{m}\exp\left\\{-\frac{\pi_{v}}{\sigma_{RB}}\sum_{i\geq
0}(t_{2i+1}-t_{2i})-\frac{\pi_{v}}{\sigma_{B}}\sum_{i\geq
1}(t_{2i}-t_{2i-1})\right\\}.$ (10)

Now assuming that $t=O(n\log n)$ and because each phase has length at least
$\omega\log^{2}n$ we have $m=o(n/\log n)$, and so we have

$\displaystyle\mathbb{P}(\mbox{\boldmath$A$}_{t}(v))$
$\displaystyle\lesssim\exp\left\\{-\left(\alpha+\frac{1}{\sigma_{B}}\left(\frac{t}{n\log
n}-\alpha\sigma_{RB}\right)\right)\log n\right\\}$
$\displaystyle=\exp\left\\{-\frac{t}{\sigma_{B}n}+\alpha\sigma_{RB}\left(\frac{1}{\sigma_{B}}-\frac{1}{\sigma_{RB}}\right)\log
n\right\\}.$ (11)

For non locally tree-like vertices, using P4, we can write

$\mathbb{P}(\mbox{\boldmath$A$}_{t}(v))\lesssim e^{-t/3n}.$ (12)

Define a time $t_{0}=(1+\varepsilon)\tau_{C}$, by

$t_{0}=(1+\varepsilon)\left(\alpha\sigma_{RB}+(1-\alpha)\sigma_{B}n\log
n\right).$

We note this value of $t_{0}$, (and $t_{1}$ below), is unrelated to our
previous use of notation $t_{i}$ for a smoothed period, but is consistent with
[4].

Thus if $\varepsilon=\log^{-1/2}n$ going back to (9) and using P4, (11), we
see that for some absolute constants $\gamma_{1},\gamma_{2}>0$,

$\displaystyle C_{u}$ $\displaystyle\leq t_{0}+\sum_{v\in[n]}\sum_{\tau\geq
0}\mathbb{P}(\mbox{\boldmath$A$}_{t_{0}+\tau})$ $\displaystyle\leq
t_{0}+ne^{-\gamma_{1}\log^{1/2}n}\sum_{\tau\geq 0}e^{-\gamma_{2}\tau\log
n}+(r+b)^{3\log\log n}\sum_{\tau\geq t_{0}}e^{-\tau/3n}$
$\displaystyle=t_{0}+o(n).$ (13)

This confirms the upper bound in Theorem 1(a).

####  3.1.2 Lower bound

For the lower bound we let
$t_{1}=\tfrac{(1-\varepsilon)\alpha(r+b)}{(b-2)(r+b-1)}n\log n$ and argue that
$C_{u}\geq t_{1}$ w.h.p. Proceeding as in [4], for any vertex $u$, we can find
a set of vertices $S$ such that at time $t_{1}$, the probability the set $S$
is covered by the walk ${\mathcal{W}}_{u}$ tends to zero. Hence
$T_{G}(u)>t_{1}$ whp which together with (13) completes the proof of Theorem
1(a).

We construct $S$ as follows. Let $\sigma$ be given by (5). Let $S\subseteq[n]$
be some maximal set of locally tree-like vertices all of which are at least
distance $2\sigma+1$ apart. Thus $|S|\geq(n-r^{3\sigma})/r^{(2\sigma+1)}$.

Let $S_{1}$ denote the subset of $S$ which has not been visited by
${\mathcal{W}}_{u}$ after step $t_{1}$.

$\displaystyle\mathbb{E}|S_{1}|$ $\displaystyle\sim\sum_{v\in
S}\exp\left\\{-\frac{t_{1}}{\sigma_{B}n}+\left(1+O\left(\frac{\log
n}{n^{1/2}}\right)\right)\frac{\alpha(r+b)\log
n}{r}\left(\frac{1}{\sigma_{RB}}-\frac{1}{\sigma_{B}}\right)\right\\}$
$\displaystyle\geq(n-r^{3\sigma})r^{-(2\sigma+1)}\exp\left\\{-\frac{\varepsilon\alpha(r+b)\log
n}{(b-2)(r+b-1)}\right\\}\to\infty.$ (14)

Let $Y_{v,t}$ be the indicator for the event that ${\mathcal{W}}_{u}$ has not
visited vertex $v$ at time $t$. Let $Z=\\{v,w\\}\subset S$. We will show below
that

$\mathbb{E}(Y_{v,t_{1}}Y_{w,t_{1}})\sim\exp\left\\{-2\left(\frac{t_{1}}{\sigma_{B}n}+\left(1+O\left(\frac{\log
n}{n^{1/2}}\right)\right)\frac{\alpha(r+b)\log
n}{r}\left(\frac{1}{\sigma_{RB}}-\frac{1}{\sigma_{B}}\right)\right)\right\\}.$
(15)

Thus

$\mathbb{E}(Y_{v,t_{1}}Y_{w,t_{1}})=(1+o(1))\mathbb{E}(Y_{v,t_{1}})\mathbb{E}(Y_{w,t_{1}}).$
(16)

It follows from (14) and (16), that

$\mathbb{P}(S(t_{1})\neq
0)\geq\frac{(\mathbb{E}|S(t_{1})|)^{2}}{\mathbb{E}|S(t_{1})|^{2}}=\frac{1}{\frac{{\bf
E}|S_{t_{1}}|(|S_{t_{1}}|-1)}{({\bf
E}|S(t_{1})|)^{2}}+(\mathbb{E}|S_{t_{1}}|)^{-1}}=1-o(1).$

Going back to (10), we see that with these values of $\pi_{Z},R_{Z}$, this
completes the proof of Theorem 1(a), apart from (15) which we give next.

##### Proof of (15).

Let $\Gamma$ be obtained from $G$ by merging $v,w$ into a single node $Z$.
This node has degree $2r$ and every other node has degree $r$.

There is a natural measure preserving mapping from the set of walks in $G$
which start at $u$ and do not visit $v$ or $w$, to the corresponding set of
walks in $\Gamma$ which do not visit $Z$. Thus the probability that
${\mathcal{W}}_{u}$ does not visit $v$ or $w$ in the first $t$ steps is equal
to the probability that a random walk $\widehat{{\mathcal{W}}}_{u}$ in
$\Gamma$ which also starts at $u$ does not visit $Z$ in the first $t$ steps.

That $\pi_{Z}=\frac{2}{n}$ is clear. We also have

$R_{v}\leq R_{Z}\leq
R_{v}+\sum_{t=2\sigma+1}^{T}(\pi_{w}+\lambda^{t})=R_{v}+O(T\lambda^{2\sigma}).$

The sum here being a bound on the probability that ${\mathcal{W}}_{v}$ is at
$w$ before the end of the mixing time. The value $\lambda$ is the second
eigenvalue in P5. $\Box$

###  3.2 Congestion model: Theorem 1(b)

Let $t_{1}=(1+\varepsilon)(1+C/F)\sigma_{RB}n\log n$ where $\varepsilon>0$ is
arbitrary. The amount of time spent in a free phase is
$(1+\varepsilon)\sigma_{RB}n\log n$ and so w.h.p. $G$ will be covered.

For the lower bound, let $t_{2}=(1-\varepsilon)(1+C/F)\sigma_{RB}n\log n$. We
defer the proof that $G$ will not be covered until Section 5.4.

##  4 Proof of Theorem 2

##### Stationary distribution and mixing time.

Let $d=r+b$ be the total degree of a vertex in the red/blue coloured graph
$G$. Assume $d\geq 3$ and $G$ satisfies the conditions of Section 2.2.

In the flip model, $\rho_{R}$ (resp. $\rho_{B}$) is the probability of
transition over a given red edge (resp. blue edge). This corresponds to a
weighted graph in which $w(e_{R})=\rho_{R}$, $w(e_{B})=\rho_{B}$ for red and
blue edges respectively, all vertices $v$ have weight $w(v)=1$ and $w(G)=n$.
Thus $\pi_{RB}(v)=1/n$, and $G$ has uniform stationary distribution. For a
given set $S\subseteq V$, the conductance (bottleneck ratio) ${\Phi}_{RB}(S)$
is

${\Phi}_{RB}(S)=\frac{Q(S,S^{c})}{\pi(S)}=\frac{\sum_{v\in S,w\in
S^{c}}\pi_{v}P_{RB}(v,w)}{\sum_{v\in S}\pi_{v}}=\frac{\sum_{v\in S,w\in
S^{c}}P_{RB}(v,w)}{|S|}.$

Comparing with a simple random walk on $G$,

$\frac{1}{|S|}{\sum_{v\in S,w\in
S^{c}}P_{RB}(v,w)}\geq\min(\rho_{R},\rho_{B})\frac{E(S:S^{c})}{d|S|}=\min(\rho_{R},\rho_{B}){\Phi}_{SRW}(S),$

where $E(S:S^{c})$ is the number of edges between $S$ and $S^{c}$ and
${\Phi}_{SRW}$ refers to the conductance of a simple randpm walk.

As $G$ satisfies P5, the conductance ${\Phi}^{*}_{SRW}$ of a simple random
walk on $G$ is constant for some $0<c<1$. Assuming $\min(\rho_{R},\rho_{B})$
is also a positive constant, the conductance ${\Phi}^{*}_{PB}$ of the flip
walk is constant, i.e.,

${\Phi}^{*}_{PB}=\min_{\pi(S)\leq
1/2}{\Phi}_{RB}{\Phi}(S)\geq\min(\rho_{R},\rho_{B}){\Phi}^{*}_{SRW}.$

It follows that the flip walk on $G$ is rapidly mixing and satisfies (2) as
required.

##### Return probability.

The proof of Theorem 2 will follow from the proof in [4], once we establish
$R_{v}$ for locally-tree-like vertices. To do this we argue as follows. The
initial formulation is for the general case $r\geq 1,b\geq 2$. We then prove
existence of solutions for $r=1,b\geq 2$, and state the exact value of $R_{v}$
for the special case $r=1,b=2$. The journey to the answer is longer than we
might expect.

Consider an infinite $d$-regular tree $T_{d}$, where $r+b=d$ and in which each
vertex has $r$ red and $b$ blue edges. For discussion we regard $T_{d}$ as
rooted at a designated vertex $v$, with all edges nominally oriented outward
from $v$. With this orientation, a transition away from $v$ (resp. $u$) at a
vertex $u$, is a transition $uw$ down an out-edge of $u$. Relative to this
orientation, a vertex other than $v$ is red if its in-edge is red, and blue if
its in-edge is blue. With the exception of $v$ this induces an alternating
pattern of red and blue vertices in $T_{d}$, in which e.g., a red vertex has
$(r-1)$ red out-edges, and $b$ blue out-edges.

Recall that, in the flip model, $\rho_{R}$ (resp. $\rho_{B}$) is the
probability of transition over a given red edge (resp. blue edge). Let $f$ be
the probability of a first return to $v$ in $T_{d}$, then the expected number
of returns to $v$ is $R_{v}(T_{d})=1/(1-f)$. Let $\phi_{v,R}$ (resp.
$\phi_{v,B}$) be the probability of a return to $v$ given the particle exits
$v$ on a red (resp. blue) edge. Thus

$f=r\rho_{R}\,\phi_{v,R}+b\rho_{B}\,\phi_{v,B}.$

Let $u$ be a red vertex, and $uw$ a red edge pointing away from $u$ and thus
away from $v$. Define $\phi_{RR}=\phi_{RR}^{(u)}(uw)$ by

$\displaystyle\phi_{RR}=$ $\displaystyle\mathbb{P}(\text{ the walk returns to
}u\mid u\text{ is red and the walk exits away from }u\text{ on a red edge}),$

and define $\phi_{RB},\phi_{BB},\phi_{BR}$ similarly. Note that
$\phi_{RR}=\phi_{BR}=\phi_{v,R}=\phi_{R}$, say. For a red vertex $u$, let
$\psi_{R}(u)$ be the probability the walk moves away from $v$ at $u$, and
subsequently returns to $u$. Thus with $P(u,w)$ the colour dependent
transition probability over the edge $uw$, $\phi(uw)$ the colour dependent
return probability, and $N^{+}_{R}(u)$ the red out-neighbours of $u$ etc.,

$\psi_{R}(u)=\sum_{w\in N^{+}(u)}P(u,w)\phi(uw)=\sum_{w\in
N^{+}_{R}(u)}\rho_{R}\phi_{RR}+\sum_{w\in N^{+}_{B}(u)}\rho_{B}\phi_{RB}.$

If $u$ is red, there are $r-1$ red out-neighbours, and $b$ blue out-
neighbours, so

$\psi_{R}=(r-1)\rho_{R}\phi_{R}+b\rho_{B}\phi_{B}.$

Suppose the transition is away from $u$ over a red edge $uw$ to a red out-
neighbour $w$, then the walk moves back to $u$ with probability $\rho_{R}$ and
so

$\phi_{RR}^{(u)}(uw)=\rho_{R}+\psi_{R}\rho_{R}+\cdots+(\psi_{R})^{j}\rho_{R}+\cdots=\frac{\rho_{R}}{1-\psi_{R}}.$
(17)

Here the term $(\psi_{R})^{j}\rho_{R}$ is the probability that the walk
returns to $u$ after making $j$ returns to $w$ that do not include a visit to
$u$.

For a walk arriving at $u$, three things can happen. It moves directly back
towards $v$ (probability $\rho_{R}>0$), moves away from $u$ and returns to $u$
later (probability $\psi_{R}$), or moves away from $u$ and never returns
(probability $\xi_{R}$). Thus

$\rho_{R}+\psi_{R}+\xi_{R}=1,$ (18)

and $\psi_{R}\leq 1-\rho_{R}<1$, and similarly for $\psi_{B}<1$. This
justifies division by $1-\psi_{R}$ in (17).

We obtain

$\displaystyle\psi_{R}=$
$\displaystyle\frac{(r-1)\rho_{R}^{2}}{1-\psi_{R}}+\frac{b\rho_{B}^{2}}{1-\psi_{B}},$
(19) $\displaystyle\psi_{B}=$
$\displaystyle\frac{r\rho_{R}^{2}}{1-\psi_{R}}+\frac{(b-1)\rho_{B}^{2}}{1-\psi_{B}},$
(20) $\displaystyle f=$
$\displaystyle\frac{r\rho_{R}^{2}}{1-\psi_{R}}+\frac{b\rho_{B}^{2}}{1-\psi_{B}}.$
(21)

Do (19) and (20) always have solutions $\psi_{R},\psi_{B}$ in $[0,1]$ and if
more than one solution, which to choose? This is discussed next. Assume for
now that solutions exists. Then for a given solution $\psi_{B}$, using (20)
and (21) we see that

$f=\psi_{B}+\frac{\rho_{B}^{2}}{1-\psi_{B}}.$ (22)

As $1/R_{v}=1-f+o(1)$ in $G$, we obtain the required solution to the cover
time of $G$ as

$C_{G}\sim\frac{1}{1-f}\;n\log n.$ (23)

##### General solution in the case $r=1$.

Put $\psi_{R}=x,\psi_{B}=z$. As $r=1$ we have $\rho_{R}+b\rho_{B}=1$. Assume
$b\geq 2$ and $\rho_{R}\leq\rho_{B}$ so that $0\leq\rho_{R}\leq 1/(b+1)$. Use
(19) to get

$\frac{1}{1-x}=\frac{1-z}{1-z-b\rho_{B}^{2}},$

and substitute this for $1/(1-x)$ in (20) giving

$z=\frac{\rho_{R}^{2}(1-z)}{1-z-b\rho_{B}^{2}}+\frac{(b-1)\rho_{B}^{2}}{1-z}.$

Put $q=b\rho_{B}$ and $\rho_{R}=1-q$ where $b/(b+1)\leq q\leq 1$, to consider
$F(z)=0$ where

$F(z)=z-\frac{(1-q)^{2}(1-z)}{1-q^{2}/b-z}-\frac{(b-1)q^{2}}{b^{2}(1-z)}.$
(24)

If $\rho_{R}=1/(b+1)$ then all edges are equivalent in a $b+1$ regular tree
and the roots $z^{*}$ are $1/(b+1),b/(b+1)$. If $q=1$ (no useable red edges)
then the problem reverts to a $b$-regular tree, in which case the roots
$z^{*}$ of $F(z)$ are $1/b,(b-1)/b$.

If $b=2,q=1$, $z=1/2$ is the only root to $F(z)=0$. Ignoring this case which
corresponds to a random walk on the line, we will assume that $q<1$ and $b\geq
2$. Let $z_{0}=1-q^{2}/b$. In the interval $I_{0}=[0,z_{0}]$, $F(0)<0$,
$F(z_{0}^{-})=-\infty$. It can be checked that $F(z)$ is concave on $I_{0}$.
In the interval $I_{1}=[z_{0},1]$, $F(z_{0}^{+})=\infty$, $F(1)=-\infty$ and
$F(z)$ is monotone decreasing. So there are between one and three roots in
$[0,1]$ depending on what happens in $I_{0}$. We will establish that if $b\geq
2,\,q<1$, then $F(1/2)>0$ which implies there are two roots in $I_{0}$. We
have

$F(1/2)=\frac{1}{2}-\frac{b(1-q)^{2}}{b-2q^{2}}-\frac{2(b-1)q^{2}}{b^{2}}.$

It can be checked that $\partial F/\partial b>0$ for any fixed $q$, so as
$F(1/2)$ is monotone increasing with $b$, and $b=2$ has the largest range of
$q$, (i.e., $2/3\leq q<1$), we check this case. After some simplification we
obtain that if $b=2$,

$F(1/2)=(1-q)\left(\frac{1+q}{2}-\frac{1}{1+q}\right).$

So $F(1/2,b=2)>0$ boils down to $(1+q)^{2}>2$. As $q\geq 2/3=b/(b+1)$, and
$(5/3)^{2}>2$, it is indeed the case that $F(1/2)>0$ as required.

##### The simplest case: Theorem 2(a).

We solve $F(z)=0$, where $F(z)$ is given by (24), in the simplest case; namely
$r=1$, and $b=2$. Thus $\rho_{R}+2\rho_{B}=1$. Put $q=1-\rho_{R}=2\rho_{B}$,
and $w=1-z$ to give, after some rearrangement, $F(w)=N(w)/D(w)$. Here the
numerator $N(w)$ is

$N(w)=w^{3}-\frac{q}{2}(4-q)w^{2}+\frac{3}{4}q^{2}w-\frac{1}{8}q^{4}.$

It can be checked that $w=q/2$ is a factor of $N(w)$ and so

$N(w)=(w-q/2)(w^{2}+w(q/2)(q-3)+q^{3}/4).$

The roots of $F(w)=0$ are $q/2,\;\;(q/4)[(3-q)\pm\sqrt{9-10q+q^{2}}]$. We
prove that the smallest root $z\in[0,1]$ is indeed the correct one. We use
$\rho_{B}+\psi_{B}+\xi_{B}=1$ from (18). As $\rho_{B}=q/2$ and
$\psi_{B}=z=1-w$ we obtain $\xi_{B}=w-q/2$.

The root $w^{-}=(q/4)[(3-q)-\sqrt{9-10q+q^{2}}]$ implies $\xi_{B}<0$ for
$q<1$. As $\xi_{B}$ is a probability, this is impossible. The root $w=q/2$ (or
$w^{-}(q=1)$) imply that $\xi_{B}=0$. This corresponds to a recurrent system,
an answer we do not accept (see below). Thus the only feasible root is
$w^{+}=(q/4)[(3-q)+\sqrt{9-10q+q^{2}}]$ giving $\psi_{B}=z=1-w^{+}$, this
being the smallest root of $F(z)=0$.

We briefly sketch why the system is not recurrent. For a random walk on the
half-line $\\{0,1,2,...\\}$ starting from vertex 1, let $q,p$ be the
probability of moving left and right respectively at any vertex $i>0$. Then
assuming $q\leq p$, the probability of absorption at the origin 0, is
$\pi_{0}=q/p$. Thus for our system

$\pi_{0}\leq\max\left\\{\frac{\rho_{R}}{1-\rho_{R}},\frac{\rho_{B}}{1-\rho_{B}}\right\\}=\max\left\\{\frac{\rho_{R}}{2\rho_{B}},\frac{\rho_{B}}{\rho_{B}+\rho_{R}}\right\\}.$

As we assume $0<\rho_{R}\leq\rho_{B}$ it follows that $\pi_{0}<1$, $\xi>0$ and
the system is not recurrent.

Refer to (22) and (23). With $\psi_{B}=1-w$ and $\rho_{B}=q/2$. the value of
$\theta=1/(1-f)$ is

$\theta=\frac{1}{2}\left(\frac{1}{w+q/2}+\frac{1}{w-q/2}\right),$

The largest value of $w$ among the roots, and hence the smallest value of
$z=\psi_{B}$, gives

$\theta=\frac{2}{q(5-q+\sqrt{9-10q+q^{2}})}+\frac{2}{q(1-q+\sqrt{9-10q+q^{2}})}.$
(25)

The minimum of $\theta(q)$ is at $q=2/3$, which follows by checking the
derivative. This corresponds to $\rho_{R}=\rho_{B}=1/3$. The value $q=2/3$
gives $\theta=2$, and hence value of $C_{G}\sim 2n\log n$ in (23). This
confirms the w.h.p. cover time of a random 3-regular graph from [4] as the
minimum cover time for this model. The value of $\theta$ is plotted in Figure
1.

Figure 1:  Plot of $\theta=\theta(q)$ from (25) as $q$ varies from 0 to 1. The
minimum value of $\theta=2$ is at $q=2/3$, giving a cover time of $2n\log n$
for random 3-regular graphs. Values of $q$ for which $\rho_{R}<\rho_{B}$ are
to the right of the vertical line at $q=2/3$. The plots diverge at $q=0,1$.

##  5 The oblivious model: Proof of Theorem 3

###  5.1 Proof of Theorem 3(a).

This follows directly from Theorem 1(a).

###  5.2 Proof of Theorem 3(b).

We prove that if $b=2$, and the blue edges span a Hamilton cycle $H$, then the
cover time of an oblivious walk on $G$ with budget
$t_{1}=(1-\varepsilon)(r+1)/rn\log n$ is asymptotic to $n^{2}/2$.

Divide $H$ into $\ell=n^{\nu}$ consecutive intervals
$I_{1},I_{2},\ldots,I_{\ell}$ of length $L=n^{1-\nu}$, where
$0<\nu\leq\varepsilon/3$. Fix one such interval $I$. Let $S_{0}$ be the
locally tree-like vertices in $I$ and then choose $S$ by greedily choosing a
subset of $S_{0}$ where each pair of vertices are at distance $2\sigma+1$
apart. Note that $|S|\geq n^{1-\nu-o(1)}$.

Let $S_{1}=S_{1}(t_{1})$ denote the subset of $S$ which has not been visited
by the walk ${\mathcal{W}}$ at step $t_{1}=(1-\varepsilon)(d-1)/(d-2)n\log n$,
where $d=r+b$ as usual, and $b=2$. Let $X_{v}$ be the indicator that vertex
$v\in S$ is unvisited at step $t_{1}$. Thus applying Lemma 4 as in Section
3.1, we obtain

$\displaystyle\mathbb{E}|S_{1}|=$ $\displaystyle\sum_{v\in S}X_{v}=\sum_{v\in
S}\exp\left\\{-(1+\eta)\frac{R_{v}}{n}\;(1-\varepsilon)\frac{d-1}{d-2}n\log
n\right\\}$ $\displaystyle=$
$\displaystyle\frac{n^{1-\nu}}{d^{3\sigma}}\;n^{-1+\varepsilon+o(1)}=n^{\delta},$

where $\delta=\varepsilon-\nu+o(1)$. Here $\eta=o(1)$ combines the errors
arising from estimating $R_{v}=(d-2)/(d-1)(1+o(1))$, the convergence via (2)
of ${\mathcal{W}}$ to $\pi_{v}=1/n$, and the approximation of
$p_{v}=\pi_{v}/R_{v}(1+O(T\pi_{v})$ in Lemma 4.

We next prove that $|S_{1}(t_{1})|>0$ by adapting the approach used in Section
3.1.2. When calculating the variance of $|S_{1}|$ by contraction of pairs
$u,v\in S_{1}$, the main error $\nu$ comes from the change in $R_{v}$ due to
the probability that the walk travels between the pair of contracted vertices
$u,v$ in the mixing time. From [4] this is

$\beta=\sum_{t=2\sigma}^{T_{G}}(\pi_{v}+\lambda^{t})=o(1/\log n)$ (26)

assuming $\lambda=1-\theta$ for some $\theta>0$ constant, and $\sigma$ is
given by (5).

For $X=\sum X_{v}$,

$\displaystyle\mathbb{E}X(X-1)=$ $\displaystyle\sum_{u,v\in
S}\mathbb{E}X_{u}X_{v}$ $\displaystyle=$ $\displaystyle\sum_{u,v\in
S}\exp\left\\{-(1+\eta)\frac{2}{n}R_{(u,v)}(1+\beta)\;(1-\varepsilon)\frac{d-1}{d-2}n\log
n\right\\}$ $\displaystyle=$ $\displaystyle
n^{2\delta}n^{O(\beta/n)}=(\mathbb{E}S_{1})^{2}\left(1+O\left(\frac{1}{n}\right)\right),$

where $\beta$ is defined in (26). So,

$\displaystyle{\bf Var}|S_{1}|=$
$\displaystyle\mathbb{E}X(X-1)+\mathbb{E}|S_{1}|-(\mathbb{E}|S_{1}|)^{2}$
$\displaystyle=$
$\displaystyle\mathbb{E}|S_{1}|\left(1+O\left(\frac{\mathbb{E}|S_{1}|}{n}\right)\right)$
$\displaystyle=$ $\displaystyle\mathbb{E}|S_{1}|(1+o(1)).$

Using the Chebychev Inequality we deduce that

$\mathbb{P}(S_{1}=\emptyset)<\mathbb{P}(|S_{1}-\mathbb{E}S_{1}|\geq\mathbb{E}S_{1}/2)\leq\frac{5}{\mathbb{E}S_{1}}=O\left(\frac{1}{n^{\delta}}\right).$

Let $\nu=\varepsilon/3$. The expected number of segments with
$S_{1}=\emptyset$ is at most

$O\left(\frac{\ell}{n^{\delta}}\right)=O\left(\frac{n^{\nu}}{n^{\varepsilon-\nu+o(1)}}\right)=\frac{1}{n^{\nu+o(1)}}.$

We conclude that w.h.p. each segment $I$ has at least one unvisited vertex in
$S_{1}(I)$ when the budget runs out at $t_{1}$. Thus we have to effectively
walk around the cycle to reach them all. This requires $\sim n^{2}/2$ time
w.h.p. Let $C_{\sc OBV}(\varepsilon)$ be the cover time of an oblivious walk
with budget at most $t_{1}=(1-\varepsilon)C(G)$, then

$C_{\sc OBV}(\varepsilon)\approx C(C_{n})\sim\frac{n^{2}}{2}.$

###  5.3 Proof of Theorem 3(c).

We first observe that the space ${\cal F}(2,r)$ of graphs formed by the union
of a random 2-factor and a random $r$-regular graph is contiguous to the space
${\cal G}(r+2)$ of random $(r+2)$-regular graphs, see for example Wormald
[18]. So, the Red/Blue walk has mixing time $O(\log n)$ w.h.p. (we apply
contiguity to the property of having a small second eigenvalue as in P5).

We next prove a basic lemma on random 2-factors.

######  Lemma 6.

W.h.p. a random 2-factor contains at least 2 cycles of length at least
$cn/(\log^{2}n)$ for some absolute constant $c>0$.

###### Proof.

We begin by arguing that the number of cycles in a random 2-factor is $O(\log
n)$ w.h.p. It follows that w.h.p. there is at least one cycle of length
$\Omega(n/\log n)$, among which we choose the longest. We then argue that
w.h.p. the maximum length of this cycle is at most $\ell=n-n/\log n$. As at
least $n/\log n$ vertices remain after removing this cycle it follows that
there is another cycle of length at least $\Omega(n/\log^{2}n)$.

##### Number of cycles.

Let $S_{n}$ denote the set of permutations of $[n]$, and let
$S^{\prime}\subseteq S_{n}$ be the subset with minimum cycle length 3. We can
obtain a random 2-factor $F$ by choosing a random permutation from
$S^{\prime}$. This is not done uniformly, but we choose permutation $\pi$ with
probability proportional to $\tfrac{1}{2^{\ell}}$ where $\ell=\ell(\pi)$ is
the number of cycles in $\pi$. Having chosen $\pi$ we obtain our 2-factor by
ignoring orientation. A 2-factor $F$ with $\ell=\ell(F)$ cycles arises from
$2^{\ell}$ distinct permutations and so a 2-factor $F$ is chosen with
probability $2^{\ell(F)}\cdot\frac{1}{2^{\ell(F)}}\cdot\frac{1}{M}$, where
$M=\sum_{\pi\in S^{\prime}}\frac{1}{2^{\ell(\pi)}}$. Now the proof of
Proposition 2(a) of Karp [11] implies that

$\mathbb{P}(\ell(\pi)\geq a\log n)\leq\mathbb{P}(Bin(a\log
n,1/2)\leq\log_{2}n)\leq n^{-a/3}\qquad\text{for }a\geq 2.$ (27)

So, $\mathbb{P}(\ell(\pi)\geq 2\log n)\leq n^{-2/3}$. Because
$|S^{\prime}|/|S_{n}|=c\sim e^{-3/2}$ this also holds for $S^{\prime}$.
Summing over $S^{\prime}$,

$M=\sum_{\ell(\pi)<2\log_{2}n}\frac{1}{2^{\ell(\pi)}}+\sum_{\ell(\pi)\geq
2\log_{2}n}\frac{1}{2^{\ell(\pi)}}\geq\frac{cn!(1-O(n^{-2/3}))}{n^{2}}.$

And

$\mathbb{P}(\ell(F)\geq 3\log_{2}n)=\sum_{m\geq 3\log_{2}n}\frac{|\\{\pi\in
S^{\prime}:\ell(\pi)=m\\}|}{2^{m}M}=O(n^{-1}).$

##### Longest cycle.

We use the configuration model of Bollobás [2]. In this model the expected
number of cycles of length at least $\ell\geq\ell_{0}=n-n/\log n$ is

$\displaystyle\sum_{k=\ell_{0}}^{n}\binom{n}{k}\frac{(k-1)!}{2}\cdot
2^{k}\cdot\frac{(2n-2k)!}{(n-k)!2^{n-k}}\cdot\frac{n!2^{n}}{(2n)!}$
$\displaystyle=\sum_{k=\ell_{0}}^{n}\frac{2^{2k}}{2k}\frac{n!n!}{(2n)!}{2n-2k\choose
n-k}$ $\displaystyle=$ $\displaystyle
O\left(\frac{1}{\sqrt{n}}\right)+O(\sqrt{n})\sum_{k=\ell_{0}}^{n-1}\frac{1}{\sqrt{n-k}}\frac{1}{k}$
$\displaystyle=$ $\displaystyle O\left(\frac{1}{\sqrt{n}}\right)+O(\sqrt{\log
n})\;\log\left(\frac{n}{n-n/\log n}\right)$
$\displaystyle=O\left(\frac{1}{\sqrt{\log n}}\right).$

∎ Given Lemma 6 we proceed as follows: let $C_{1},\,C_{2}$ be two of the
cycles of length at least $\Omega(n/\log^{2}n)$, as promised by Lemma 6. As in
Section 5.2, let $L=n^{1-\nu}$ where $\nu>0$. Partition each of the cycles
$C_{1},\,C_{2}$ into intervals of length $L$. We know that w.h.p. at time
$t_{1}=(1-\varepsilon)(d-1)/(d-2)n\log n$, (where $d=r+b$) there will be
unvisited vertices in $C_{1},\,C_{2}$ and the result follows.

###  5.4 Finishing the proof of Theorem 1(b). The lower bound

For the lower bound, let $t_{2}=(1-\varepsilon)(1+C/F)\sigma_{RB}n\log n$. The
length $C,F$ of the charged and free periods are fixed and in constant
proportion. The $t_{2}$ steps are divided into $\tau=n^{\theta}$ phases of
equal length $C+F=n^{1-\theta+o(1)}$. The total amount of time spent in free
phases is $(1-\varepsilon)\sigma_{RB}n\log n$.

In phase $1\leq i\leq\tau$, during a charged period $C$ the walk will w.h.p.
cover an interval $J_{i}$ of the Hamilton cycle of length
$n^{(1-\theta)/2+o(1)}$. Let $I_{1},I_{2},\ldots,I_{\ell}$ be intervals of
length $L=n^{1-\nu}$, where $\nu=\varepsilon/3$ as in Section 5.2. In total,
the intervals $J_{1},J_{2},\ldots,J_{\tau}$ cover at most
$n^{\theta}\,n^{(1+\theta)/2+o(1)}$ vertices.

We require $n^{\theta+(1+\theta)/2+o(1)}\ll L=n^{1-\varepsilon/3}$, which is
satisfied by $\theta=(1-\varepsilon)/4$. With this value of $\theta$, w.h.p.
each interval $I_{j}$ $j=1,...,\ell$ will contain a vertex unvisited during
the free phases. This completes the proof of Theorem 1(b).

## References

  * [1] David Aldous and James Allen Fill. Reversible Markov Chains and Random Walks on Graphs. Unfiished monograph, 2002 (recompiled version, 2014).
  * [2] B. Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled graphs. European Journal on Combinatorics 1, 311-316, (1980).
  * [3] B. Bollobás and F. R. K. Chung. The diameter of a cycle plus a random matching. SIAM Journal on Discrete Mathematics 1, 328–333 (1988).
  * [4] C. Cooper and A. M. Frieze, The cover time of random regular graphs, SIAM Journal on Discrete Mathematics, 18 (2005) 728-740.
  * [5] C. Cooper and A. M. Frieze, The cover time of random digraphs, Stationary distribution and cover time of random walks on random digraphs, Journal of Combinatorial Theory B 102 (2012) 329-362.
  * [6] C. Cooper and A. M. Frieze, The cover time of random geometric graphs, Random Structures and Algorithms 38 (2011) 324-349.
  * [7] C. Cooper and A. M. Frieze, The cover time of the giant component of $G_{n,p}$, Random Structures and Algorithms, 32 (2008) 401–439.
  * [8] C. Cooper, A. M. Frieze and T. Radzik, The cover times of random walks on hypergraphs. Theoretical Computer Science, 509 (2013) 51–69.
  * [9] D. Coppersmith, P. Doyle, P. Raghavan, M. Snir, Random Walks on Weighted Graphs, and Applications to On-line Algorithms (Preliminary Version). STOC 1990: 369-378
  * [10] P. Holme, Modern temporal network theory: A colloquium, Eur. Phys. J. B 88 (2015) 234.
  * [11] R. Karp, A patching algorithm for the non-symmetric traveling salesman problem, SIAM Journal on Computing 8 (1979) 561–573.
  * [12] J. H. B. Kemperman. The oscillating random walk. Stochastic Processes and their Applications 2, l-29, (1974).
  * [13] David A Levin and Yuval Peres. Markov Chains and Mixing Times. American Mathematical Society., 2017.
  * [14] S. N. Majumdar, F. Mori, and P. Vivo. Cost of Diffusion: Nonlinearity and Giant Fluctuations, Physical Review Letters 130, 237102 (2023).
  * [15] S. N. Majumdar, F. Mori, and P. Vivo, Nonlinear-cost random walk: Exact statistics of the distance covered for fixed budget, Physical Review E 108, 064122 (2023).
  * [16] R. Robinson and N. Wormald, Almost all cubic graphs are Hamiltonian, Random Structures and Algorithms 3 (1992) 117-125.
  * [17] Watts, D. J.; Strogatz, S. H. (1998). Collective dynamics of ’small-world’ networks, Nature 393 (6684) 440–442.
  * [18] N. Wormald, Models of random regular graphs, Surveys in Combinatorics (1999) 239-298.