# Cover Time in Edge-Uniform Stochastically-Evolving Graphs +
## 1 Introduction
### Our Results  
We define a general model of stochastically-evolving graphs, where each possible edge evolves independently, but all of them evolve following the same stochastic rule. Furthermore, the stochastic rule may take into account the last \(k\) states of a given edge. The motivation for such a model lies in several practical examples from networking where the existence of an edge in the recent past means it is likely to exist in the near future, e.g., for telephone or Internet links. In some other cases, existence may mean that an edge has \"served its purpose\" and is now unlikely to appear in the near future, e.g., due to a high maintenance cost. The model is a discrete-time one following previous work in the computer science literature. Moreover, as a first start and for mathematical convenience, it is formalized as a synchronous system, where all possible edges evolve concurrently in distinct rounds (each round corresponding to a discrete time step). Special cases of our model have appeared in previous literature, e.g., in [9; 10] for \(k=0\) and in the line of work starting from [5] for \(k=1\); however, they only consider special graph topologies (like ring and clique). On the other hand, the model we define is general in the sense that no assumptions, aside from connectivity, are made on the topology of the underlying graph and any amount of history is allowed in the stochastic rule. Thence, we believe it can be valued as a basis for more general results to follow, capturing search or communication tasks in such dynamic graphs. We hereby provide the first known bounds relative to the cover time of a simple random walk taking place in such stochastically-evolving graphs for \(k=0\). To do so, we make use of a simple, yet fairly useful, modified random walk, namely the Random Walk with a Delay (RWD), where at each time step, the agent is choosing uniformly at random from the incident edges of the static underlying graph and then waits for the chosen edge to become alive in order to traverse it. Despite the fact that this strategy may not sound naturally-motivated enough, it can act as a handy tool when studying other, more natural, random walk models, as in the case of this paper. Indeed, we study the natural random walk on such graphs, namely the Random Walk on what is Available (RWA), where at each time step, the agent only considers the currently alive incident edges and chooses to traverse one out of them uniformly at random. For the case \(k=0\), that is when each edge appears at each round with a fixed probability \(p\) regardless of history, we prove that the cover time for RWD is upper bounded by \(C_{G}/p\), where \(C_{G}\) is the cover time of a simple random walk on the (static) underlying graph \(G\). The result can be obtained both by a careful mapping of the RWD walk to its corresponding simple random walk on the static graph and by generalizing the standard electrical network theory literature in [17; 18]. Later, we proceed to prove that the cover time for RWA is between \(C_{G}/(1-(1-p)^{\Delta})\) and \(C_{G}/(1-(1-p)^{\delta})\), where \(\delta\), respectively \(\Delta\), is the minimum, respectively maximum, degree of the underlying graph. The main idea here is to reduce RWA to an RWD walk, where at each step, the traversal delay is lower, respectively upper, bounded by \((1-(1-p)^{\delta})\), respectively \((1-(1-p)^{\Delta})\). For \(k=1\), the stochastic rule takes into account the previous, one time step ago, state of the edge. If an edge was not present, then it becomes alive with probability \(p\), whereas if it was alive, then it dies with probability \(q\). For RWD, we show a \(C_{G}/\xi_{min}\) upper bound by considering the minimum probability guarantee of existence at each round, i.e., \(\xi_{min}=\min\{p,1-q\}\). Similarly, we show a \(C_{G}/\xi_{max}\) lower bound, where \(\xi_{max}=\max\{p,1-q\}\).