# Cover Time in Edge-Uniform Stochastically-Evolving Graphs +
## 4 Cover Time with Zero-Step History
### Random Walk on What Is Available  
Random walk with a delay does provide a nice connection to electrical network theory. However, depending on \(p\), there could be long periods of time where the agent is simply standing still at the same node. Since the walk is random anyway, waiting for an edge to appear may not sound very wise. Hence, we now analyse the strategy of a Random Walk on what is Available (shortly RWA). That is, suppose the agent has just arrived at a node \(v\) after the second stage at time step \(t\), and then, \(E_{t+1}\) is fixed after the first stage at time step \(t+1\). Now, the agent picks uniformly at random only amongst the alive incident edges at time step \(t+1\). Let \(d_{t+1}(v)\) stand for the degree of node \(v\) in \(G_{t+1}\). If \(d_{t+1}(v)=0\), then the agent does not move at time step \(t+1\). Otherwise, if \(d_{t+1}(v)>0\), the agent selects an alive incident edge each having probability \(\frac{1}{d_{t+1}(p)}\). The agent then follows the selected edge to complete the second stage of time step \(t+1\) and repeats the strategy. In a nutshell, the agent keeps moving randomly on available edges and only remains on the same node if no edge is alive at the current time step. Below, let \(\delta=\min_{v\in V}d(v)\) and \(\Delta=\max_{v\in V}d(v)\). For any connected underlying graph \(G\) with min-degree \(\delta\) and max-degree \(\Delta\) evolving under the zero-step history EUE, the cover time for RWA is at least \(C_{G}/(1-(1-p)^{\Delta})\) and at most \(C_{G}/(1-(1-p)^{\delta})\). Proof. : Suppose the agent follows RWA and has reached node \(u\in V\) after time step \(t\). Then, \(G_{t+1}\) becomes fixed, and the agent selects uniformly at random a neighbouring edge to which to move. Let \(M_{uv}\) (where \(v\in\{w\in V:(u,w)\in E\}\)) stand for a random variable taking value one if the agent moves to node \(v\) and zero otherwise. For \(k=1,2,\ldots,d(u)=d\), let \(A_{k}\) stand for the event that \(d_{t+1}(u)=k\). Therefore, \(\Pr(A_{k})=(^{d}_{k})p^{k}(1-p)^{d-k}\) is exactly the probability \(k\) out of the \(d\) edges existing since each edge exists independently with probability \(p\). Now, let us consider the probability \(\Pr(M_{uv}=1|A_{k})\): the probability \(v\) will be reached given that \(k\) neighbours are present. This is exactly the product of the probability that \(v\) is indeed in the chosen \(k\)-tuple (say \(p_{1}\)) and the probability that then \(v\) is chosen uniformly at random (say \(p_{2}\)) from the \(k\)-tuple. \(p_{1}=(^{d-1}_{k-1})/(^{d}_{k})=\frac{k}{d}\), since the model is edge-uniform, and we can fix \(v\) and choose any of the \((^{d-1}_{k-1})\)\(k\)-tuples with \(v\) in them out of the \((^{d}_{k})\) total ones. On the other hand, \(p_{2}=\frac{1}{k}\) by uniformity. Overall, we get \(\Pr(M_{uv}=1|A_{k})=p_{1}\cdot p_{2}=\frac{1}{d}\). We can now apply the total probability law to calculate:  
\[\Pr(M_{uv}=1)=\sum_{k=1}^{d}\Pr(M_{uv}=1|A_{k})\Pr(A_{k})=\tfrac{1}{d}\sum_{k =1}^{d}(^{d}_{k})p^{k}(1-p)^{d-k}=\tfrac{1}{d}(1-(1-p)^{d})\]  
To conclude, let us reduce RWA to RWD. Indeed, in RWD, the equivalent transition probability is \(\Pr(M_{uv}=1)=\frac{1}{d}p\), accounting both for the uniform choice and the delay \(p\). Therefore, the RWA probability can be viewed as \(\frac{1}{d}p^{\prime}\), where \(p^{\prime}=(1-(1-p)^{d})\). To achieve edge-uniformity, we set \(p^{\prime}=(1-(1-p)^{\delta})\), which lower bounds the delay of each edge, and finally, we can apply the same RWD analysis by substituting \(p\) by \(p^{\prime}\). Similarly, we can set the upper-bound delay \(p^{\prime\prime}=(1-(1-p)^{\Delta})\) to lower bound the cover time. Applying Theorem 2 completes the proof. The value of \(\delta\) used to lower-bound the transition probability may be a harsh estimate for general graphs. However, it becomes quite more accurate in the special case of a \(d\)-regular underlying graph where \(\delta=\Delta=d\). To conclude this section, we provide a worst-case lower bound on the cover time based on similar techniques as above.