Cover Time in EdgeUniform StochasticallyEvolving Graphs We define a general model of stochasticallyevolving graphs, namely the edgeuniform stochasticallyevolving graphs. In this model, each possible edge of an underlying general static graph evolves independently being either alive or dead at each discrete time step of evolution following a (Markovian) stochastic rule. The stochastic rule is identical for each possible edge and may depend on the past     k xe2x89xa5 0     observations of the edgexe2x80x99s state. We examine two kinds of random walks for a single agent taking place in such a dynamic graph: (i) The Random Walk with a Delay (RWD), where at each step, the agent chooses (uniformly at random) an incident possible edge, i.e., an incident edge in the underlying static graph, and then, it waits till the edge becomes alive to traverse it. (ii) The more natural Random Walk on what is Available (RWA), where the agent only looks at alive incident edges at each time step and traverses one of them uniformly at random. Our study is on bounding the cover time, i.e., the expected time until each node is visited at least once by the agent. For RWD, we provide a first upper bound for the cases     k  0 , 1     by correlating RWD with a simple random walk on a static graph. Moreover, we present a modified electrical network theory capturing the     k  0     case. For RWA, we derive some first bounds for the case     k  0    , by reducing RWA to an RWDequivalent walk with a modified delay. Further, we also provide a framework that is shown to compute the exact value of the cover time for a general family of stochasticallyevolving graphs in exponential time. Finally, we conduct experiments on the cover time of RWA in edgeuniform graphs and compare the experimental findings with our theoretical bounds.

Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths Search patterns of randomly oriented steps of different lengths have been observed on all scales of the biological world, ranging from the microscopic to the ecological, including in protein motors, bacteria, Tcells, honeybees, marine predators, and more. Through different models, it has been demonstrated that adopting a variety in the magnitude of the step lengths can greatly improve the search efficiency. However, the precise connection between the search efficiency and the number of step lengths in the repertoire of the searcher has not been identified. Motivated by biological examples in onedimensional terrains, a recent paper studied the best cover time on an nnode cycle that can be achieved by a random walk process that uses k step lengths. By tuning the lengths and corresponding probabilities the authors therein showed that the best cover time is roughly n 1Theta(1k). While this bound is useful for large values of k, it is hardly informative for small k values, which are of interest in biology. In this paper, we provide a tight bound for the cover time of such a walk, for every integer k u003e 1. Specifically, up to lower order polylogarithmic factors, the upper bound on the cover time is a polynomial in n of exponent 1 1(2k1). For k  2, 3, 4 and 5 the exponent is thus 43 , 65 , 87 , and 109 , respectively. Informally, our result implies that, as long as the number of step lengths k is not too large, incorporating an additional step length to the repertoire of the process enables to improve the cover time by a polynomial factor, but the extent of the improvement gradually decreases with k.