Search

We introduce the profligacy of a search process as a competition between its expected cost and the probability of finding the target. The arbiter of the competition is a parameter $\lambda$ that represents how much a searcher invests into increasing the chance of success. Minimizing the profligacy with respect to the search strategy specifies the optimal search. We show that in the case of diffusion with stochastic resetting, the amount of resetting in the optimal strategy has a highly nontrivial dependence on model parameters resulting in classical continuous transitions, discontinuous transitions and tricritical points as well as non-standard discontinuous transitions exhibiting re-entrant behavior and overhangs., Comment: 12 pages, 8 figures

Neural Cellular Automata (NCA) are a powerful combination of machine learning and mechanistic modelling. We train NCA to learn complex dynamics from time series of images and PDE trajectories. Our method is designed to identify underlying local rules that govern large scale dynamic emergent behaviours. Previous work on NCA focuses on learning rules that give stationary emergent structures. We extend NCA to capture both transient and stable structures within the same system, as well as learning rules that capture the dynamics of Turing pattern formation in nonlinear Partial Differential Equations (PDEs). We demonstrate that NCA can generalise very well beyond their PDE training data, we show how to constrain NCA to respect given symmetries, and we explore the effects of associated hyperparameters on model performance and stability. Being able to learn arbitrary dynamics gives NCA great potential as a data driven modelling framework, especially for modelling biological pattern formation., Comment: For videos referenced in appendix, see: https://github.com/AlexDR1998/NCA/tree/main/Videos

Language change is a cultural evolutionary process in which variants of linguistic variables change in frequency through processes analogous to mutation, selection and genetic drift. In this work, we apply a recently-introduced method to corpus data to quantify the strength of selection in specific instances of historical language change. We first demonstrate, in the context of English irregular verbs, that this method is more reliable and interpretable than similar methods that have previously been applied. We further extend this study to demonstrate that a bias towards phonological simplicity overrides that favouring grammatical simplicity when these are in conflict. Finally, with reference to Spanish spelling reforms, we show that the method can also detect points in time at which selection strengths change, a feature that is generically expected for socially-motivated language change. Together, these results indicate how hypotheses for mechanisms of language change can be tested quantitatively using historical corpus data.

Resetting a stochastic process has been shown to expedite the completion time of some complex tasks, such as finding a target for the first time. Here we consider the cost of resetting by associating to each reset a cost, which is a function of the distance travelled during the reset event. We compute the Laplace transform of the joint probability of first passage time $t_f$, number of resets $N$ and total resetting cost $C$, and use this to study the statistics of the total cost and also the time to completion ${\mathcal T} = C + t_f$. We show that in the limit of zero resetting rate, the mean total cost is finite for a linear cost function, vanishes for a sub-linear cost function and diverges for a super-linear cost function. This result contrasts with the case of no resetting where the cost is always zero. We also find that the resetting rate which optimizes the mean time to completion may be increased or decreased with respect to the case of no resetting cost according to the choice of cost function. For the case of an exponentially increasing cost function, we show that the mean total cost diverges at a finite resetting rate. We explain this by showing that the distribution of the cost has a power-law tail with a continuously varying exponent that depends on the resetting rate., Comment: 22 pages, 7 figures

We construct a reliable estimation of evolutionary parameters within the Wright-Fisher model, which describes changes in allele frequencies due to selection and genetic drift, from time-series data. Such data exists for biological populations, for example via artificial evolution experiments, and for the cultural evolution of behavior, such as linguistic corpora that document historical usage of different words with similar meanings. Our method of analysis builds on a Beta-with-Spikes approximation to the distribution of allele frequencies predicted by the Wright-Fisher model. We introduce a self-contained scheme for estimating the parameters in the approximation, and demonstrate its robustness with synthetic data, especially in the strong-selection and near-extinction regimes where previous approaches fail. We further apply to allele frequency data for baker's yeast (Saccharomyces cerevisiae), finding a significant signal of selection in cases where independent evidence supports such a conclusion. We further demonstrate the possibility of detecting time-points at which evolutionary parameters change in the context of a historical spelling reform in the Spanish language.

