Abstract:
The mixing time of a discrete-time quantum walk on the hypercube is considered. The mean probability distribution of a Markov chain on a hypercube is known to mix to a uniform distribution in time O(n log n). We show that the mean probability distribution of a discrete-time quantum walk on a hypercube mixes to a (generally non-uniform) distribution pi(x) in time O(n) and the stationary distribution is determined by the initial state of the walk. An explicit expression for pi(x) is derived for the particular case of a symmetric walk. These results are consistent with those obtained previously for a continuous-time quantum walk. The effect of decoherence due to randomly breaking links between connected sites in the hypercube is also considered. We find that the probability distribution mixes to the uniform distribution as expected. However, the mixing time has a minimum at a critical decoherence rate $p \approx 0.1$. A similar effect was previously reported for the QW on the N-cycle with decoherence from repeated measurements of position. A controlled amount of decoherence helps to obtain--and preserve--a uniform distribution over the $2^n$ sites of the hypercube in the shortest possible time.

Abstract:
We establish conditions on sequences of graphs which ensure that the mixing times of the random walks on the graphs in the sequence converge. The main assumption is that the graphs, associated measures and heat kernels converge in a suitable Gromov-Hausdorff sense. With this result we are able to establish the convergence of the mixing times on the largest component of the Erdos-Renyi random graph in the critical window, sharpening previous results for this random graph model. Our results also enable us to establish convergence in a number of other examples, such as finitely ramified fractal graphs, Galton-Watson trees and the range of a high-dimensional random walk.

Abstract:
Given a finite graph G, a vertex of the lamplighter graph consists of a zero-one labeling of the vertices of G, and a marked vertex of G. For transitive graphs G, we show that, up to constants, the relaxation time for simple random walk in corresponding lamplighter graph is the maximal hitting time for simple random walk in G, while the mixing time in total variation on the lamplighter graph is the expected cover time on G. The mixing time in the uniform metric on the lamplighter graph admits a sharp threshold, and equals |G| multiplied by the relaxation time on G, up to a factor of log |G|. For the lamplighter group over the discrete two dimensional torus of sidelength n, the relaxation time is of order n^2 log n, the total variation mixing time is of order n^2 log^2 n, and the uniform mixing time is of order n^4. In dimension d>2, the relaxation time is of order n^d, the total variation mixing time is of order n^d log n, and the uniform mixing time is of order n^{d+2}. These are the first examples we know of of finite transitive graphs with uniformly bounded degrees where these three mixing time parameters are of different orders of magnitude.

Abstract:
Mixing properties of discrete-time quantum walks on two-dimensional grids with torus-like boundary conditions are analyzed, focusing on their connection to the complexity of the corresponding abstract search algorithm. In particular, an exact expression for the stationary distribution of the coherent walk over odd-sided lattices is obtained after solving the eigenproblem for the evolution operator for this particular graph. The limiting distribution and mixing time of a quantum walk with a coin operator modified as in the abstract search algorithm are obtained numerically. On the basis of these results, the relation between the mixing time of the modified walk and the running time of the corresponding abstract search algorithm is discussed.

Abstract:
We study the behavior of random walk on dynamical percolation. In this model, the edges of a graph G are either open or closed and refresh their status at rate \mu\ while at the same time a random walker moves on G at rate 1 but only along edges which are open. On the d-dimensional torus with side length n, we prove that in the subcritical regime, the mixing times for both the full system and the random walker are n^2/\mu\ up to constants. We also obtain results concerning mean squared displacement and hitting times. Finally, we show that the usual recurrence transience dichotomy for the lattice Z^d holds for this model as well.

