First passage on disordered intervals.

We derive unexpected first-passage properties for nearest-neighbor hopping on finite intervals with disordered hopping rates, including (a) a highly variable spatial dependence of the first-passage time, (b) huge disparities in first-passage times for different realizations of hopping rates, (c) significant discrepancies between the first moment and the square root of the second moment of the first-passage time, and (d) bimodal first-passage time distributions. Our approach relies on the backward equation, in conjunction with probability generating functions, to obtain all moments, as well as the distribution of first-passage times. Our approach is simpler than previous approaches based on the forward equation, in which computing the mth moment of the first-passage time requires all preceding moments.

Universal exploration dynamics of random walks.

The territory explored by a random walk is a key property that may be quantified by the number of distinct sites that the random walk visits up to a given time. We introduce a more fundamental quantity, the time τn required by a random walk to find a site that it never visited previously when the walk has already visited n distinct sites, which encompasses the full dynamics about the visitation statistics. To study it, we develop a theoretical approach that relies on a mapping with a trapping problem, in which the spatial distribution of traps is continuously updated by the random walk itself. Despite the geometrical complexity of the territory explored by a random walk, the distribution of the τn can be accounted for by simple analytical expressions. Processes as varied as regular diffusion, anomalous diffusion, and diffusion in disordered media and fractals, fall into the same universality classes.

Complete visitation statistics of one-dimensional random walks.

We develop a framework to determine the complete statistical behavior of a fundamental quantity in the theory of random walks, namely, the probability that n_{1},n_{2},n_{3},... distinct sites are visited at times t_{1},t_{2},t_{3},.... From this multiple-time distribution, we show that the visitation statistics of one-dimensional random walks are temporally correlated, and we quantify the non-Markovian nature of the process. We exploit these ideas to derive unexpected results for the two-time trapping problem and to determine the visitation statistics of two important stochastic processes, the run-and-tumble particle and the biased random walk.

Divergence and consensus in majority rule.

We investigate majority rule dynamics in a population with two classes of people, each with two opinion states ±1, and with tunable interactions between people in different classes. In an update, a randomly selected group adopts the majority opinion if all group members belong to the same class; if not, majority rule is applied with rate ε. Consensus is achieved in a time that scales logarithmically with population size if ε≥ε_{c}=1/9. For ε<ε_{c}, the population can get trapped in a polarized state, with one class preferring the +1 state and the other preferring -1. The time to escape this polarized state and reach consensus scales exponentially with population size.

Optimization in First-Passage Resetting.

We investigate classic diffusion with the added feature that a diffusing particle is reset to its starting point each time the particle reaches a specified threshold. In an infinite domain, this process is nonstationary and its probability distribution exhibits rich features. In a finite domain, we define a nontrivial optimization in which a cost is incurred whenever the particle is reset and a reward is obtained while the particle stays near the reset point. We derive the condition to optimize the net gain in this system, namely, the reward minus the cost.

Nonuniversal opinion dynamics driven by opposing external influences.

We study the opinion dynamics of a generalized voter model in which N voters are additionally influenced by two opposing news sources whose effect is to promote political polarization. As the influence of these news sources is increased, the mean time to reach consensus scales nonuniversally as N^{α}. The parameter α quantifies the influence of the news sources and increases without bound as the news sources become increasingly influential. The time to reach a politically polarized state, in which roughly equal fractions of the populations are in each opinion state, is generally short, and the steady-state opinion distribution exhibits a transition from near consensus to a politically polarized state as a function of α.

Topology-controlled Potts coarsening.

We uncover unusual topological features in the long-time relaxation of the q-state kinetic Potts ferromagnet on the triangular lattice that is instantaneously quenched to zero temperature from a zero-magnetization initial state. For q=3, the final state is either the ground state (frequency ≈0.75), a frozen three-hexagon state (frequency ≈0.16), a two-stripe state (frequency ≈0.09), or a three-stripe state (frequency <2×10^{-4}). Other final state topologies, such as states with more than three hexagons, occur with probability 10^{-5} or smaller, for q=3. The relaxation to the frozen three-hexagon state is governed by a time that scales as L^{2}lnL. We provide a heuristic argument for this anomalous scaling and present additional new features of Potts coarsening on the triangular lattice for q=3 and for q>3.

Exclusion in junction geometries.

