Search

Multi-type birth-death processes underlie approaches for inferring evolutionary dynamics from phylogenetic trees across biological scales, ranging from deep-time species macroevolution to rapid viral evolution and somatic cellular proliferation. A limitation of current phylogenetic birth-death models is that they require restrictive linearity assumptions that yield tractable message-passing likelihoods, but that also preclude interactions between individuals. Many fundamental evolutionary processes -- such as environmental carrying capacity or frequency-dependent selection -- entail interactions, and may strongly influence the dynamics in some systems. Here, we introduce a multi-type birth-death process in mean-field interaction with an ensemble of replicas of the focal process. We prove that, under quite general conditions, the ensemble's stochastically evolving interaction field converges to a deterministic trajectory in the limit of an infinite ensemble. In this limit, the replicas effectively decouple, and self-consistent interactions appear as nonlinearities in the infinitesimal generator of the focal process. We investigate a special case that is rich enough to model both carrying capacity and frequency-dependent selection while yielding tractable message-passing likelihoods in the context of a phylogenetic birth-death model., Comment: 31 pages, 1 figure

In 2006, Warnow, Evans, Ringe, and Nakhleh proposed a stochastic model (hereafter, the WERN 2006 model) of multi-state linguistic character evolution that allowed for homoplasy and borrowing. They proved that if there is no borrowing between languages and homoplastic states are known in advance, then the phylogenetic tree of a set of languages is statistically identifiable under this model, and they presented statistically consistent methods for estimating these phylogenetic trees. However, they left open the question of whether a phylogenetic network -- which would explicitly model borrowing between languages that are in contact -- can be estimated under the model of character evolution. Here, we establish that under some mild additional constraints on the WERN 2006 model, the phylogenetic network topology is statistically identifiable, and we present algorithms to infer the phylogenetic network. We discuss the ramifications for linguistic phylogenetic network estimation in practice, and suggest directions for future research., Comment: 16 pages, 2 figures

We introduce the space of virtual Markov chains (VMCs) as a projective limit of the spaces of all finite state space Markov chains (MCs), in the same way that the space of virtual permutations is the projective limit of the spaces of all permutations of finite sets. We introduce the notions of virtual initial distribution (VID) and a virtual transition matrix (VTM), and we show that the law of any VMC is uniquely characterized by a pair of a VID and VTM which have to satisfy a certain compatibility condition. Lastly, we study various properties of compact convex sets associated to the theory of VMCs, including that the Birkhoff-von Neumann theorem fails in the virtual setting., Comment: 46 pages

For $1\le p \le \infty$, the Fr\'echet $p$-mean of a probability measure on a metric space is an important notion of central tendency that generalizes the usual notions in the real line of mean ($p=2$) and median ($p=1$). In this work we prove a collection of limit theorems for Fr\'echet means and related objects, which, in general, constitute a sequence of random closed sets. On the one hand, we show that many limit theorems (a strong law of large numbers, an ergodic theorem, and a large deviations principle) can be simply descended from analogous theorems on the space of probability measures via purely topological considerations. On the other hand, we provide the first sufficient conditions for the strong law of large numbers to hold in a $T_2$ topology (in particular, the Fell topology), and we show that this condition is necessary in some special cases. We also discuss statistical and computational implications of the results herein., Comment: 33 pages, 1 figure

Given a two-sided real-valued L\'evy process $(X_t)_{t \in \mathbb{R}}$, define processes $(L_t)_{t \in \mathbb{R}}$ and $(M_t)_{t \in \mathbb{R}}$ by $L_t := \sup\{h \in \mathbb{R} : h - \alpha(t-s) \le X_s \text{ for all } s \le t\} = \inf\{X_s + \alpha(t-s) : s \le t\}$, $t \in \mathbb{R}$, and $M_t := \sup \{ h \in \mathbb{R} : h - \alpha|t-s| \leq X_s \text{ for all } s \in \mathbb{R} \} = \inf \{X_s + \alpha |t-s| : s \in \mathbb{R}\}$, $t \in \mathbb{R}$. The corresponding contact sets are the random sets $\mathcal{H}_\alpha := \{ t \in \mathbb{R} : X_{t}\wedge X_{t-} = L_t\}$ and $\mathcal{Z}_\alpha := \{ t \in \mathbb{R} : X_{t}\wedge X_{t-} = M_t\}$. For a fixed $\alpha>\mathbb{E}[X_1]$ (resp. $\alpha>|\mathbb{E}[X_1]|$) the set $\mathcal{H}_\alpha$ (resp. $\mathcal{Z}_\alpha$) is non-empty, closed, unbounded above and below, stationary, and regenerative. The collections $(\mathcal{H}_{\alpha})_{\alpha > \mathbb{E}[X_1]}$ and $(\mathcal{Z}_{\alpha})_{\alpha > |\mathbb{E}[X_1]|}$ are increasing in $\alpha$ and the regeneration property is compatible with these inclusions in that each family is a continuum of embedded regenerative sets in the sense of Bertoin. We show that $(\sup\{t < 0 : t \in \mathcal{H}_\alpha\})_{\alpha > \mathbb{E}[X_1]}$ is a c\`adl\`ag, nondecreasing, pure jump process with independent increments and determine the intensity measure of the associated Poisson process of jumps. We obtain a similar result for $(\sup\{t < 0 : t \in \mathcal{Z}_\alpha\})_{\alpha > |\beta|}$ when $(X_t)_{t \in \mathbb{R}}$ is a (two-sided) Brownian motion with drift $\beta$., Comment: 11 pages

