# Cover Time in Edge-Uniform Stochastically-Evolving Graphs +
## 4 Cover Time with Zero-Step History
### Random Walk with a Delay  
A first approach toward covering \(G\) with a single agent is the following: The agent is randomly walking \(G\) as if all edges were present, and when an edge is not present, it just waits for it to appear in a following time step. More formally, suppose the agent arrives on a node \(v\in V\) with (static) degree \(d(v)\) at the second stage of time step \(t\). Then, after the graph is fixed for time step \(t+1\), the agent selects a neighbour of \(v\), say \(u\in N(v)\), uniformly at random, i.e., with probability \(\frac{1}{d(v)}\). If \((v,u)\in E_{t+1}\), then the agent moves to \(u\) and repeats the above procedure. Otherwise, it remains on \(v\) until the first time step \(t^{\prime}>t+1\) such that \((v,u)\in E_{t^{\prime}}\) and then moves to \(u\). This way, \(p\) acts as a delay probability, since the agent follows the same random walk it would on a static graph, but with an expected delay of \(\frac{1}{p}\) time steps at each node. Notice that, in order for such a strategy to be feasible, each node must maintain knowledge about its neighbours in the underlying graph; not just the currently alive ones. From now on, we refer to this strategy for the agent as the Random Walk with a Delay (RWD). Now, let us upper bound the cover time of RWD by exploiting its strong correlation to a simple random walk on the underlying graph \(G\) via [PERSON]'s equation (Theorem 1). Below, let \(C_{G}\) stand for the cover time of a simple random walk on the static graph \(G\). **Theorem 1** ([23]). : _Let \(X_{1},X_{2},\ldots,X_{N}\) be a sequence of real-valued, independent and identically distributed random variables, where \(N\) is a nonnegative integer random variable independent of the sequence (in other words, a stopping time for the sequence). If each \(X_{i}\) and \(N\) have finite expectations, then it holds:_  
\[E[X_{1}+X_{2}+\ldots+X_{N}]=E[N]\cdot E[X_{1}]\]  
**Theorem 2**. : _For any connected underlying graph \(G\) evolving under the zero-step history EUE, the cover time for RWD is expectedly \(C_{G}/p\)._  
Proof. : Consider a Simple Random Walk (SRW) and an RWD (under the EUE model) taking place on a given connected graph \(G\). Given that RWD decides on the next node to visit uniformly at random based on the underlying graph, that is in exactly the same way SRW does, we use a coupling argument to enforce RWD and SRW to follow the exact same trajectory, i.e., sequence of visited nodes. Then, let the trajectory end when each node in \(G\) has been visited at least once, and denote by \(T\) the total number of node transitions made by the agent. Such a trajectory under SRW will cover all nodes in expectedly \(E[T]=C_{G}\) time steps. On the other hand, in the RWD case, for each transition, we have to take into account the delay experienced until the chosen edge becomes available. Let \(D_{i}\geq 1\) be a random variable, where \(1\leq i\leq T\) stands for the actual delay corresponding to node transition \(i\) in the trajectory. Then, the expected number of time steps till the trajectory is realized is given by \(E[D_{1}+\ldots+D_{T}]\). Since the random variables \(D_{i}\) are independent and identically distributed by the edge-uniformity of our model, \(T\) is a stopping time for them and all of them have finite expectations, then by Theorem 1, we get: \(E[D_{1}+\ldots+D_{T}]=E[T]\cdot E[D_{1}]=C_{G}\cdot 1/p\). For an explicit general bound on RWD, it suffices to use \(C_{G}\leq 2m(n-1)\) proven in [2]. Another way to analyse the above procedure is to make use of a modified version of the standard literature approach of electrical networks and random walks [17; 18]. This point of view gives us expressions for the hitting time between any two nodes of the underlying graph. That is, we hereby (in Lemmata 1, 2 and Theorem 3) provide a generalization of the results given in [17; 18], thus correlating the hitting and commute times of RWD with an electrical network analogue and reaching a conclusion for the cover time similar to the one of Theorem 2.