We investigate the dynamics of the asymmetric exclusion process at a junction. When two input roads are initially fully occupied and a single output road is initially empty, the ensuing rarefaction wave has a rich spatial structure. The density profile also changes dramatically as the initial densities are varied. Related phenomenology arises when one road feeds into two. Finally, we determine the phase diagram of the open system, where particles are fed into two roads at rate α for each road, the two roads merge into one, and particles are extracted from the single output road at rate ß.

Optimally frugal foraging.

We introduce the frugal foraging model in which a forager performs a discrete-time random walk on a lattice in which each site initially contains S food units. The forager metabolizes one unit of food at each step and starves to death when it last ate S steps in the past. Whenever the forager eats, it consumes all food at its current site and this site remains empty forever (no food replenishment). The crucial property of the forager is that it is frugal and eats only when encountering food within at most k steps of starvation. We compute the average lifetime analytically as a function of the frugality threshold and show that there exists an optimal strategy, namely, an optimal frugality threshold k^{*} that maximizes the forager lifetime.

Trapping and escape in a turbid medium.

We investigate the absorption of diffusing molecules in a fluid-filled spherical beaker that contains many small reactive traps. The molecules are absorbed either by hitting a trap or by escaping via the beaker walls. In the physical situation where the number N of traps is large and their radii a are small compared to the beaker radius R, the fraction of molecules E that escape to the beaker wall and the complementary fraction T that eventually are absorbed by the traps depend only on the dimensionless parameter combination λ = Na/R. We compute E and T as a function of λ for a spherical beaker and for beakers of other three-dimensional shapes. The asymptotic behavior is found to be universal: 1 - E ∼ λ for λ → 0 and E ∼ λ-1/2 for λ → ∞.

Does greed help a forager survive?

We investigate the role of greed on the lifetime of a random-walking forager on an initially resource-rich lattice. Whenever the forager lands on a food-containing site, all the food there is eaten and the forager can hop S more steps without food before starving. Upon reaching an empty site, the forager comes one time unit closer to starvation. The forager is also greedy-given a choice to move to an empty or to a food-containing site in its local neighborhood, the forager moves preferentially toward food. Surprisingly, the forager lifetime varies nonmonotonically with greed, with different senses of the nonmonotonicity in one and two dimensions. Also unexpectedly, the forager lifetime in one dimension has a huge peak for very negative greed where the forager is food averse.

Search in patchy media: Exploitation-exploration tradeoff.

How to best exploit patchy resources? We introduce a minimal exploitation-migration model that incorporates the coupling between a searcher's trajectory, modeled by a random walk, and ensuing depletion of the environment by the searcher's consumption of resources. The searcher also migrates to a new patch when it takes S consecutive steps without finding resources. We compute the distribution of consumed resources F_{t} at time t for this non-Markovian searcher and show that consumption is maximized by exploring multiple patches. In one dimension, we derive the optimal strategy to maximize F_{t}. This strategy is robust with respect to the distribution of resources within patches and the criterion for leaving the current patch. We also show that F_{t} has an optimum in the ecologically relevant case of two-dimensional patchy environments.

Structural Transitions in Densifying Networks.

We introduce a minimal generative model for densifying networks in which a new node attaches to a randomly selected target node and also to each of its neighbors with probability p. The networks that emerge from this copying mechanism are sparse for p<1/2 and dense (average degree increasing with number of nodes N) for p≥1/2. The behavior in the dense regime is especially rich; for example, individual network realizations that are built by copying are disparate and not self-averaging. Further, there is an infinite sequence of structural anomalies at p=2/3, 3/4, 4/5, etc., where the N dependences of the number of triangles (3-cliques), 4-cliques, undergo phase transitions. When linking to second neighbors of the target can occur, the probability that the resulting graph is complete-all nodes are connected-is nonzero as N→∞.

Universality classes of foraging with resource renewal.

We determine the impact of resource renewal on the lifetime of a forager that depletes its environment and starves if it wanders too long without eating. In the framework of a minimal starving random-walk model with resource renewal, there are three universal classes of behavior as a function of the renewal time. For sufficiently rapid renewal, foragers are immortal, while foragers have a finite lifetime otherwise. In the specific case of one dimension, there is a third regime, for sufficiently slow renewal, in which the lifetime of the forager is independent of the renewal time. We outline an enumeration method to determine the mean lifetime of the forager in the mortal regime.