For $\alpha >0$, the $\alpha$-Lipschitz minorant of a function $f : \mathbb{R} \rightarrow \mathbb{R}$ is the greatest function $m : \mathbb{R} \rightarrow \mathbb{R}$ such that $m \leq f$ and $\vert m(s) - m(t) \vert \leq \alpha \vert s-t \vert$ for all $s,t \in \mathbb{R}$, should such a function exist. If $X=(X_t)_{t \in \mathbb{R}}$ is a real-valued L\'evy process that is not a pure linear drift with slope $\pm \alpha$, then the sample paths of $X$ have an $\alpha$-Lipschitz minorant almost surely if and only if $\mathbb{E}[\vert X_1 \vert]< \infty$ and $\vert \mathbb{E}[X_1]\vert < \alpha$. Denoting the minorant by $M$, we consider the contact set $\mathcal{Z}:=\{ t \in \mathbb{R} : M_t = X_t \wedge X_{t-}\}$, which, since it is regenerative and stationary, has the distribution of the closed range of some subordinator "made stationary" in a suitable sense. We provide a description of the excursions of the L\'evy process away from its contact set similar to the one presented in It\^o excursion theory. We study the distribution of the excursion on the special interval straddling zero. We also give an explicit path decomposition of the other "generic" excursions in the case of Brownian motion with drift $\beta$ with $\vert \beta \vert < \alpha$. Finally, we investigate the progressive enlargement of the Brownian filtration by the random time that is the first point of the contact set after zero., Comment: 35 pages

An infinite sequence of real random variables $(\xi_1, \xi_2, \dots)$ is said to be rotatable if every finite subsequence $(\xi_1, \dots, \xi_n)$ has a spherically symmetric distribution. A celebrated theorem of Freedman states that $(\xi_1, \xi_2, \dots)$ is rotatable if and only if $\xi_j = \tau \eta_j$ for all $j$, where $(\eta_1, \eta_2, \dots)$ is a sequence of independent standard Gaussian random variables and $\tau$ is an independent nonnegative random variable. Freedman's theorem is equivalent to a classical result of Schoenberg which says that a continuous function $\phi : \mathbb{R}_+ \to \mathbb{C}$ with $\phi(0) = 1$ is completely monotone if and only if $\phi_n: \mathbb{R}^n \to \mathbb{R}$ given by $\phi_n(x_1, \ldots, x_n) = \phi(x_1^2 + \cdots + x_n^2)$ is nonnegative definite for all $n \in \mathbb{N}$. We establish the analogue of Freedman's theorem for sequences of random variables taking values in local fields using probabilistic methods and then use it to establish a local field analogue of Schoenberg's result. Along the way, we obtain a local field counterpart of an observation variously attributed to Maxwell, Poincar\'e, and Borel which says that if $(\zeta_1, \ldots, \zeta_n)$ is uniformly distributed on the sphere of radius $\sqrt{n}$ in $\mathbb{R}^n$, then, for fixed $k \in \mathbb{N}$, the distribution of $(\zeta_1, \ldots, \zeta_k)$ converges to that of a vector of $k$ independent standard Gaussian random variables as $n \to \infty$., Comment: 13 pages

A radix sort tree arises when storing distinct infinite binary words in the leaves of a binary tree such that for any two words their common prefixes coincide with the common prefixes of the corresponding two leaves. If one deletes the out-degree $1$ vertices in the radix sort tree and "closes up the gaps", then the resulting PATRICIA tree maintains all the information that is necessary for sorting the infinite words into lexicographic order. We investigate the PATRICIA chains -- the tree-valued Markov chains that arise when successively building the PATRICIA trees for the collection of infinite binary words $Z_1,\ldots, Z_n$, $n=1,2,\ldots$, where the source words $Z_1, Z_2,\ldots$ are independent and have a common diffuse distribution on $\{0,1\}^\infty$. It turns out that the PATRICIA chains share a common collection of backward transition probabilities and that these are the same as those of a chain introduced by R\'emy for successively generating uniform random binary trees with larger and larger numbers of leaves. This means that the infinite bridges of any PATRICIA chain (that is, the chains obtained by conditioning a PATRICIA chain on its remote future) coincide with the infinite bridges of the R\'emy chain. The infinite bridges of the R\'emy chain are characterized concretely in Evans, Gr\"ubel, and Wakolbinger 2017 and we recall that characterization here while adding some details and clarifications., Comment: 35 pages