Abstract:
We study the mixing time of random graphs in the $d$-dimensional toric unit cube $[0,1]^d$ generated by the geographical threshold graph (GTG) model, a generalization of random geometric graphs (RGG). In a GTG, nodes are distributed in a Euclidean space, and edges are assigned according to a threshold function involving the distance between nodes as well as randomly chosen node weights, drawn from some distribution. The connectivity threshold for GTGs is comparable to that of RGGs, essentially corresponding to a connectivity radius of $r=(\log n/n)^{1/d}$. However, the degree distributions at this threshold are quite different: in an RGG the degrees are essentially uniform, while RGGs have heterogeneous degrees that depend upon the weight distribution. Herein, we study the mixing times of random walks on $d$-dimensional GTGs near the connectivity threshold for $d \geq 2$. If the weight distribution function decays with $\mathbb{P}[W \geq x] = O(1/x^{d+\nu})$ for an arbitrarily small constant $\nu>0$ then the mixing time of GTG is $\mixbound$. This matches the known mixing bounds for the $d$-dimensional RGG.

Abstract:
We examine the vertical mixing induced by the swimming of microorganisms at low Reynolds and P\'eclet numbers in a stably stratified ocean, and show that the global contribution of oceanic microswimmers to vertical mixing is negligible. We propose two approaches to estimating the mixing efficiency, $\eta$, or the ratio of the rate of potential energy creation to the total rate-of-working on the ocean by microswimmers. The first is based on scaling arguments and estimates $\eta$ in terms of the ratio between the typical organism size, $a$, and an intrinsic length scale for the stratified flow, $\ell = \left ( \nu \kappa / N^2 \right )^{1/4}$, where $\nu$ is the kinematic viscosity, $\kappa$ the diffusivity, and $N$ the buoyancy frequency. In particular, for small organisms in the relevant oceanic limit, $a / \ell \ll 1$, we predict the scaling $\eta \sim (a / \ell)^3$. The second estimate of $\eta$ is formed by solving the full coupled flow-stratification problem by modeling the swimmer as a regularized force dipole, and computing the efficiency numerically. Our computational results, which are examined for all ratios $a/\ell$, validate the scaling arguments in the limit $a / \ell \ll 1$ and further predict $\eta \approx 1.2 \left ( a / \ell \right )^3$ for vertical swimming and $\eta \approx 0.15 \left ( a / \ell \right )^3$ for horizontal swimming. These results, relevant for any stratified fluid rich in biological activity, imply that the mixing efficiency of swimming microorganisms in the ocean is at very most 8\% and is likely smaller by at least two orders of magnitude.

Abstract:
We prove a law of large numbers for a class of multidimensional random walks in random environments where the environment satisfies appropriate mixing conditions, which hold when the environment is a weak mixing field in the sense of Dobrushin and Shlosman. Our result holds if the mixing rate balances moments of some random times depending on the path. It applies in the non-nestling case, but we also provide examples of nestling walks that satisfy our assumptions. The derivation is based on an adaptation, using coupling, of the regeneration argument of Sznitman-Zerner.

Abstract:
Shear-induced vertical mixing in a stratified flow is a key ingredient of thermohaline circulation. We experimentally determine the vertical flux of momentum and density of a forced gravity current using high-resolution velocity and density measurements. A constant eddy viscosity model provides a poor description of the physics of mixing, but a Prandtl mixing length model relating momentum and density fluxes to mean velocity and density gradients works well. For $ \approx 0.08$ and $Re_\lambda \approx 100$, the mixing lengths are fairly constant, about the same magnitude, comparable to the turbulent shear length.

Abstract:
Classical random walks on well-behaved graphs are rapidly mixing towards the uniform distribution. Moore and Russell showed that a continuous quantum walk on the hypercube is instantaneously uniform mixing. We show that the continuous-time quantum walks on other well-behaved graphs do not exhibit this uniform mixing. We prove that the only graphs amongst balanced complete multipartite graphs that have the instantaneous uniform mixing property are the complete graphs on two, three and four vertices, and the cycle graph on four vertices. Our proof exploits the circulant structure of these graphs. Furthermore, we conjecture that most complete cycles and Cayley graphs lack this mixing property as well.