We consider a model system of persistent random walkers that can jam, pass through each other or jump apart (recoil) on contact. In a continuum limit, where particle motion between stochastic changes in direction becomes deterministic, we find that the stationary inter-particle distribution functions are governed by an inhomogeneous fourth-order differential equation. Our main focus is on determining the boundary conditions that these distribution functions should satisfy. We find that these do not arise naturally from physical considerations, but need to be carefully matched to functional forms that arise from the analysis of an underlying discrete process. The inter-particle distribution functions, or their first derivatives, are generically found to be discontinuous at the boundaries., Comment: 16 pages; 5 figures; published in PRE

We consider the interplay between persistent motion, which is a generic property of active particles, and a recoil interaction which causes particles to jump apart on contact. The recoil interaction exemplifies an active contact interaction between particles, which is inelastic and is generated by the active nature of the constituents. It is inspired by the `shock' dynamics of certain microorganisms, such as \emph{Pyramimonas octopus}, and always generates an effective repulsion between a pair of passive particles. Highly persistent particles can be attractive or repulsive, according to the shape of the recoil distribution. We show that the repulsive case admits an unexpected transition to attraction at intermediate persistence lengths, that originates in the advective effects of persistence. This allows active particles to fundamentally change the collective effect of active interactions amongst them, by varying their persistence length., Comment: 6 pages; 3 figures; published in EPL (see DOI); reference corrected

Languages emerge and change over time at the population level though interactions between individual speakers. It is, however, hard to directly observe how a single speaker's linguistic innovation precipitates a population-wide change in the language, and many theoretical proposals exist. We introduce a very general mathematical model that encompasses a wide variety of individual-level linguistic behaviours and provides statistical predictions for the population-level changes that result from them. This model allows us to compare the likelihood of empirically-attested changes in definite and indefinite articles in multiple languages under different assumptions on the way in which individuals learn and use language. We find that accounts of language change that appeal primarily to errors in childhood language acquisition are very weakly supported by the historical data, whereas those that allow speakers to change incrementally across the lifespan are more plausible, particularly when combined with social network effects., Comment: 50 pages, 11 figures

Colexification refers to the phenomenon of multiple meanings sharing one word in a language. Cross-linguistic lexification patterns have been shown to be largely predictable, as similar concepts are often colexified. We test a recent claim that, beyond this general tendency, communicative needs play an important role in shaping colexification patterns. We approach this question by means of a series of human experiments, using an artificial language communication game paradigm. Our results across four experiments match the previous cross-linguistic findings: all other things being equal, speakers do prefer to colexify similar concepts. However, we also find evidence supporting the communicative need hypothesis: when faced with a frequent need to distinguish similar pairs of meanings, speakers adjust their colexification preferences to maintain communicative efficiency, and avoid colexifying those similar meanings which need to be distinguished in communication. This research provides further evidence to support the argument that languages are shaped by the needs and preferences of their speakers.

In a model of $N$ volume-excluding spheres in a $d$-dimensional tube, we consider how differences between particles in their drift velocities, diffusivities, and sizes influence the steady state distribution and axial particle current. We show that the model is exactly solvable when the geometrical constraints prevent any particle from overtaking every other -- a notion we term quasi-one-dimensionality. Then, due to a ratchet effect, the current is biased towards the velocities of the least diffusive particles. We consider special cases of this model in one dimension, and derive the exact joint gap distribution for driven tracers in a passive bath. We describe the relationship between phase space structure and irreversible drift that makes the quasi-one-dimensional supposition key to the model's solvability., Comment: 26 pages, 7 figures

All living languages change over time. The causes for this are many, one being the emergence and borrowing of new linguistic elements. Competition between the new elements and older ones with a similar semantic or grammatical function may lead to speakers preferring one of them, and leaving the other to go out of use. We introduce a general method for quantifying competition between linguistic elements in diachronic corpora which does not require language-specific resources other than a sufficiently large corpus. This approach is readily applicable to a wide range of languages and linguistic subsystems. Here, we apply it to lexical data in five corpora differing in language, type, genre, and time span. We find that changes in communicative need are consistently predictive of lexical competition dynamics. Near-synonymous words are more likely to directly compete if they belong to a topic of conversation whose importance to language users is constant over time, possibly leading to the extinction of one of the competing words. By contrast, in topics which are increasing in importance for language users, near-synonymous words tend not to compete directly and can coexist. This suggests that, in addition to direct competition between words, language change can be driven by competition between topics or semantic subspaces.

We consider the persistent exclusion process in which a set of persistent random walkers interact via hard-core exclusion on a hypercubic lattice in $d$ dimensions. We work within the ballistic regime whereby particles continue to hop in the same direction over many lattice sites before reorienting. In the case of two particles, we find the mean first-passage time to a jammed state where the particles occupy adjacent sites and face each other. This is achieved within an approximation that amounts to embedding the one-dimensional system in a higher-dimensional reservoir. Numerical results demonstrate the validity of this approximation, even for small lattices. The results admit a straightforward generalisation to dilute systems comprising more than two particles. A self-consistency condition on the validity of these results suggest that clusters may form at arbitrarily low densities in the ballistic regime, in contrast to what has been found in the diffusive limit., Comment: Version to appear in JSTAT (18 pages; 10 figures)

The deluge of single-cell data obtained by sequencing, imaging and epigenetic markers has led to an increasingly detailed description of cell state. However, it remains challenging to identify how cells transition between different states, in part because data are typically limited to snapshots in time. A prerequisite for inferring cell state transitions from such snapshots is to distinguish whether transitions are coupled to cell divisions. To address this, we present two minimal branching process models of cell division and differentiation in a well-mixed population. These models describe dynamics where differentiation and division are coupled or uncoupled. For each model, we derive analytic expressions for each subpopulation's mean and variance and for the likelihood, allowing exact Bayesian parameter inference and model selection in the idealised case of fully observed trajectories of differentiation and division events. In the case of snapshots, we present a sample path algorithm and use this to predict optimal temporal spacing of measurements for experimental design. We then apply this methodology to an \textit{in vitro} dataset assaying the clonal growth of epiblast stem cells in culture conditions promoting self-renewal or differentiation. Here, the larger number of cell states necessitates approximate Bayesian computation. For both culture conditions, our inference supports the model where cell state transitions are coupled to division. For culture conditions promoting differentiation, our analysis indicates a possible shift in dynamics, with these processes becoming more coupled over time.

We review various combinatorial interpretations and mappings of stationary-state probabilities of the totally asymmetric, partially asymmetric and symmetric simple exclusion processes (TASEP, PASEP, SSEP respectively). In these steady states, the statistical weight of a configuration is determined from a matrix product, which can be written explicitly in terms of generalised ladder operators. This lends a natural association to the enumeration of random walks with certain properties. Specifically, there is a one-to-many mapping of steady-state configurations to a larger state space of discrete paths, which themselves map to an even larger state space of number permutations. It is often the case that the configuration weights in the extended space are of a relatively simple form (e.g., a Boltzmann-like distribution). Meanwhile, various physical properties of the nonequilibrium steady state - such as the entropy - can be interpreted in terms of how this larger state space has been partitioned. These mappings sometimes allow physical results to be derived very simply, and conversely the physical approach allows some new combinatorial problems to be solved. This work brings together results and observations scattered in the combinatorics and statistical physics literature, and also presents new results. The review is pitched at statistical physicists who, though not professional combinatorialists, are competent and enthusiastic amateurs., Comment: 56 pages, 21 figures

We construct and exactly solve a model of an extended Brownian ratchet. The model comprises an arbitrary number of heterogeneous, growing and shrinking filaments which together move a rigid membrane by a ratchet mechanism. The model draws parallels with the dynamics of actin filament networks at the leading edge of the cell. In the model, the filaments grow and contract stochastically. The model also includes forces which derive from a potential dependent on the separation between the filaments and the membrane. These forces serve to attract the filaments to the membrane or generate a surface tension that prevents the filaments from dispersing. We derive an N -dimensional diffusion equation for the N filament-membrane separations, which allows the steady-state probability distribution function to be calculated exactly under certain conditions. These conditions are fulfilled by the physically relevant cases of linear and quadratic interaction potentials. The exact solution of the diffusion equation furnishes expressions for the average velocity of the membrane and critical system parameters for which the system stalls and has zero net velocity. In the case of a restoring force, the membrane velocity grows as the square root of the force constant, whereas it decreases once a surface tension is introduced.

We compare the fluctuations in the velocity and in the fraction of time spent at a given position for minimal models of a passive and an active particle: an asymmetric random walker and a run-and-tumble particle in continuous time and on a 1D lattice. We compute rate functions and effective dynamics conditioned on large deviations for these observables. While generally different, for a unique and non-trivial choice of rates (up to a rescaling of time) the velocity rate functions for the two models become identical, whereas the effective processes generating the fluctuations remain distinct. This equivalence coincides with a remarkable parity of the spectra of the processes' generators. For the occupation-time problem, we show that both the passive and active particles undergo a prototypical dynamical phase transition when the average velocity is non-vanishing in the long-time limit., Comment: 27 pages, 10 figures

Newberry et al. (Detecting evolutionary forces in language change, Nature 551, 2017) tackle an important but difficult problem in linguistics, the testing of selective theories of language change against a null model of drift. Having applied a test from population genetics (the Frequency Increment Test) to a number of relevant examples, they suggest stochasticity has a previously under-appreciated role in language evolution. We replicate their results and find that while the overall observation holds, results produced by this approach on individual time series can be sensitive to how the corpus is organized into temporal segments (binning). Furthermore, we use a large set of simulations in conjunction with binning to systematically explore the range of applicability of the Frequency Increment Test. We conclude that care should be exercised with interpreting results of tests like the Frequency Increment Test on individual series, given the researcher degrees of freedom available when applying the test to corpus data, and fundamental differences between genetic and linguistic data. Our findings have implications for selection testing and temporal binning in general, as well as demonstrating the usefulness of simulations for evaluating methods newly introduced to the field.

Exact solutions of interacting random walk models, such as 1D lattice gases, offer precise insight into the origin of nonequilibrium phenomena. Here, we study a model of run-and-tumble particles on a ring lattice interacting via hardcore exclusion. We present the exact solution for one and two particles using a generating function technique. For two particles, the eigenvectors and eigenvalues are explicitly expressed using two parameters reminiscent of Bethe roots, whose numerical values are determined by polynomial equations which we derive. The spectrum depends in a complicated way on the ratio of direction reversal rate to lattice jump rate, $\omega$. For both one and two particles, the spectrum consists of separate real bands for large $\omega$, which mix and become complex-valued for small $\omega$. At exceptional values of $\omega$, two or more eigenvalues coalesce such that the Markov matrix is non-diagonalizable. A consequence of this intricate parameter dependence is the appearance of dynamical transitions: non-analytic minima in the longest relaxation times as functions of $\omega$ (for a given lattice size). Exceptional points are theoretically and experimentally relevant in, e.g., open quantum systems and multichannel scattering. We propose that the phenomenon should be a ubiquitous feature of classical nonequilibrium models as well, and of relevance to physical observables in this context., Comment: 29 pages, 7 figures, revised submission to J. Stat. Mech

Cross-situational word learning, wherein a learner combines information about possible meanings of a word across multiple exposures, has previously been shown to be a very powerful strategy to acquire a large lexicon in a short time. However, this success may derive from idealizations that are made when modeling the word-learning process. In particular, an earlier model assumed that a learner could perfectly recall all previous instances of a word's use and the inferences that were drawn about its meaning. In this work, we relax this assumption and determine the performance of a model cross-situational learner who forgets word-meaning associations over time. Our main finding is that it is possible for this learner to acquire a human-scale lexicon by adulthood with word-exposure and memory-decay rates that are consistent with empirical research on childhood word learning, as long as the degree of referential uncertainty is not too high or the learner employs a mutual exclusivity constraint. Our findings therefore suggest that successful word learning does not necessarily demand either highly accurate long-term tracking of word and meaning statistics or hypothesis-testing strategies., Comment: 39 pages, 16 figures

We consider the collective behaviour of active particles that locally align with their neighbours. Agent-based simulation models have previously shown that in one dimension, these particles can form into a flock that maintains its stability by stochastically alternating its direction. Until now, this behaviour has been seen in models based on continuum field equations only by appealing to long-range interactions that are not present in the simulation model. Here, we derive a set of stochastic field equations with local interactions that reproduces both qualitatively and quantitatively the behaviour of the agent-based model, including the alternating flock phase. A crucial component is a multiplicative noise term of the voter model type in the dynamics of the local polarization whose magnitude is inversely proportional to the local density. We show that there is an important subtlety in determining the physically appropriate noise, in that it depends on a careful choice of the field variables used to characterise the system. We further use the resulting equations to show that a nonlinear alignment interaction of at least cubic order is needed for flocking to arise.

The availability of large diachronic corpora has provided the impetus for a growing body of quantitative research on language evolution and meaning change. The central quantities in this research are token frequencies of linguistic elements in texts, with changes in frequency taken to reflect the popularity or selective fitness of an element. However, corpus frequencies may change for a wide variety of reasons, including purely random sampling effects, or because corpora are composed of contemporary media and fiction texts within which the underlying topics ebb and flow with cultural and socio-political trends. In this work, we introduce a simple model for controlling for topical fluctuations in corpora - the topical-cultural advection model - and demonstrate how it provides a robust baseline of variability in word frequency changes over time. We validate the model on a diachronic corpus spanning two centuries, and a carefully-controlled artificial language change scenario, and then use it to correct for topical fluctuations in historical time series. Finally, we use the model to show that the emergence of new words typically corresponds with the rise of a trending topic. This suggests that some lexical innovations occur due to growing communicative need in a subspace of the lexicon, and that the topical-cultural advection model can be used to quantify this., Comment: Code to run the analyses described in this paper is now available at https://github.com/andreskarjus/topical_cultural_advection_model . A previous shorter version of this paper outlining the basic model appeared as an extended abstract in the proceedings of the Society for Computation in Linguistics (Karjus et al. 2018, Topical advection as a baseline model for corpus-based lexical dynamics)

The Renyi entropy is a generalisation of the Shannon entropy that is sensitive to the fine details of a probability distribution. We present results for the Renyi entropy of the totally asymmetric exclusion process (TASEP). We calculate explicitly an entropy whereby the squares of configuration probabilities are summed, using the matrix product formalism to map the problem to one involving a six direction lattice walk in the upper quarter plane. We derive the generating function across the whole phase diagram, using an obstinate kernel method. This gives the leading behaviour of the Renyi entropy and corrections in all phases of the TASEP. The leading behaviour is given by the result for a Bernoulli measure and we conjecture that this holds for all Renyi entropies. Within the maximal current phase the correction to the leading behaviour is logarithmic in the system size. Finally, we remark upon a special property of equilibrium systems whereby discontinuities in the Renyi entropy arise away from phase transitions, which we refer to as secondary transitions. We find no such secondary transition for this nonequilibrium system, supporting the notion that these are specific to equilibrium cases.

We investigate mechanisms for language change within a framework where an unconventional signal for a meaning is first innovated, and then subsequently propagated through a speech community to replace the existing convention. We appeal to the notion of universality as it applies to complex interacting systems in the physical sciences and which establishes a link between generic ('universal') patterns at the macroscopic scale and relates them to symmetries at the microscopic scale. By relating the presence and absence of specific symmetries to fundamentally distinct mechanisms for language change at the level of individual speakers and speech acts, we are able to draw conclusions about which of these underlying mechanisms are most likely to be responsible for the changes that actually occur. Since these mechanisms are typically believed to be common to all speakers in all speech communities, this provides a means to relate universals in individual behaviour to language universals., Comment: 15 pages, 2 figures; Proceedings of the Flow Machines Workshop: Creativity and Universality in Language, Paris, June 18 to 20, 2014

Methods and insights from statistical physics are finding an increasing variety of applications where one seeks to understand the emergent properties of a complex interacting system. One such area concerns the dynamics of language at a variety of levels of description, from the behaviour of individual agents learning simple artificial languages from each other, up to changes in the structure of languages shared by large groups of speakers over historical timescales. In this Colloquium, we survey a hierarchy of scales at which language and linguistic behaviour can be described, along with the main progress in understanding that has been made at each of them---much of which has come from the statistical physics community. We argue that future developments may arise by linking the different levels of the hierarchy together in a more coherent fashion, in particular where this allows more effective use of rich empirical data sets., Comment: Colloquium (short review paper) solicited by European Physical Journal B. 18 pages, 3 figures. accepted v2 contains more text, figures, references and coherence