We show that any smooth bi-Lipschitz $h$ can be represented exactly as a composition $h_m \circ ... \circ h_1$ of functions $h_1,...,h_m$ that are close to the identity in the sense that each $\left(h_i-\mathrm{Id}\right)$ is Lipschitz, and the Lipschitz constant decreases inversely with the number $m$ of functions composed. This implies that $h$ can be represented to any accuracy by a deep residual network whose nonlinear layers compute functions with a small Lipschitz constant. Next, we consider nonlinear regression with a composition of near-identity nonlinear maps. We show that, regarding Fr\'echet derivatives with respect to the $h_1,...,h_m$, any critical point of a quadratic criterion in this near-identity region must be a global minimizer. In contrast, if we consider derivatives with respect to parameters of a fixed-size residual network with sigmoid activation functions, we show that there are near-identity critical points that are suboptimal, even in the realizable case. Informally, this means that functional gradient methods for residual networks cannot get stuck at suboptimal critical points corresponding to near-identity layers, whereas parametric gradient methods for sigmoidal residual networks suffer from suboptimal critical points in the near-identity region.

Suppose that $(X_t)_{t \ge 0}$ is a one-dimensional Brownian motion with negative drift $-\mu$. It is possible to make sense of conditioning this process to be in the state $0$ at an independent exponential random time and if we kill the conditioned process at the exponential time the resulting process is Markov. If we let the rate parameter of the random time go to $0$, then the limit of the killed Markov process evolves like $X$ conditioned to hit $0$, after which time it behaves as $X$ killed at the last time $X$ visits $0$. Equivalently, the limit process has the dynamics of the killed "bang--bang" Brownian motion that evolves like Brownian motion with positive drift $+\mu$ when it is negative, like Brownian motion with negative drift $-\mu$ when it is positive, and is killed according to the local time spent at $0$. An extension of this result holds in great generality for Borel right processes conditioned to be in some state $a$ at an exponential random time, at which time they are killed. Our proofs involve understanding the Campbell measures associated with local times, the use of excursion theory, and the development of a suitable analogue of the "bang--bang" construction for general Markov processes. As examples, we consider the special case when the transient Borel right process is a one-dimensional diffusion. Characterizing the limiting conditioned and killed process via its infinitesimal generator leads to an investigation of the $h$-transforms of transient one-dimensional diffusion processes that goes beyond what is known and is of independent interest., Comment: 39 pages

We consider a Markov chain that iteratively generates a sequence of random finite words in such a way that the $n^{\mathrm{th}}$ word is uniformly distributed over the set of words of length $2n$ in which $n$ letters are $a$ and $n$ letters are $b$: at each step an $a$ and a $b$ are shuffled in uniformly at random among the letters of the current word. We obtain a concrete characterization of the Doob-Martin boundary of this Markov chain. Writing $N(u)$ for the number of letters $a$ (equivalently, $b$) in the finite word $u$, we show that a sequence $(u_n)_{n \in \mathbb{N}}$ of finite words converges to a point in the boundary if, for an arbitrary word $v$, there is convergence as $n$ tends to infinity of the probability that the selection of $N(v)$ letters $a$ and $N(v)$ letters $b$ uniformly at random from $u_n$ and maintaining their relative order results in $v$. We exhibit a bijective correspondence between the points in the boundary and ergodic random total orders on the set $\{a_1, b_1, a_2, b_2, \ldots \}$ that have distributions which are separately invariant under finite permutations of the indices of the $a'$s and those of the $b'$s. We establish a further bijective correspondence between the set of such random total orders and the set of pairs $(\mu,\nu)$ of diffuse probability measures on $[0,1]$ such that $\frac{1}{2}(\mu+\nu)$ is Lebesgue measure: the restriction of the random total order to $\{a_1, b_1, \ldots, a_n, b_n\}$ is obtained by taking $X_1, \ldots, X_n$ (resp. $Y_1, \ldots, Y_n$) i.i.d. with common distribution $\mu$ (resp. $\nu$), letting $(Z_1, \ldots, Z_{2n})$ be $\{X_1, Y_1, \ldots, X_n, Y_n\}$ in increasing order, and declaring that the $k^{\mathrm{th}}$ smallest element in the restricted total order is $a_i$ (resp. $b_j$) if $Z_k = X_i$ (resp. $Z_k = Y_j$)., Comment: 24 pages, revised to deal with reviewer's comments

