Let $X$ be a lazy random walk on a graph $G$. If $G$ is undirected, then the mixing time is upper bounded by the maximum hitting time of the graph. This fails for directed chains, as the biased random walk on the cycle $\mathbb{Z}_n$ shows. However, we establish that for Eulerian digraphs, the mixing time is $O(mn)$, where $m$ is the number of edges and $n$ is the number of vertices. In the reversible case, the mixing time is robust to the change of the laziness parameter. Surprisingly, in the directed setting the mixing time can be sensitive to such changes. We also study exploration and cover times for random walks on Eulerian digraphs and prove universal upper bounds in analogy to the undirected case.

Static wireless networks are by now quite well understood mathematically through the random geometric graph model. By contrast, there are relatively few rigorous results on the practically important case of mobile networks. In this paper we consider a natural extension of the random geometric graph model to the mobile setting by allowing nodes to move in space according to Brownian motion. We study three fundamental questions in this model: detection (the time until a given target point—which may be either fixed or moving—is detected by the network), coverage (the time until all points inside a finite box are detected by the network), and percolation (the time until a given node is able to communicate with the giant component of the network). We derive precise asymptotics for these problems by combining ideas from stochastic geometry, coupling and multi-scale analysis. We also give an application of our results to analyze the time to broadcast a message in a mobile network.

We propose a new model for file-sharing peer-to-peer (P2P) networks that mimics the incentives provided by the popular BitTorrent system. In it, larger files are split into chunks and a peer can download or swap only one chunk at a time. We propose a Markov chain model in continuous time that resembles a stochastic epidemic/coagulation model. We prove that the Markov chain is approximated by a differential equation which, by itself, can give some rough information about the performance of the system. Finally, using this model, we explore the performance of BitTorrent-like incentives for an open system with peer departures and arrivals and a single file (torrent) with two chunks.