Densification and structural transitions in networks that grow by node copying.

We introduce a growing network model, the copying model, in which a new node attaches to a randomly selected target node and, in addition, independently to each of the neighbors of the target with copying probability p. When p<1/2, this algorithm generates sparse networks, in which the average node degree is finite. A power-law degree distribution also arises, with a nonuniversal exponent whose value is determined by a transcendental equation in p. In the sparse regime, the network is "normal," e.g., the relative fluctuations in the number of links are asymptotically negligible. For p≥1/2, the emergent networks are dense (the average degree increases with the number of nodes N), and they exhibit intriguing structural behaviors. In particular, the N dependence of the number of m cliques (complete subgraphs of m nodes) undergoes m-1 transitions from normal to progressively more anomalous behavior at an m-dependent critical values of p. Different realizations of the network, which start from the same initial state, exhibit macroscopic fluctuations in the thermodynamic limit: absence of self-averaging. When linking to second neighbors of the target node can occur, the number of links asymptotically grows as N^{2} as N→∞, so that the network is effectively complete as N→∞.

Influence of Luddism on innovation diffusion.

We generalize the classical Bass model of innovation diffusion to include a new class of agents-Luddites-that oppose the spread of innovation. Our model also incorporates ignorants, susceptibles, and adopters. When an ignorant and a susceptible meet, the former is converted to a susceptible at a given rate, while a susceptible spontaneously adopts the innovation at a constant rate. In response to the rate of adoption, an ignorant may become a Luddite and permanently reject the innovation. Instead of reaching complete adoption, the final state generally consists of a population of Luddites, ignorants, and adopters. The evolution of this system is investigated analytically and by stochastic simulations. We determine the stationary distribution of adopters, the time needed to reach the final state, and the influence of the network topology on the innovation spread. Our model exhibits an important dichotomy: When the rate of adoption is low, an innovation spreads slowly but widely; in contrast, when the adoption rate is high, the innovation spreads rapidly but the extent of the adoption is severely limited by Luddites.

Safe leads and lead changes in competitive team sports.

We investigate the time evolution of lead changes within individual games of competitive team sports. Exploiting ideas from the theory of random walks, the number of lead changes within a single game follows a Gaussian distribution. We show that the probability that the last lead change and the time of the largest lead size are governed by the same arcsine law, a bimodal distribution that diverges at the start and at the end of the game. We also determine the probability that a given lead is "safe" as a function of its size L and game time t. Our predictions generally agree with comprehensive data on more than 1.25 million scoring events in roughly 40,000 games across four professional or semiprofessional team sports, and are more accurate than popular heuristics currently used in sports analytics.

Mortality, redundancy, and diversity in stochastic search.

We investigate a stochastic search process in one dimension under the competing roles of mortality, redundancy, and diversity of the searchers. This picture represents a toy model for the fertilization of an oocyte by sperm. A population of N independent and mortal diffusing searchers all start at x=L and attempt to reach the target at x=0. When mortality is irrelevant, the search time scales as τ_{D}/lnN for lnN≫1, where τ_{D}~L^{2}/D is the diffusive time scale. Conversely, when the mortality rate µ of the searchers is sufficiently large, the search time scales as sqrt[τ_{D}/µ], independent of N. When searchers have distinct and high mortalities, a subpopulation with a nontrivial optimal diffusivity is most likely to reach the target. We also discuss the effect of chemotaxis on the search time and its fluctuations.

Depletion-controlled starvation of a diffusing forager.

We study the starvation of a lattice random walker in which each site initially contains one food unit and the walker can travel S steps without food before starving. When the walker encounters food, it is completely eaten, and the walker can again travel S steps without food before starving. When the walker hits an empty site, the time until the walker starves decreases by 1. In spatial dimension d=1, the average lifetime of the walker ⟨τ⟩∝S, while for d>2, ⟨τ⟩≃exp(S^{ω}), with ω→1 as d→∞; the latter behavior suggests that the upper critical dimension is infinite. In the marginal case of d=2, ⟨τ⟩∝S^{z}, with z≈2. Long-lived walks explore a highly ramified region so they always remain close to sources of food and the distribution of distinct sites visited does not obey single-parameter scaling.