The trie-based radix sort algorithm stores pairwise different infinite binary strings in the leaves of a binary tree in a way that the Ulam-Harris coding of each leaf equals a prefix (that is, an initial segment) of the corresponding string, with the prefixes being of minimal length so that they are pairwise different. We investigate the {\em radix sort tree chains} -- the tree-valued Markov chains that arise when successively storing infinite binary strings $Z_1,\ldots, Z_n$, $n=1,2,\ldots$ according to the trie-based radix sort algorithm, where the source strings $Z_1, Z_2,\ldots$ are independent and identically distributed. We establish a bijective correspondence between the full Doob--Martin boundary of the radix sort tree chain with a {\em symmetric Bernoulli source} (that is, each $Z_k$ is a fair coin-tossing sequence) and the family of radix sort tree chains for which the common distribution of the $Z_k$ is a diffuse probability measure on $\{0,1\}^\infty$. In essence, our result characterizes all the ways that it is possible to condition such a chain of radix sort trees consistently on its behavior "in the large"., Comment: 15 pages, 0 figures

The advent of accessible ancient DNA technology now allows the direct ascertainment of allele frequencies in ancestral populations, thereby enabling the use of allele frequency time series to detect and estimate natural selection. Such direct observations of allele frequency dynamics are expected to be more powerful than inferences made using patterns of linked neutral variation obtained from modern individuals. We develop a Bayesian method to make use of allele frequency time series data and infer the parameters of general diploid selection, along with allele age, in non-equilibrium populations. We introduce a novel path augmentation approach, in which we use Markov chain Monte Carlo to integrate over the space of allele frequency trajectories consistent with the observed data. Using simulations, we show that this approach has good power to estimate selection coefficients and allele age. Moreover, when applying our approach to data on horse coat color, we find that ignoring a relevant demographic history can significantly bias the results of inference. Our approach is made available in a C++ software package., Comment: 27 pages

A scaling on some space is a measurable action of the group of positive real numbers. A measure on a measurable space equipped with a scaling is said to be $\alpha$-homogeneous for some nonzero real number $\alpha$ if the mass of any measurable set scaled by any factor $t > 0$ is the multiple $t^{-\alpha}$ of the set's original mass. It is shown rather generally that given an $\alpha$-homogeneous measure on a measurable space there is a measurable bijection between the space and the Cartesian product of a subset of the space and the positive real numbers (that is, a "system of polar coordinates") such that the push-forward of the $\alpha$-homogeneous measure by this bijection is the product of a probability measure on the first component (that is, on the "angular" component) and an $\alpha$-homogeneous measure on the positive half-line (that is, on the "radial" component). This result is applied to the intensity measures of Poisson processes that arise in L\'evy-Khinchin-It\^o-like representations of infinitely divisible random elements. It is established that if a strictly stable random element in a convex cone admits a series representation as the sum of points of a Poisson process, then it necessarily has a LePage representation as the sum of i.i.d. random elements of the cone scaled by the successive points of an independent unit intensity Poisson process on the positive half-line each raised to the power $-\frac{1}{\alpha}$., Comment: 22 pages

For $d \in \{1,2,3\}$, let $(B^d_t;~ t \geq 0)$ be a $d$-dimensional standard Brownian motion. We study the $d$-Brownian span set $Span(d):=\{t-s;~ B^d_s=B^d_t~\mbox{for some}~0 \leq s \leq t\}$. We prove that almost surely the random set $Span(d)$ is $\sigma$-compact and dense in $\mathbb{R}_{+}$. In addition, we show that $Span(1)=\mathbb{R}_{+}$ almost surely; the Lebesgue measure of $Span(2)$ is $0$ almost surely and its Hausdorff dimension is $1$ almost surely; and the Hausdorff dimension of $Span(3)$ is $\frac{1}{2}$ almost surely. We also list a number of conjectures and open problems., Comment: 33 pages, 4 figures. This paper is published by http://projecteuclid.org/euclid.aihp/1500624032

Given an edge-weighted tree $T$ with $n$ leaves, sample the leaves uniformly at random without replacement and let $W_k$, $2 \le k \le n$, be the length of the subtree spanned by the first $k$ leaves. We consider the question, "Can $T$ be identified (up to isomorphism) by the joint probability distribution of the random vector $(W_2, \ldots, W_n)$?" We show that if $T$ is known {\em a priori} to belong to one of various families of edge-weighted trees, then the answer is, "Yes." These families include the edge-weighted trees with edge-weights in general position, the ultrametric edge-weighted trees, and certain families with equal weights on all edges such as $(k+1)$-valent and rooted $k$-ary trees for $k \ge 2$ and caterpillars.

