# Cover Time in Edge-Uniform Stochastically-Evolving Graphs +
## 4 Cover Time with Zero-Step History
### Random Walk with a Delay
In particular, given the underlying graph \(G\), we design an electrical network, \(N(G)\), with the same edges as \(G\), but where each edge has a resistance of \(r=\frac{1}{p}\) ohms. Let \(H_{u,v}\) stand for the hitting time from node \(u\) to node \(v\) in \(G\), i.e., the expected number of time steps until the agent reaches \(v\) after starting from \(u\) and following RWD. Furthermore, let \(\phi_{u,v}\) declare the electrical potential difference between nodes \(u\) and \(v\) in \(N(G)\) when, for each \(w\in V\), we inject \(d(w)\) amperes of current into \(w\) and withdraw \(2m\) amperes of current from a single node \(v\). We now upper-bound the cover time of \(G\) under RWD by correlating \(H_{u,v}\) to \(\phi_{u,v}\). Lemma 1: _For all \(u,v\in V\), \(H_{u,v}=\phi_{u,v}\) holds._  
Proof: Let us denote by \(C_{uw}\) the current flowing between two neighbouring nodes \(u\) and \(w\). Then, \(d(u)=\sum_{w\in N(u)}C_{uw}\), since at each node, the total inward current must match the total outward current ([PERSON]'s first law). Moving forward, \(C_{uw}=\phi_{uw}/r=\phi_{uw}/(1/p)=p\cdot\phi_{uw}\) by [PERSON]'s law. Finally, \(\phi_{uw}=\phi_{uw}-\phi_{uw}\), since the sum of electrical potential differences forming a path is equal to the total electrical potential difference of the path ([PERSON]'s second law). Overall, we can rewrite \(d(u)=\sum_{w\in N(u)}p(\phi_{u,v}-\phi_{w,v})=d(u)\cdot p\cdot\phi_{u,v}-p\sum_ {w\in N(u)}\phi_{w,v}\). Rearranging gives:  
\[\phi_{u,v}=\frac{1}{p}+\frac{1}{d(u)}\sum_{w\in N(u)}\phi_{w,v}.\]  
Regarding the hitting time from \(u\) to \(v\), we rewrite it based on the first step:  
\[H_{u,v}=\frac{1}{p}+\frac{1}{d(u)}\sum_{w\in N(u)}H_{w,v}\]  
since the first addend represents the expected number of steps for the selected edge to appear due to RWD and the second addend stands for the expected time for the rest of the walk. Wrapping it up, since both formulas above hold for each \(u\in V\setminus\{v\}\), therefore inducing two identical linear systems of \(n\) equations and \(n\) variables, it follows that there exists a unique solution to both of them, and \(H_{u,v}=\phi_{u,v}\). In the lemma below, let \(R_{u,v}\) stand for the effective resistance between \(u\) and \(v\), i.e., the electrical potential difference induced when flowing a current of one ampere from \(u\) to \(v\). Lemma 2: _For all \(u,v\in V\), \(H_{u,v}+H_{v,u}=2 mR_{u,v}\) holds._  
Proof: Similar to the definition of \(\phi_{u,v}\) above, one can define \(\phi_{v,u}\) as the electrical potential difference between \(v\) and \(u\) when \(d(w)\) amperes of current are injected into each node \(w\) and \(2m\) of them are withdrawn from node \(u\). Next, note that changing all currents' signs leads to a new network where for the electrical potential difference, namely \(\phi^{\prime}\), it holds \(\phi^{\prime}_{u,v}=\phi_{v,u}\). We can now apply the superposition theorem (see Section 13.3 in [24]) and linearly superpose the two networks implied from \(\phi_{u,v}\) and \(\phi^{\prime}_{u,v}\), creating a new one where \(2m\) amperes are injected into \(u\), \(2m\) amperes are withdrawn from \(v\) and no current is injected or withdrawn at any other node. Let \(\phi^{\prime\prime}_{u,v}\) stand for the electrical potential difference between \(u\) and \(v\) in this last network. By the superposition argument, we get \(\phi^{\prime\prime}_{u,v}=\phi_{u,v}+\phi^{\prime}_{u,v}=\phi_{u,v}+\phi_{v,u}\), while from [PERSON]'s law, we get \(\phi^{\prime\prime}_{u,v}=2m\cdot R_{u,v}\). The proof concludes by combining these two observations and applying Lemma 1. For any connected underlying graph \(G\) evolving under the zero-step history EUE, the cover time for RWD is at most \(2m(n-1)/p\). Proof. : Consider a spanning tree \(T\) of \(G\). An agent, starting from any node, can visit all nodes by performing a Eulerian tour on the edges of \(T\) (crossing each edge twice).