Source author record

P. L. Krapivsky

P. L. Krapivsky appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

96works

33topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2026arXiv

Impurity dynamics in a zero-temperature gas

If energy is suddenly released in a localized region of space uniformly filled with identical stationary hard spheres, the outcome is a blast with an asymptotically spherical shock wave separating moving and stationary hard spheres. The radius $R(t)$ of the region filled with the moving spheres grows as $t^{2/(d+2)}$, where $d$ is the spatial dimension. The simplest way to inject energy is to kick a few `impurity' particles. Using hydrodynamics and kinetic theory, we argue that the typical displacement of an impurity scales as $R_{\rm imp} \sim λ(R/λ)^{(4+3d^2)/(8+3d^2)}$, where $λ$ is the mean-free path in the initial state. The number of collisions experienced by each impurity grows as $(R/λ)^{(8+2d^2)/(8+3d^2)}$, while its average speed decreases as $t^{-d(8-2d+3d^2)/[(2+d)(8+3d^2)]}$. In $2D$, the predictions for impurity displacement, collision numbers, and speed are $t^{2/5},~t^{2/5}$ and $t^{-2/5}$, respectively. These predictions are in reasonable agreement with the results of molecular dynamics simulations.

preprint2024arXiv

Random sequential covering of a one-dimensional lattice by $k$-mers

In random sequential covering, identical objects are deposited randomly, irreversibly, and sequentially; only attempts that increase coverage are accepted. The process continues indefinitely on an infinite substrate, and we analyze the dynamics of random sequential covering of $\mathbb{Z}$ using $k$-mers. We introduce a method that provides a comprehensive solution to the dynamics of this process. We derive explicit solutions for trimers, tetramers, and pentamers; we study numerically random sequential covering by longer polymers ($k>5$).

preprint2022arXiv

Diffusion in a fluid flow generated by a source at the apex of a wedge

We consider a particle diffusing inside a wedge with absorbing boundaries and driven by a radial flow of incompressible fluid generated by a source at the apex. The survival probability decays as (time)^{-b} with exponent depending on the opening angle of the wedge and the Reynolds number associated with the hydrodynamic flow. The computation of the decay exponent reduces to finding the ground state energy of the quantum particle in an infinitely deep potential well with shape determined by the radial flow velocity.

preprint2021arXiv

Aggregation in non-uniform systems with advection and localized source

We explore analytically and numerically agglomeration driven by advection and localized source. The system is inhomogeneous in one dimension, viz. along the direction of advection. We analyze a simplified model with mass-independent advection velocity, diffusion coefficient, and reaction rates. We also examine a model with mass-dependent coefficients describing aggregation with sedimentation. For the simplified model, we obtain an exact solution for the stationary spatially dependent agglomerate densities. In the model describing aggregation with sedimentation, we report a new conservation law and develop a scaling theory for the densities. For numerical efficiency we exploit the low-rank approximation technique; this dramatically increases the computational speed and allows simulations of large systems. The numerical results are in excellent agreement with the predictions of our theory.

preprint2020arXiv

On multidimensional record patterns

Multidimensional record patterns are random sets of lattice points defined by means of a recursive stochastic construction. The patterns thus generated owe their richness to the fact that the construction is not based on a total order, except in one dimension, where usual records in sequences of independent random variables are recovered. We derive many exact results on the statistics of multidimensional record patterns on finite samples drawn on hypercubic lattices in any dimension $D$. The most detailed analysis concerns the two-dimensional situation, where we also investigate the distribution of the landing position of the record point which is closest to the origin. Asymptotic expressions for the full distribution and the moments of the number of records on large hypercubic samples are also obtained. The latter distribution is related to that of the largest of $D$ standard Gaussian variables.

preprint2020arXiv

Random walk through a fertile site

We study the dynamics of random walks hopping on homogeneous hyper-cubic lattices and multiplying at a fertile site. In one and two dimensions, the total number $\mathcal{N}(t)$ of walkers grows exponentially at a Malthusian rate depending on the dimensionality and the multiplication rate $μ$ at the fertile site. When $d>d_c=2$, the number of walkers may remain finite forever for any $μ$; it surely remains finite when $μ\leq μ_d$. We determine $μ_d$ and show that $\langle\mathcal{N}(t)\rangle$ grows exponentially if $μ>μ_d$. The distribution of the total number of walkers remains broad when $d\leq 2$, and also when $d>2$ and $μ>μ_d$. We compute $\langle \mathcal{N}^m\rangle$ explicitly for small $m$, and show how to determine higher moments. In the critical regime, $\langle \mathcal{N}\rangle$ grows as $\sqrt{t}$ for $d=3$, $t/\ln t$ for $d=4$, and $t$ for $d>4$. Higher moments grow anomalously, $\langle \mathcal{N}^m\rangle\sim \langle \mathcal{N}\rangle^{2m-1}$, in the critical regime; the growth is normal, $\langle \mathcal{N}^m\rangle\sim \langle \mathcal{N}\rangle^{m}$, in the exponential phase. The distribution of the number of walkers in the critical regime is asymptotically stationary and universal, viz. it is independent of the spatial dimension. Interactions between walkers may drastically change the behavior. For random walks with exclusion, if $d>2$, there is again a critical multiplication rate, above which $\langle\mathcal{N}(t)\rangle$ grows linearly (not exponentially) in time; when $d\leq d_c=2$, the leading behavior is independent on $μ$ and $\langle\mathcal{N}(t)\rangle$ exhibits a sub-linear growth.

preprint2020arXiv

Simple Parking Strategies

We investigate simple strategies that embody the decisions that one faces when trying to park near a popular destination. Should one park far from the target (destination), where finding a spot is easy, but then be faced with a long walk, or should one attempt to look for a desirable spot close to the target, where spots may be hard to find? We study an idealized parking process on a one-dimensional geometry where the desired target is located at $x=0$, cars enter the system from the right at a rate $λ$ and each car leaves at a unit rate. We analyze three parking strategies---meek, prudent, and optimistic---and determine which is optimal.

preprint2019arXiv

Free Bosons with a Localized Source

We analyze the time evolution of an open quantum system driven by a localized source of bosons. We consider non-interacting identical bosons that are injected into a single lattice site and and perform a continuous time quantum walks on a lattice. We show that the average number of bosons grows exponentially with time when the input rate exceeds a certain lattice-dependent critical value. Below the threshold, the growth is quadratic in time, which is still much faster than the naive linear in time growth. We compute the critical input rate for hyper-cubic lattices and find that it is positive in all dimensions $d$ except for $d=2$ where the critical input rate vanishes---the growth is always exponential in two dimensions. To understand the exponential growth, we construct an explicit microscopic Hamiltonian model which gives rise to the open system dynamics once the bath is traced out. Exponential growth is identified with a region of dynamic instability of the Hamiltonian system.

preprint2019arXiv

Free Fermions with a Localized Source

We study an open quantum system of free fermions on an infinite lattice coupled to a localized particle source. In the long time limit, the total number of fermions in the system increases linearly with growth rate dependent on the lattice geometry and dimensionality. We express the growth rate in terms of lattice Green functions and derive explicit formulae in one dimension and for the square lattice. The interplay between the dynamics and the coupling to the environment leads, in contrast to classical systems, to a non-monotonic dependence of the particle growth rate on the input rate. We show that for all lattices the particle growth rate is inversely proportional to the input rate when the latter becomes large. This is a manifestation of the quantum Zeno effect.

preprint2016arXiv

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<\frac{1}{2}$, this algorithm generates sparse networks, in which the average node degree is finite. A power-law degree distribution also arises, with a non-universal 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\geq \frac{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 a $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\to\infty$, so that the network is effectively complete as $N\to \infty$.

preprint2016arXiv

Escape and Finite-Size Scaling in Diffusion-Controlled Annihilation

We study diffusion-controlled single-species annihilation with a finite number of particles. In this reaction-diffusion process, each particle undergoes ordinary diffusion, and when two particles meet, they annihilate. We focus on spatial dimensions $d>2$ where a finite number of particles typically survive the annihilation process. Using the rate equation approach and scaling techniques we investigate the average number of surviving particles, $M$, as a function of the initial number of particles, $N$. In three dimensions, for instance, we find the scaling law $M\sim N^{1/3}$ in the asymptotic regime $N\gg 1$. We show that two time scales govern the reaction kinetics: the diffusion time scale, $T\sim N^{2/3}$, and the escape time scale, $τ\sim N^{4/3}$. The vast majority of annihilation events occur on the diffusion time scale, while no annihilation events occur beyond the escape time scale.

preprint2016arXiv

Joint distributions of partial and global maxima of a Brownian Bridge

We analyze the joint distributions and temporal correlations between the partial maximum $m$ and the global maximum $M$ achieved by a Brownian Bridge on the subinterval $[0,t_1]$ and on the entire interval $[0,t]$, respectively. We determine three probability distribution functions: The joint distribution $P(m,M)$ of both maxima; the distribution $P(m)$ of the partial maximum; and the distribution $Π(G)$ of the gap between the maxima, $G = M-m$. We present exact results for the moments of these distributions and quantify the temporal correlations between $m$ and $M$ by calculating the Pearson correlation coefficient.

preprint2016arXiv

Kinetics of Aggregation with Choice

We generalize the ordinary aggregation process to allow for choice. In ordinary aggregation, two random clusters merge and form a larger aggregate. In our implementation of choice, a target cluster and two candidate clusters are randomly selected, and the target cluster merges with the larger of the two candidate clusters. We study the long-time asymptotic behavior, and find that as in ordinary aggregation, the size density adheres to the standard scaling form. However, aggregation with choice exhibits a number of novel features. First, the density of the smallest clusters exhibits anomalous scaling. Second, both the small-size and the large-size tails of the density are overpopulated, at the expense of the density moderate-size clusters. We also study the complementary case where the smaller candidate clusters participates in the aggregation process, and find abundance of moderate clusters at the expense of small and large clusters. Additionally, we investigate aggregation processes with choice among multiple candidate clusters, and a symmetric implementation where the choice is between two pairs of clusters.

preprint2016arXiv

Kinetics of Diffusion-Controlled Annihilation with Sparse Initial Conditions

We study diffusion-controlled single-species annihilation with sparse initial conditions. In this random process, particles undergo Brownian motion, and when two particles meet, both disappear. We focus on sparse initial conditions where particles occupy a subspace of dimension $δ$ that is embedded in a larger space of dimension $d$. We find that the co-dimension $Δ=d-δ$ governs the behavior. All particles disappear when the co-dimension is sufficiently small, $Δ\leq 2$; otherwise, a finite fraction of particles indefinitely survive. We establish the asymptotic behavior of the probability $S(t)$ that a test particle survives until time $t$. When the subspace is a line, $δ=1$, we find inverse logarithmic decay, $S\sim (\ln t)^{-1}$, in three dimensions, and a modified power-law decay, $S\sim (\ln t)\,t^{-1/2}$, in two dimensions. In general, the survival probability decays algebraically when $Δ<2$, and there is an inverse logarithmic decay at the critical co-dimension $Δ=2$.

preprint2016arXiv

Maxima of Two Random Walks: Universal Statistics of Lead Changes

We investigate statistics of lead changes of the maxima of two discrete-time random walks in one dimension. We show that the average number of lead changes grows as $π^{-1}\ln(t)$ in the long-time limit. We present theoretical and numerical evidence that this asymptotic behavior is universal. Specifically, this behavior is independent of the jump distribution: the same asymptotic underlies standard Brownian motion and symmetric Levy flights. We also show that the probability to have at most n lead changes behaves as $t^{-1/4}[\ln t]^n$ for Brownian motion and as $t^{-β(μ)}[\ln t]^n$ for symmetric Levy flights with index $μ$. The decay exponent $β(μ)$ varies continuously with the Levy index when $0<μ<2$, while $β=1/4$ for $μ>2$.

preprint2016arXiv

Quantum centipedes: collective dynamics of interacting quantum walkers

We consider the quantum centipede made of $N$ fermionic quantum walkers on the one-dimensional lattice interacting by means of the simplest of all hard-bound constraints: the distance between two consecutive fermions is either one or two lattice spacings. This composite quantum walker spreads ballistically, just as the simple quantum walk. However, because of the interactions between the internal degrees of freedom, the distribution of its center-of-mass velocity displays numerous ballistic fronts in the long-time limit, corresponding to singularities in the empirical velocity distribution. The spectrum of the centipede and the corresponding group velocities are analyzed by direct means for the first few values of $N$. Some analytical results are obtained for arbitrary $N$ by exploiting an exact mapping of the problem onto a free-fermion system. We thus derive the maximal velocity describing the ballistic spreading of the two extremal fronts of the centipede wavefunction, including its non-trivial value in the large-$N$ limit.

preprint2016arXiv

Reply to "Comment on Generalized Exclusion Processes: Transport Coefficients"

We reply to the comment of Becker, Nelissen, Cleuren, Partoens, and Van den Broeck, Phys. Rev. E 93, 046101 (2016) on our article, Phys. Rev. E 90, 052108 (2014) about transport properties of a class of generalized exclusion processes.

preprint2016arXiv

Structural Transitions in Dense Networks

We introduce an evolving network model in which a new node attaches to a randomly selected target node and also to each of its neighbors with probability $p$. The resulting network is sparse for $p<\frac{1}{2}$ and dense (average degree increasing with number of nodes $N$) for $p\geq \frac{1}{2}$. In the dense regime, individual networks realizations built by this copying mechanism are disparate and not self-averaging. Further, there is an infinite sequence of structural anomalies at $p=\frac{2}{3}$, $\frac{3}{4}$, $\frac{4}{5}$, etc., where the dependences on $N$ 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---where all nodes are connected---is non-zero as $N\to\infty$.

preprint2016arXiv

Temporal correlations of the running maximum of a Brownian trajectory

We study the correlations between the maxima $m$ and $M$ of a Brownian motion (BM) on the time intervals $[0,t_1]$ and $[0,t_2]$, with $t_2>t_1$. We determine exact forms of the distribution functions $P(m,M)$ and $P(G = M - m)$, and calculate the moments $\mathbb{E}\{\left(M - m\right)^k\}$ and the cross-moments $\mathbb{E}\{m^l M^k\}$ with arbitrary integers $l$ and $k$. We show that correlations between $m$ and $M$ decay as $\sqrt{t_1/t_2}$ when $t_2/t_1 \to \infty$, revealing strong memory effects in the statistics of the BM maxima. We also compute the Pearson correlation coefficient $ρ(m,M)$, the power spectrum of $M_t$, and we discuss a possibility of extracting the ensemble-averaged diffusion coefficient in single-trajectory experiments using a single realization of the maximum process.

preprint2015arXiv

Aggregation Driven by a Localized Source

We study aggregation driven by a localized source of monomers. The densities become stationary and have algebraic tails far away from the source. We show that in a model with mass-independent reaction rates and diffusion coefficients, the density of monomers decays as $r^{-β(d)}$ in $d$ dimensions. The decay exponent has irrational values in physically relevant dimensions: $β(3)=(\sqrt{17}+1)/2$ and $β(2)=\sqrt{8}$. We also study Brownian coagulation with a localized source and establish the behavior of the total cluster density and the total number of of clusters in the system. The latter quantity exhibits a logarithmic growth with time.

preprint2015arXiv

Analytical results for the distribution of shortest path lengths in random networks

We present two complementary analytical approaches for calculating the distribution of shortest path lengths in Erdos-Rényi networks, based on recursion equations for the shells around a reference node and for the paths originating from it. The results are in agreement with numerical simulations for a broad range of network sizes and connectivities. The average and standard deviation of the distribution are also obtained. In the case that the mean degree scales as $N^α$ with the network size, the distribution becomes extremely narrow in the asymptotic limit, namely almost all pairs of nodes are equidistant, at distance $d=\lfloor 1/α\rfloor$ from each other. The distribution of shortest path lengths between nodes of degree $m$ and the rest of the network is calculated. Its average is shown to be a monotonically decreasing function of $m$, providing an interesting relation between a local property and a global property of the network. The methodology presented here can be applied to more general classes of networks.

preprint2015arXiv

Dynamical properties of single-file diffusion

We study the statistics of a tagged particle in single-file diffusion, a one-dimensional interacting infinite-particle system in which the order of particles never changes. We compute the two-time correlation function for the displacement of the tagged particle for an arbitrary single-file system. We also discuss single-file analogs of the arcsine law and the law of the iterated logarithm characterizing the behavior of Brownian motion. Using a macroscopic fluctuation theory we devise a formalism giving the cumulant generating functional. In principle, this functional contains the full statistics of the tagged particle trajectory---the full single-time statistics, all multiple-time correlation functions, etc. are merely special cases.

preprint2015arXiv

Interacting quantum walkers: Two-body bosonic and fermionic bound states

We investigate the dynamics of bound states of two interacting particles, either bosons or fermions, performing a continuous-time quantum walk on a one-dimensional lattice. We consider the situation where the distance between both particles has a hard bound, and the richer situation where the particles are bound by a smooth confining potential. The main emphasis is on the velocity characterizing the ballistic spreading of these bound states, and on the structure of the asymptotic distribution profile of their center-of-mass coordinate. The latter profile generically exhibits many internal fronts.

preprint2015arXiv

Irreversible Reactions and Diffusive Escape: Stationary Properties

We study three basic diffusion-controlled reaction processes -- annihilation, coalescence, and aggregation. We examine the evolution starting with the most natural inhomogeneous initial configuration where a half-line is uniformly filled by particles, while the complementary half-line is empty. We show that the total number of particles that infiltrate the initially empty half-line is finite and has a stationary distribution. We determine the evolution of the average density from which we derive the average total number N of particles in the initially empty half-line; e.g., for annihilation \langle N\rangle = 3/16+1/(4π). For the coalescence process, we devise a procedure that in principle allows one to compute P(N), the probability to find exactly N particles in the initially empty half-line; we complete the calculations in the first non-trivial case (N=1). As a by-product we derive the distance distribution between the two leading particles.

preprint2015arXiv

Mass Exchange Processes with Input

We investigate a system of interacting clusters evolving through mass exchange and supplemented by input of small clusters. Three possibilities depending on the rate of exchange generically occur when input is homogeneous: continuous growth, gelation, and instantaneous gelation. We mostly study the growth regime using scaling methods. An exchange process with reaction rates equal to the product of reactant masses admits an exact solution which allows us to justify the validity of scaling approaches in this special case. We also investigate exchange processes with a localized input. We show that if the diffusion coefficients are mass-independent, the cluster mass distribution becomes stationary and develops an algebraic tail far away from the source.

preprint2015arXiv

Native ultrametricity of sparse random ensembles

We investigate the eigenvalue density in ensembles of large sparse Bernoulli random matrices. We demonstrate that the fraction of linear subgraphs just below the percolation threshold is about 95\% of all finite subgraphs, and the distribution of linear chains is purely exponential. We analyze in detail the spectral density of ensembles of linear subgraphs, discuss its ultrametric nature and show that near the spectrum boundary, the tail of the spectral density exhibits a Lifshitz singularity typical for Anderson localization. We also discuss an intriguing connection of the spectral density to the Dedekind $η$-function. We conjecture that ultrametricity is inherit to complex systems with extremal sparse statistics and argue that a number-theoretic ultrametricity emerges in any rare-event statistics.

preprint2015arXiv

Scaling Exponents for Ordered Maxima

We study extreme value statistics of multiple sequences of random variables. For each sequence with N variables, independently drawn from the same distribution, the running maximum is defined as the largest variable to date. We compare the running maxima of m independent sequences, and investigate the probability S_N that the maxima are perfectly ordered, that is, the running maximum of the first sequence is always larger than that of the second sequence, which is always larger than the running maximum of the third sequence, and so on. The probability S_N is universal: it does not depend on the distribution from which the random variables are drawn. For two sequences, S_N ~ N^(-1/2), and in general, the decay is algebraic, S_N ~ N^(-σ_m), for large N. We analytically obtain the exponent sigma_3= 1.302931 as root of a transcendental equation. Furthermore, the exponents sigma_m grow with m, and we show that sigma_m ~ m for large m.

preprint2014arXiv

Choice-Driven Phase Transition in Complex Networks

We investigate choice-driven network growth. In this model, nodes are added one by one according to the following procedure: for each addition event a set of target nodes is selected, each according to linear preferential attachment, and a new node attaches to the target with the highest degree. Depending on precise details of the attachment rule, the resulting networks has three possible outcomes: (i) a non-universal power-law degree distribution; (ii) a single macroscopic hub (a node whose degree is of the order of N, the number of network nodes), while the remainder of the nodes comprises a non-universal power-law degree distribution; (iii) a degree distribution that decays as (k ln k)^{-2} at the transition between cases (i) and (ii). These properties are robust when attachment occurs to the highest-degree node from at least two targets. When attachment is made to a target whose degree is not the highest, the degree distribution has the ultra-narrow double-exponential form exp(-const. x e^k), from which the largest degree grows only as ln(ln N).

preprint2014arXiv

Emergence of Clustering in an Acquaintance Model without Homophily

We introduce an agent-based acquaintance model in which social links are created by processes in which there is no explicit homophily. In spite of the homogeneous nature of the social interactions, highly-clustered social networks can arise. The crucial feature of our model is that of variable transitive interactions. Namely, when an agent introduces two unconnected friends, the rate at which a connection actually occurs between them depends on the number of their mutual acquaintances. As this transitive interaction rate is varied, the social network undergoes a dramatic clustering transition. Close to the transition, the network consists of a collection of well-defined communities. As a function of time, the network can also undergo an \emph{incomplete} gelation transition, in which the gel, or giant cluster, does not constitute the entire network, even at infinite time. Some of the clustering properties of our model also arise, but in a more gradual manner, in Facebook networks. Finally, we discuss a more realistic variant of our original model in which there is a soft cutoff in the rate of transitive interactions. With this variant, one can construct network realizations that quantitatively match Facebook networks.

preprint2014arXiv

Exclusion Processes with Avalanches

In an exclusion process with avalanches, when a particle hops to a neighboring empty site which is adjacent to an island the particle on the other end of the island immediately hops and if it joins another island this triggers another hop. There are no restrictions on the length of islands and the duration of the avalanche. This process is well-defined in the low-density region, ρ<1/2. We describe the nature of steady states (on a ring) and determine all correlation functions. For the asymmetric version of the process, we compute the steady state current, and we describe shock and rarefaction waves which arise in the evolution of the step-function initial profile. For the symmetric version, we determine the diffusion coefficient and examine the evolution of a tagged particle.

preprint2014arXiv

Generalized Exclusion Processes: Transport Coefficients

A class of generalized exclusion processes parametrized by the maximal occupancy, $k\geq 1$, is investigated. For these processes with symmetric nearest-neighbor hopping, we compute the diffusion coefficient and show that it is independent on the spatial dimension. In the extreme cases of $k=1$ (simple symmetric exclusion process) and $k=\infty$ (non-interacting symmetric random walks) the diffusion coefficient is constant; for $2\leq k<\infty$, the diffusion coefficient depends on the density and the maximal occupancy $k$. We also study the evolution of a tagged particle. It exhibits a diffusive behavior which is characterized by the coefficient of self-diffusion which we probe numerically.

preprint2014arXiv

Highly Dispersed Networks Generated by Enhanced Redirection

We analyze growing networks that are built by enhanced redirection. Nodes are sequentially added and each incoming node attaches to a randomly chosen 'target' node with probability 1-r, or to the parent of the target node with probability r. When the redirection probability r is an increasing function of the degree of the parent node, with r-->1 as the parent degree diverges, networks grown via this enhanced redirection mechanism exhibit unusual properties, including: (i) multiple macrohubs---nodes with degrees proportional to the number of network nodes N; (ii) non-extensivity of the degree distribution in which the number of nodes of degree k, N_k, scales as N^{nu-1}/k^{nu}, with 1<nu<2; (iii) lack of self-averaging, with large fluctuations between individual network realizations. These features are robust and continue to hold when the incoming node has out-degree greater than 1 so that networks contain closed loops. The latter networks are strongly clustered; for the specific case of the double attachment, the average local clustering coefficient is <C_i>=4(ln2)-2=0.77258...

preprint2014arXiv

Large Deviations in Single File Diffusion

We apply macroscopic fluctuation theory to study the diffusion of a tracer in a one-dimensional interacting particle system with excluded mutual passage, known as single-file diffusion. In the case of Brownian point particles with hard-core repulsion, we derive the cumulant generating function of the tracer position and its large deviation function. In the general case of arbitrary inter-particle interactions, we express the variance of the tracer position in terms of the collective transport properties, viz. the diffusion coefficient and the mobility. Our analysis applies both for fluctuating (annealed) and fixed (quenched) initial configurations.

preprint2014arXiv

Lattice gases with a point source

We study diffusive lattice gases with local injection of particles, namely we assume that whenever the origin becomes empty, a new particle is immediately injected into the origin. We consider two lattice gases: a symmetric simple exclusion process and random walkers. The interplay between the injection events and the positions of the particles already present implies an effective collective interaction even for the ostensibly non-interacting random walkers. We determine the average total number of particles entering into the initially empty system. We also compute the average total number of distinct sites visited by all particles, and discuss the shape of the visited domain and the statistics of visits.

preprint2014arXiv

Melting of an Ising Quadrant

We consider an Ising ferromagnet endowed with zero-temperature spin-flip dynamics and examine the evolution of the Ising quadrant, namely the spin configuration when the minority phase initially occupies a quadrant while the majority phase occupies three remaining quadrants. The two phases are then always separated by a single interface which generically recedes into the minority phase in a self-similar diffusive manner. The area of the invaded region grows (on average) linearly with time and exhibits non-trivial fluctuations. We map the interface separating the two phases onto the one-dimensional symmetric simple exclusion process and utilize this isomorphism to compute basic cumulants of the area. First, we determine the variance via an exact microscopic analysis (the Bethe ansatz). Then we turn to a continuum treatment by recasting the underlying exclusion process into the framework of the macroscopic fluctuation theory. This provides a systematic way of analyzing the statistics of the invaded area and allows us to determine the asymptotic behaviors of the first four cumulants of the area.

preprint2014arXiv

Persistence of Random Walk Records

We study records generated by Brownian particles in one dimension. Specifically, we investigate an ordinary random walk and define the record as the maximal position of the walk. We compare the record of an individual random walk with the mean record, obtained as an average over infinitely many realizations. We term the walk "superior" if the record is always above average, and conversely, the walk is said to be "inferior" if the record is always below average. We find that the fraction of superior walks, S, decays algebraically with time, S ~ t^(-beta), in the limit t --> infty, and that the persistence exponent is nontrivial, beta=0.382258.... The fraction of inferior walks, I, also decays as a power law, I ~ t^(-alpha), but the persistence exponent is smaller, alpha=0.241608.... Both exponents are roots of transcendental equations involving the parabolic cylinder function. To obtain these theoretical results, we analyze the joint density of superior walks with given record and position, while for inferior walks it suffices to study the density as function of position.

preprint2014arXiv

Slow Kinetics of Brownian Maxima

We study extreme-value statistics of Brownian trajectories in one dimension. We define the maximum as the largest position to date and compare maxima of two particles undergoing independent Brownian motion. We focus on the probability P(t) that the two maxima remain ordered up to time t, and find the algebraic decay P ~ t^(-beta) with exponent beta=1/4. When the two particles have diffusion constants D1 and D2, the exponent depends on the mobilities, beta=(1/pi)arctan[sqrt(D2/D1)]. We also use numerical simulations to investigate maxima of multiple particles in one dimension and the largest extension of particles in higher dimensions.

preprint2014arXiv

Survival of a static target in a gas of diffusing particles with exclusion

Let a lattice gas of constant density, described by the symmetric simple exclusion process, be brought in contact with a "target": a spherical absorber of radius $R$. Employing the macroscopic fluctuation theory (MFT), we evaluate the probability ${\mathcal P}(T)$ that no gas particle hits the target until a long but finite time $T$. We also find the most likely gas density history conditional on the non-hitting. The results depend on the dimension of space $d$ and on the rescaled parameter $\ell=R/\sqrt{D_0T}$, where $D_0$ is the gas diffusivity. For small $\ell$ and $d>2$, ${\mathcal P}(T)$ is determined by an exact stationary solution of the MFT equations that we find. For large $\ell$, and for any $\ell$ in one dimension, the relevant MFT solutions are non-stationary. In this case $\ln {\mathcal P}(T)$ scales differently with relevant parameters, and it also depends on whether the initial condition is random or deterministic. The latter effects also occur if the lattice gas is composed of non-interacting random walkers. Finally, we extend the formalism to a whole class of diffusive gases of interacting particles.

preprint2014arXiv

Survival of classical and quantum particles in the presence of traps

We present a detailed comparison of the motion of a classical and of a quantum particle in the presence of trapping sites, within the framework of continuous-time classical and quantum random walk. The main emphasis is on the qualitative differences in the temporal behavior of the survival probabilities of both kinds of particles. As a general rule, static traps are far less efficient to absorb quantum particles than classical ones. Several lattice geometries are successively considered: an infinite chain with a single trap, a finite ring with a single trap, a finite ring with several traps, and an infinite chain and a higher-dimensional lattice with a random distribution of traps with a given density. For the latter disordered systems, the classical and the quantum survival probabilities obey a stretched exponential asymptotic decay, albeit with different exponents. These results confirm earlier predictions, and the corresponding amplitudes are evaluated. In the one-dimensional geometry of the infinite chain, we obtain a full analytical prediction for the amplitude of the quantum problem, including its dependence on the trap density and strength.

preprint2013arXiv

Asymmetric Exclusion Process with Global Hopping

We study a one-dimensional totally asymmetric simple exclusion process with one special site from which particles fly to any empty site (not just to the neighboring site). The system attains a non-trivial stationary state with density profile varying over the spatial extent of the system. The density profile undergoes a non-equilibrium phase transition when the average density passes through the critical value 1-1/[4(1-ln 2)]=0.185277..., viz. in addition to the discontinuity in the vicinity of the special site, a shock wave is formed in the bulk of the system when the density exceeds the critical density.

preprint2013arXiv

Crystal Growth Inside an Octant

We study crystal growth inside an infinite octant on a cubic lattice. The growth proceeds through the deposition of elementary cubes into inner corners. After re-scaling by the characteristic size, the interface becomes progressively more deterministic in the long-time limit. Utilizing known results for the crystal growth inside a two-dimensional corner, we propose a hyperbolic partial differential equation for the evolution of the limiting shape. This equation is interpreted as a Hamilton-Jacobi equation which helps in finding an analytical solution. Simulations of the growth process are in excellent agreement with analytical predictions. We then study the evolution of the sub-leading correction to the volume of the crystal, the asymptotic growth of the variance of the volume of the crystal, and the total number of inner and outer corners. We also show how to generalize the results to arbitrary spatial dimension.

preprint2013arXiv

Distinct Degrees and Their Distribution in Complex Networks

We investigate a variety of statistical properties associated with the number of distinct degrees that exist in a typical network for various classes of networks. For a single realization of a network with N nodes that is drawn from an ensemble in which the number of nodes of degree k has an algebraic tail, N_k ~ N/k^nu for k>>1, the number of distinct degrees grows as N^{1/nu}. Such an algebraic growth is also observed in scientific citation data. We also determine the N dependence of statistical quantities associated with the sparse, large-k range of the degree distribution, such as the location of the first hole (where N_k=0), the last doublet (two consecutive occupied degrees), triplet, dimer (N_k=2), trimer, etc.

preprint2013arXiv

Dynamics of Repulsion Processes

We study dynamical behaviors of one-dimensional stochastic lattice gases with repulsive interactions whose span can be arbitrary large. We endow the system with a zero-temperature dynamics, so that the hops to empty sites which would have led to the increase of energy are forbidden. We assume that the strength of interactions sufficiently quickly decreases with the separation between the particles, so that interactions can be treated in a lexicographic order. For such repulsion processes with symmetric nearest-neighbor hopping we analytically determine the density-dependent diffusion coefficient. We also compute the variance of the displacement of a tagged particle.

preprint2013arXiv

Fate of 2D Kinetic Ising Ferromagnets and Critical Percolation Crossing Probabilities

We present evidence for a deep connection between the zero-temperature coarsening of the two-dimensional kinetic Ising model (KIM) and critical continuum percolation. In addition to reaching the ground state, the KIM can also fall into a variety of topologically distinct metastable stripe states. The probability to reach a stripe state that winds a times horizontally and b times vertically on a square lattice with periodic boundary conditions equals the corresponding exactly-solved critical percolation crossing probability P_{a,b} for a spanning path with winding numbers a and b.

preprint2013arXiv

First Passage in Conical Geometry and Ordering of Brownian Particles

We survey recent results on first-passage processes in unbounded cones and their applications to ordering of particles undergoing Brownian motion in one dimension. We first discuss the survival probability S(t) that a diffusing particle, in arbitrary spatial dimension, remains inside a conical domain up to time t. In general, this quantity decays algebraically S ~ t^{-beta} in the long-time limit. The exponent beta depends on the opening angle of the cone and the spatial dimension, and it is root of a transcendental equation involving the associated Legendre functions. The exponent becomes a function of a single scaling variable in the limit of large spatial dimension. We then describe two first-passage problems involving the order of N independent Brownian particles in one dimension where survival probabilities decay algebraically as well. To analyze these problems, we identify the trajectories of the N particles with the trajectory of one particle in N dimensions, confined to within a certain boundary, and we use a circular cone with matching solid angle as a replacement for the confining boundary. For N=3, the confining boundary is a wedge and the approach is exact. In general, this "cone approximation" gives strict lower bounds as well as useful estimates or the first-passage exponents. Interestingly, the cone approximation becomes asymptotically exact when N-->infinity as it predicts the exact scaling function that governs the spectrum of first-passage exponents.

preprint2013arXiv

Highly Dispersed Networks

We introduce a new class of networks that grow by enhanced redirection. Nodes are introduced sequentially, and each either attaches to a randomly chosen target node with probability 1-r or to the ancestor of the target with probability r, where r an increasing function of the degree of the ancestor. This mechanism leads to highly-dispersed networks with unusual properties: (i) existence of multiple macrohubs---nodes whose degree is a finite fraction of the total number of network nodes N, (ii) lack of self averaging, and (iii) anomalous scaling, in which N_k, the number of nodes of degree k scales as N_k N^{nu-1}/k^{nu}, with 1<nu<2.

preprint2013arXiv

Limiting Shapes in Two-Dimensional Ising Ferromagnets

We consider an Ising model on a square grid with ferromagnetic spin-spin interactions spanning beyond nearest neighbors. Starting from initial states with a single unbounded interface separating ordered phases, we investigate the evolution of the interface subject to zero-temperature spin-flip dynamics. We consider an interface which is initially (i) the boundary of the quadrant, or (ii) the boundary of a semi-infinite stripe. In the former case the interface recedes from its original location in a self-similar diffusive manner. After a re-scaling by t^{1/2}, the shape of the interface becomes more and more deterministic; we determine this limiting shape analytically and verify our predictions numerically. The semi-infinite stripe acquires a stationary shape resembling a finger, and this finger translates along its axis. We compute the limiting shape and the velocity of the Ising finger.

preprint2013arXiv

Spatial evolution of tumors with successive driver mutations

We study the spatial evolutionary dynamics of solid tumors as they obtain additional driver mutations. We start with a cancer clone that expands uniformly in three dimensions giving rise to a spherical shape. We assume that cell division occurs on the surface of the growing tumor. Each cell division has a chance to give rise to a mutation that activates an additional driver gene. The resulting clone has an enhanced growth rate, which generates a local ensemble of faster growing cells, thereby distorting the spherical shape of the tumor. We derive analytic formulas for the geometric boundary that separates the original cancer clone from the new mutant as well as the expanding frontier of the new mutant. The total number of original cancer cells converges to a constant as time goes to infinity, because this clone becomes enveloped by mutants. We derive formulas for the abundance and diversity of additional driver mutations as function of time. Our model is semi-deterministic: the spatial growth of the various cancer clones follows deterministic equations, but the arrival of a new mutant is a stochastic event.

preprint2013arXiv

Statistics of Superior Records

We study statistics of records in a sequence of random variables. These identical and independently distributed variables are drawn from the parent distribution rho. The running record equals the maximum of all elements in the sequence up to a given point. We define a superior sequence as one where all running records are above the average record, expected for the parent distribution rho. We find that the fraction of superior sequences S_N decays algebraically with sequence length N, S_N ~ N^{-beta} in the limit N-->infty. Interestingly, the decay exponent beta is nontrivial, being the root of an integral equation. For example, when rho is a uniform distribution with compact support, we find beta=0.450265. In general, the tail of the parent distribution governs the exponent beta. We also consider the dual problem of inferior sequences, where all records are below average, and find that the fraction of inferior sequences I_N decays algebraically, albeit with a different decay exponent, I_N ~ N^{-alpha}. We use the above statistical measures to analyze earthquake data.

preprint2013arXiv

Zero-Temperature Coarsening in the 2d Potts Model

We study the fate of the 2d kinetic q-state Potts model after a sudden quench to zero temperature. Both ground states and complicated static states are reached with non-zero probabilities. These outcomes resemble those found in the quench of the 2d Ising model; however, the variety of static states in the q-state Potts model (with q>=3) is much richer than in the Ising model, where static states are either ground or stripe states. Another possibility is that the system gets trapped on a set of equal-energy blinker states where a subset of spins can flip ad infinitum; these states are similar to those found in the quench of the 3d Ising model. The evolution towards the final energy is also unusual---at long times, sudden and massive energy drops may occur that are accompanied by macroscopic reordering of the domain structure. This indeterminacy in the zero-temperature quench of the kinetic Potts model is at odds with basic predictions from the theory of phase-ordering kinetics. We also propose a continuum description of coarsening with more than two equivalent ground states. The resulting time-dependent Ginzburg-Landau equations reproduce the complex cluster patterns that arise in the quench of the kinetic Potts model.

P. L. Krapivsky

What is connected

Connect this record

See the researcher in context

Building this map preview

96 published item(s)

Impurity dynamics in a zero-temperature gas

Random sequential covering of a one-dimensional lattice by $k$-mers

Diffusion in a fluid flow generated by a source at the apex of a wedge

Aggregation in non-uniform systems with advection and localized source

On multidimensional record patterns

Random walk through a fertile site

Simple Parking Strategies

Free Bosons with a Localized Source

Free Fermions with a Localized Source

Densification and Structural Transitions in Networks that Grow by Node Copying

Escape and Finite-Size Scaling in Diffusion-Controlled Annihilation

Joint distributions of partial and global maxima of a Brownian Bridge

Kinetics of Aggregation with Choice

Kinetics of Diffusion-Controlled Annihilation with Sparse Initial Conditions

Maxima of Two Random Walks: Universal Statistics of Lead Changes

Quantum centipedes: collective dynamics of interacting quantum walkers

Reply to "Comment on Generalized Exclusion Processes: Transport Coefficients"

Structural Transitions in Dense Networks

Temporal correlations of the running maximum of a Brownian trajectory

Aggregation Driven by a Localized Source

Analytical results for the distribution of shortest path lengths in random networks

Dynamical properties of single-file diffusion

Interacting quantum walkers: Two-body bosonic and fermionic bound states

Irreversible Reactions and Diffusive Escape: Stationary Properties

Mass Exchange Processes with Input

Native ultrametricity of sparse random ensembles

Scaling Exponents for Ordered Maxima

Choice-Driven Phase Transition in Complex Networks

Emergence of Clustering in an Acquaintance Model without Homophily

Exclusion Processes with Avalanches

Generalized Exclusion Processes: Transport Coefficients

Highly Dispersed Networks Generated by Enhanced Redirection

Large Deviations in Single File Diffusion

Lattice gases with a point source

Melting of an Ising Quadrant

Persistence of Random Walk Records

Slow Kinetics of Brownian Maxima

Survival of a static target in a gas of diffusing particles with exclusion

Survival of classical and quantum particles in the presence of traps

Asymmetric Exclusion Process with Global Hopping

Crystal Growth Inside an Octant

Distinct Degrees and Their Distribution in Complex Networks

Dynamics of Repulsion Processes

Fate of 2D Kinetic Ising Ferromagnets and Critical Percolation Crossing Probabilities

First Passage in Conical Geometry and Ordering of Brownian Particles

Highly Dispersed Networks

Limiting Shapes in Two-Dimensional Ising Ferromagnets

Spatial evolution of tumors with successive driver mutations

Statistics of Superior Records

Zero-Temperature Coarsening in the 2d Potts Model

Compact Waves in Microscopic Nonlinear Diffusion

Continuum Cascade Model of Directed Random Graphs: Traveling Wave Analysis

Discrete Analog of the Burgers Equation

Driven Brownian coagulation of polymers

Fluctuations of Current in Non-Stationary Diffusive Lattice Gases

Growth Inside a Corner: The Limiting Interface Shape

Limiting Shapes of Ising Droplets, Ising Fingers, and Ising Solitons

Molecular Spiders on the Plane

Outbreak size distributions in epidemics with multiple stages

Reaction-Diffusion Process Driven by a Localized Source: First Passage Properties

Reaction-Diffusion Processes with Nonlinear Diffusion

Reply to Comment on "Growth Inside a Corner: The Limiting Interface Shape"

Scaling Behavior of Threshold Epidemics

Symmetric Exclusion Process with a Localized Source

Void formation in diffusive lattice gases

Dynamics of a quantum particle in low-dimensional disordered systems with extended states

Dynamics of Random Graphs with Bounded Degrees

Exact solution of a two-type branching process: Models of tumor progression

Freezing into Stripe States in Two-Dimensional Ferromagnets and Crossing Probabilities in Critical Percolation

Kinetics of Ring Formation

Lorentz Gas at a Positive Temperature

On stochastic differential equations with random delay

Popularity-Driven Networking

Reinforcement-Driven Spread of Innovations and Fads