R\'emy's algorithm is a Markov chain that iteratively generates a sequence of random trees in such a way that the $n^{\mathrm{th}}$ tree is uniformly distributed over the set of rooted, planar, binary trees with $2n+1$ vertices. We obtain a concrete characterization of the Doob--Martin boundary of this transient Markov chain and thereby delineate all the ways in which, loosely speaking, this process can be conditioned to "go to infinity" at large times. A (deterministic) sequence of finite rooted, planar, binary trees converges to a point in the boundary if for each $m$ the random rooted, planar, binary tree spanned by $m+1$ leaves chosen uniformly at random from the $n^{\mathrm{th}}$ tree in the sequence converges in distribution as $n$ tends to infinity -- a notion of convergence that is analogous to one that appears in the recently developed theory of graph limits. We show that a point in the Doob--Martin boundary may be identified with the following ensemble of objects: a complete separable $\mathbb{R}$-tree that is rooted and binary in a suitable sense, a diffuse probability measure on the $\mathbb{R}$-tree that allows us to make sense of sampling points from it, and a kernel on the $\mathbb{R}$-tree that describes the probability that the first of a given pair of points is below and to the left of their most recent common ancestor while the second is below and to the right. The Doob--Martin boundary corresponds bijectively to the set of extreme points of the closed convex set of normalized nonnegative harmonic functions, in other words, the minimal and full Doob--Martin boundaries coincide. These results are in the spirit of the identification of graphons as limit objects in the theory of graph limits., Comment: Compared to version 3, which was published in Ann. Probab. 45 (2017), 225-277, this version has the additional Section 9, which corrects Remark 5.20 and the proof of Lemma 5.3, and amends Definition 5.8

Schools with the highest average student performance are often the smallest schools; localities with the highest rates of some cancers are frequently small and the effects observed in clinical trials are likely to be largest for the smallest numbers of subjects. Informal explanations of this "small-schools phenomenon" point to the fact that the sample means of smaller samples have higher variances. But this cannot be a complete explanation: If we draw two samples from a diffuse distribution that is symmetric about some point, then the chance that the smaller sample has larger mean is 50\%. A particular consequence of results proved below is that if one draws three or more samples of different sizes from the same normal distribution, then the sample mean of the smallest sample is most likely to be highest, the sample mean of the second smallest sample is second most likely to be highest, and so on; this is true even though for any pair of samples, each one of the pair is equally likely to have the larger sample mean. Our conclusions are relevant to certain stochastic choice models including the following generalization of Thurstone's Law of Comparative Judgment. There are $n$ items. Item $i$ is preferred to item $j$ if $Z_i < Z_j$, where $Z$ is a random $n$-vector of preference scores. Suppose $\mathbb{P}\{Z_i = Z_j\} = 0$ for $i \ne j$, so there are no ties. Item $k$ is the favorite if $Z_k < \min_{i\ne k} Z_i$. Let $p_i$ denote the chance that item $i$ is the favorite. We characterize a large class of distributions for $Z$ for which $p_1 > p_2 > \cdots > p_n$. Our results are most surprising when $\mathbb{P}\{Z_i < Z_j\} = \mathbb{P}\{Z_i > Z_j\} = \frac{1}{2}$ for $i \ne j$, so neither of any two items is likely to be preferred over the other in a pairwise comparison., Comment: Revised to take into account referees' comments. Mention of the regression effect has been removed to concentrate on the small schools phenomenon as a concrete illustration of our results

The classical skew-product decomposition of planar Brownian motion represents the process in polar coordinates as an autonomously Markovian radial part and an angular part that is an independent Brownian motion on the unit circle time-changed according to the radial part. Theorem 4 of Liao (2009) gives a broad generalization of this fact to a setting where there is a diffusion on a manifold $X$ with a distribution that is equivariant under the smooth action of a Lie group $K$. Under appropriate conditions, there is a decomposition into an autonomously Markovian "radial" part that lives on the space of orbits of $K$ and an "angular" part that is an independent Brownian motion on the homogeneous space $K/M$, where $M$ is the isotropy subgroup of a point of $x$, that is time-changed with a time-change that is adapted to the filtration of the radial part. We present two apparent counterexamples to Theorem 4 of Liao (2009). In the first counterexample the angular part is not a time-change of any Brownian motion on $K/M$, whereas in the second counterexample the angular part is the time-change of a Brownian motion on $K/M$ but this Brownian motion is not independent of the radial part. In both of these examples $K/M$ has dimension $1$. The statement and proof of Theorem 4 from Liao (2009) remain valid when $K/M$ has dimension greater than $1$. Our examples raise the question of what conditions lead to the usual sort of skew-product decomposition when $K/M$ has dimension $1$ and what conditions lead to there being no decomposition at all or one in which the angular part is a time-changed Brownian motion but this Brownian motion is not independent of the radial part., Comment: 14 pages; added Example 2 which was suggested by a referee; open question added in Section 5

We consider a population living in a patchy environment that varies stochastically in space and time. The population is composed of two morphs (that is, individuals of the same species with different genotypes). In terms of survival and reproductive success, the associated phenotypes differ only in their habitat selection strategies. We compute invasion rates corresponding to the rates at which the abundance of an initially rare morph increases in the presence of the other morph established at equilibrium. If both morphs have positive invasion rates when rare, then there is an equilibrium distribution such that the two morphs coexist; that is, there is a protected polymorphism for habitat selection. Alternatively, if one morph has a negative invasion rate when rare, then it is asymptotically displaced by the other morph under all initial conditions where both morphs are present. We refine the characterization of an evolutionary stable strategy for habitat selection from [Schreiber, 2012] in a mathematically rigorous manner. We provide a necessary and sufficient condition for the existence of an ESS that uses all patches and determine when using a single patch is an ESS. We also provide an explicit formula for the ESS when there are two habitat types. We show that adding environmental stochasticity results in an ESS that, when compared to the ESS for the corresponding model without stochasticity, spends less time in patches with larger carrying capacities and possibly makes use of sink patches, thereby practicing a spatial form of bet hedging., Comment: Revised in light of referees' comments, Published on-line Journal of Mathematical Biology 2014 http://link.springer.com/article/10.1007/s00285-014-0824-5

A metric measure space is a complete separable metric space equipped with probability measure that has full support. Two such spaces are equivalent if they are isometric as metric spaces via an isometry that maps the probability measure on the first space to the probability measure on the second. The resulting set of equivalence classes can be metrized with the Gromov-Prohorov metric of Greven, Pfaffelhuber and Winter. We consider the natural binary operation $\boxplus$ on this space that takes two metric measure spaces and forms their Cartesian product equipped with the sum of the two metrics and the product of the two probability measures. We show that the metric measure spaces equipped with this operation form a cancellative, commutative, Polish semigroup with a translation invariant metric and that each element has a unique factorization into prime elements. We investigate the interaction between the semigroup structure and the natural action of the positive real numbers on this space that arises from scaling the metric. For example, we show that for any given positive real numbers $a,b,c$ the trivial space is the only space $\mathcal{X}$ that satisfies $a \mathcal{X} \boxplus b \mathcal{X} = c \mathcal{X}$. We establish that there is no analogue of the law of large numbers: if $\mathbf{X}_1, \mathbf{X}_2$..., is an identically distributed independent sequence of random spaces, then no subsequence of $\frac{1}{n} \boxplus_{k=1}^n \mathbf{X}_k$ converges in distribution unless each $\mathbf{X}_k$ is almost surely equal to the trivial space. We characterize the infinitely divisible probability measures and the L\'evy processes on this semigroup, characterize the stable probability measures and establish a counterpart of the LePage representation for the latter class., Comment: 48 pages, 0 figures. The previous version considered only compact metric measure spaces, but new arguments allow all the results of the previous version to be extended to the setting of complete separable metric measure spaces

In a uniform random permutation \Pi of [n] := {1,2,...,n}, the set of elements k in [n-1] such that \Pi(k+1) = \Pi(k) + 1 has the same distribution as the set of fixed points of \Pi that lie in [n-1]. We give three different proofs of this fact using, respectively, an enumeration relying on the inclusion-exclusion principle, the introduction of two different Markov chains to generate uniform random permutations, and the construction of a combinatorial bijection. We also obtain the distribution of the analogous set for circular permutations that consists of those k in [n] such that \Pi(k+1 mod n) = \Pi(k) + 1 mod n. This latter random set is just the set of fixed points of the commutator [\rho, \Pi], where \rho is the n-cycle (1,2,...,n). We show for a general permutation \eta that, under weak conditions on the number of fixed points and 2-cycles of \eta, the total variation distance between the distribution of the number of fixed points of [\eta,\Pi] and a Poisson distribution with expected value 1 is small when n is large., Comment: revised to incorporate corrections suggested by referee

We investigate the properties of a Wright-Fisher diffusion process started from frequency x at time 0 and conditioned to be at frequency y at time T. Such a process is called a bridge. Bridges arise naturally in the analysis of selection acting on standing variation and in the inference of selection from allele frequency time series. We establish a number of results about the distribution of neutral Wright-Fisher bridges and develop a novel rejection sampling scheme for bridges under selection that we use to study their behavior., Comment: 25 pages, 3 figures, 1 table

Kilometer-sized moonlets in Saturn's A ring create S-shaped wakes called "propellers" in surrounding material. The Cassini spacecraft has tracked the motions of propellers for several years and finds that they deviate from Keplerian orbits having constant semimajor axes. The inferred orbital migration is known to switch sign. We show using a statistical test that the time series of orbital longitudes of the propeller Bl\'eriot is consistent with that of a time-integrated Gaussian random walk. That is, Bl\'eriot's observed migration pattern is consistent with being stochastic. We further show, using a combination of analytic estimates and collisional N-body simulations, that stochastic migration of the right magnitude to explain the Cassini observations can be driven by encounters with ring particles 10-20 m in radius. That the local ring mass is concentrated in decameter-sized particles is supported on independent grounds by occultation analyses., Comment: 10 pages, 7 figures, 1 table; accepted to MNRAS. v2: edited for mathematical and expositional clarity and completeness

The inverse first passage time problem asks whether, for a Brownian motion $B$ and a nonnegative random variable $\zeta$, there exists a time-varying barrier $b$ such that $\mathbb{P}\{B_s>b(s),0\leq s\leq t\}=\mathbb{P}\{\zeta>t\}$. We study a "smoothed" version of this problem and ask whether there is a "barrier" $b$ such that $ \mathbb{E}[\exp(-\lambda\int_0^t\psi(B_s-b(s))\,ds)]=\mathbb{P}\{\zeta >t\}$, where $\lambda$ is a killing rate parameter, and $\psi:\mathbb{R}\to[0,1]$ is a nonincreasing function. We prove that if $\psi$ is suitably smooth, the function $t\mapsto \mathbb{P}\{\zeta>t\}$ is twice continuously differentiable, and the condition $0<-\frac{d\log\mathbb{P}\{\zeta>t\}}{dt}<\lambda$ holds for the hazard rate of $\zeta$, then there exists a unique continuously differentiable function $b$ solving the smoothed problem. We show how this result leads to flexible models of default for which it is possible to compute expected values of contingent claims., Comment: Published in at http://dx.doi.org/10.1214/12-AAP902 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

For $\alpha > 0$, the $\alpha$-Lipschitz minorant of a function $f: \mathbb{R} \to \mathbb{R}$ is the greatest function $m : \mathbb{R} \to \mathbb{R}$ such that $m \leq f$ and $|m(s)-m(t)| \le \alpha |s-t|$ for all $s,t \in \mathbb{R}$, should such a function exist. If $X=(X_t)_{t \in \mathbb{R}}$ is a real-valued L\'evy process that is not pure linear drift with slope $\pm \alpha$, then the sample paths of $X$ have an $\alpha$-Lipschitz minorant almost surely if and only if $| \mathbb{E}[X_1] | < \alpha$. Denoting the minorant by $M$, we investigate properties of the random closed set $\mathcal{Z} := {t \in \mathbb{R} : M_t = X_t \wedge X_{t-}}$, which, since it is regenerative and stationary, has the distribution of the closed range of some subordinator "made stationary" in a suitable sense. We give conditions for the contact set $\mathcal{Z}$ to be countable or to have zero Lebesgue measure, and we obtain formulas that characterize the L\'evy measure of the associated subordinator. We study the limit of $\mathcal{Z}$ as $\alpha \to \infty$ and find for the so-called abrupt L\'evy processes introduced by Vigon that this limit is the set of local infima of $X$. When $X$ is a Brownian motion with drift $\beta$ such that $|\beta| < \alpha$, we calculate explicitly the densities of various random variables related to the minorant., Comment: 42 pages, 3 figures, revised to incorporate comments from readers plus further results on the behavior of Levy processes at their local extrema and extra references

A short proof is given of a necessary and sufficient condition for the normalized occupation measure of a L\'evy process in a metrizable compact group to be asymptotically uniform with probability one., Comment: 13 pages

Principal components (PCA) and hierarchical clustering are two of the most heavily used techniques for analyzing the differences between nucleic acid sequence samples sampled from a given environment. However, a classical application of these techniques to distances computed between samples can lack transparency because there is no ready interpretation of the axes of classical PCA plots, and it is difficult to assign any clear intuitive meaning to either the internal nodes or the edge lengths of trees produced by distance-based hierarchical clustering methods such as UPGMA. We show that more interesting and interpretable results are produced by two new methods that leverage the special structure of phylogenetic placement data. Edge principal components analysis enables the detection of important differences between samples that contain closely related taxa. Each principal component axis is simply a collection of signed weights on the edges of the phylogenetic tree, and these weights are easily visualized by a suitable thickening and coloring of the edges. Squash clustering outputs a (rooted) clustering tree in which each internal node corresponds to an appropriate "average" of the original samples at the leaves below the node. Moreover, the length of an edge is a suitably defined distance between the averaged samples associated with the two incident nodes, rather than the less interpretable average of distances produced by UPGMA. We present these methods and illustrate their use with data from the microbiome of the human vagina.

We consider stochastic equations of the form $X_k = \phi_k(X_{k+1}) Z_k$, $k \in \mathbb{N}$, where $X_k$ and $Z_k$ are random variables taking values in a compact group $G_k$, $\phi_k: G_{k+1} \to G_k$ is a continuous homomorphism, and the noise $(Z_k)_{k \in \mathbb{N}}$ is a sequence of independent random variables. We take the sequence of homomorphisms and the sequence of noise distributions as given, and investigate what conditions on these objects result in a unique distribution for the "solution" sequence $(X_k)_{k \in \mathbb{N}}$ and what conditions permits the existence of a solution sequence that is a function of the noise alone (that is, the solution does not incorporate extra input randomness "at infinity"). Our results extend previous work on stochastic equations on a single group that was originally motivated by Tsirelson's example of a stochastic differential equation that has a unique solution in law but no strong solutions., Comment: 20 pages, revised according to referee's suggestions

Classical ecological theory predicts that environmental stochasticity increases extinction risk by reducing the average per-capita growth rate of populations. To understand the interactive effects of environmental stochasticity, spatial heterogeneity, and dispersal on population growth, we study the following model for population abundances in $n$ patches: the conditional law of $X_{t+dt}$ given $X_t=x$ is such that when $dt$ is small the conditional mean of $X_{t+dt}^i-X_t^i$ is approximately $[x^i\mu_i+\sum_j(x^j D_{ji}-x^i D_{ij})]dt$, where $X_t^i$ and $\mu_i$ are the abundance and per capita growth rate in the $i$-th patch respectivly, and $D_{ij}$ is the dispersal rate from the $i$-th to the $j$-th patch, and the conditional covariance of $X_{t+dt}^i-X_t^i$ and $X_{t+dt}^j-X_t^j$ is approximately $x^i x^j \sigma_{ij}dt$. We show for such a spatially extended population that if $S_t=(X_t^1+...+X_t^n)$ is the total population abundance, then $Y_t=X_t/S_t$, the vector of patch proportions, converges in law to a random vector $Y_\infty$ as $t\to\infty$, and the stochastic growth rate $\lim_{t\to\infty}t^{-1}\log S_t$ equals the space-time average per-capita growth rate $\sum_i\mu_i\E[Y_\infty^i]$ experienced by the population minus half of the space-time average temporal variation $\E[\sum_{i,j}\sigma_{ij}Y_\infty^i Y_\infty^j]$ experienced by the population. We derive analytic results for the law of $Y_\infty$, find which choice of the dispersal mechanism $D$ produces an optimal stochastic growth rate for a freely dispersing population, and investigate the effect on the stochastic growth rate of constraints on dispersal rates. Our results provide fundamental insights into "ideal free" movement in the face of uncertainty, the persistence of coupled sink populations, the evolution of dispersal rates, and the single large or several small (SLOSS) debate in conservation biology., Comment: 47 pages, 4 figures

Recent whole genome polymerase binding assays have shown that a large proportion of unexpressed genes have pre-assembled RNA pol II transcription initiation complex stably bound to their promoters. Some such promoter proximally paused genes are regulated at transcription elongation rather than at initiation; it has been proposed that this difference allows these genes to both express faster and achieve more synchronous expression across populations of cells, thus overcoming molecular "noise" arising from low copy number factors. It has been established experimentally that genes which are regulated at elongation tend to express faster and more synchronously; however, it has not been shown directly whether or not it is the change in the regulated step {\em per se} that causes this increase in speed and synchrony. We investigate this question by proposing and analyzing a continuous-time Markov chain model of polymerase complex assembly regulated at one of two steps: initial polymerase association with DNA, or release from a paused, transcribing state. Our analysis demonstrates that, over a wide range of physical parameters, increased speed and synchrony are functional consequences of elongation control. Further, we make new predictions about the effect of elongation regulation on the consistent control of total transcript number between cells, and identify which elements in the transcription induction pathway are most sensitive to molecular noise and thus may be most evolutionarily constrained. Our methods produce symbolic expressions for quantities of interest with reasonable computational effort and can be used to explore the interplay between interaction topology and molecular noise in a broader class of biochemical networks. We provide general-purpose code implementing these methods., Comment: 21 pages, 6 figures; to be published in PLoS Computational Biology

It is possible to represent each of a number of Markov chains as an evolving sequence of connected subsets of a directed acyclic graph that grow in the following way: initially, all vertices of the graph are unoccupied, particles are fed in one-by-one at a distinguished source vertex, successive particles proceed along directed edges according to an appropriate stochastic mechanism, and each particle comes to rest once it encounters an unoccupied vertex. Examples include the binary and digital search tree processes, the random recursive tree process and generalizations of it arising from nested instances of Pitman's two-parameter Chinese restaurant process, tree-growth models associated with Mallows' phi model of random permutations and with Schuetzenberger's non-commutative q-binomial theorem, and a construction due to Luczak and Winkler that grows uniform random binary trees in a Markovian manner. We introduce a framework that encompasses such Markov chains, and we characterize their asymptotic behavior by analyzing in detail their Doob-Martin compactifications, Poisson boundaries and tail sigma-fields., Comment: 62 pages, 8 figures, revised to address referee's comments