The coalescent point process of multi-type branching trees

We define a multi-type coalescent point process of a general branching process with countably many types. This multi-type coalescent fully describes the genealogy of the (quasi-stationary) standing population providing types along ancestral lineages of all individuals in the standing population. We show that the coalescent process is a functional of a certain Markov chain defined by the planar embedding of the multi-type branching process.     

A probabilistic approach to the leader problem in random graphs

We study the fixation time of the identity of the leader, that is, the most massive component, in the general setting of Aldous's multiplicative coalescent, which in an asymptotic sense describes the evolution of the component sizes of a wide array of near‐critical coalescent processes, including the classical Erd?s‐Rényi process. We show tightness of the fixation time in the “Brownian” regime, explicitly determining the median value of the fixation time to within an optimal O(1) window. This generalizes ?uczak's result for the Erd?s‐Rényi random graph using completely different techniques. In the heavy‐tailed case, in which the limit of the component sizes can be encoded using a thinned pure‐jump Lévy process, we prove that only one‐sided tightness holds. This shows a genuine difference in the possible behavior in the two regimes.     

Non‐homogeneous infinitely many sites discrete‐time model with exact coalescent

Kingman's coalescent is among the most fertile concepts in mathematical population genetics. However, it only approximates the exact coalescent process associated with the Wright–Fisher model, in which the ancestry of a sample does not have to be a binary tree. The distinction between the approximate and exact coalescent becomes important when population size is small and time has to be measured in discrete units (generations). In the present paper, we explore the exact coalescent, with mutations following the infinitely many sites model. The methods used involve random point processes and generating functionals. This allows obtaining joint distributions of segregating sites in arbitrary intervals or collections of intervals, and generally in arbitrary Borel subsets of two or more chromosomes. Using this framework it is possible to find the moments of the numbers of segregating sites on pairs of chromosomes, as well as the moments of the average of the number of pairwise differences, in the form that is more general than usually. In addition, we demonstrate limit properties of the first two moments under a range of demographic scenarios, including different patterns of population growth. This latter part complements results obtained earlier for Kingman's coalescent. Finally, we discuss various applications, including the analysis of fluctuation experiments, from which mutation rates of biological cells can be inferred. Copyright © 2009 John Wiley & Sons, Ltd.     

Service differentiation through selective lateral transshipments

We consider a multi-item spare parts problem with multiple warehouses and two customer classes, where lateral transshipments are used as a differentiation tool. Specifically, premium requests that cannot be met from stock at their preferred warehouse may be satisfied from stock at other warehouses (so-called lateral transshipments). We first derive approximations for the mean waiting time per class in a single-item model with selective lateral transshipments. Next, we embed our method in a multi-item model minimizing the holding costs and costs of lateral and emergency shipments from upstream locations in the network. Compared to the option of using only selective emergency shipments for differentiation, the addition of selective lateral transshipments can lead to significant further cost savings (14% on average).     

ALOHA networks: a game-theoretic approach

In this paper we consider a wireless network consisting of various nodes, where transmissions are regulated by the slotted ALOHA protocol. Nodes using the protocol behave autonomously, and decide at random whether to transmit in a particular time slot. Simultaneous transmissions by multiple nodes cause collisions, rendering the transmissions useless. Nodes can avoid collisions by cooperating, for example by exchanging control messages to coordinate their transmissions. We measure the network performance by the long-term average fraction of time slots in which a successful transmission takes place, and we are interested in how to allocate the performance gains obtained from cooperation among the nodes. To this end we define and analyze a cooperative ALOHA game. We show that this type of game is convex and we consider three solution concepts: the core, the Shapley value, and the compromise value. Furthermore, we develop a set of weighted gain splitting (WGS) allocation rules, and show that this set coincides with the core of the game. These WGS allocation rules can be used to provide an alternative characterization of the Shapley value. Finally, we analyze the sensitivity of the cooperative solution concepts with respect to changes in the wireless network.     

On the quantity and quality of single nucleotide polymorphisms in the human genome

Single nucleotide polymorphisms (SNPs) are useful markers for locating genes since they occur throughout the human genome and thousands can be scored at once using DNA microarrays. Here, we use branching processes and coalescent theory to show that if one uses Kruglyak's (Nature Gen. 12 (1999) 139–144) model of the growth of the human population and one assumes an average mutation rate of 1×10⁻⁸ per nucleotide per generation then there are about 5.7 million SNP's in the human genome, or one every 526 base pairs. We also obtain results for the number of SNPs that will be found in samples of sizes n⩾2 to gain insight into the number that will be found by various experimental procedures.     

Analysis of an open tandem queueing network with population constraint and constant service times 1

We consider an open tandem queueing network with population constraint and constant service times. The total number of customers that may be present in the network can not exceed a given value K. Customers arriving at the queueing network when there are more than K customers are forced to wait in an external queue. The arrival process to the queueing network is assumed to be arbitrary. We show that this queueing network can be transformed into a simple network involving only two nodes. Using this simple network, we obtain an upper and lower bound on the mean waiting time. These bounds can be easily calculated. Validations against simulation data establish the tightness of these bounds.     

Splitting trees with neutral Poissonian mutations I: Small families

We consider a neutral dynamical model of biological diversity, where individuals live and reproduce independently. They have i.i.d. lifetime durations (which are not necessarily exponentially distributed) and give birth (singly) at constant rate b. Such a genealogical tree is usually called a splitting tree [9], and the population counting process (N_t;t≥0) is a homogeneous, binary Crump-Mode-Jagers process.We assume that individuals independently experience mutations at constant rate θ during their lifetimes, under the infinite-alleles assumption: each mutation instantaneously confers a brand new type, called an allele, to its carrier. We are interested in the allele frequency spectrum at time t, i.e., the number A(t) of distinct alleles represented in the population at time t, and more specifically, the numbers A(k,t) of alleles represented by k individuals at time t, k=1,2,…,N_t.We mainly use two classes of tools: coalescent point processes, as defined in [15], and branching processes counted by random characteristics, as defined in [11] and [13]. We provide explicit formulae for the expectation of A(k,t) conditional on population size in a coalescent point process, which apply to the special case of splitting trees. We separately derive the a.s. limits of A(k,t)/N_t and of A(t)/N_t thanks to random characteristics, in the same vein as in [19].Last, we separately compute the expected homozygosity by applying a method introduced in [14], characterizing the dynamics of the tree distribution as the origination time of the tree moves back in time, in the spirit of backward Kolmogorov equations.     

The reversibility and an SPDE for the generalized Fleming–Viot processes with mutation

The (Ξ,A)$(\Xi ,A)$-Fleming–Viot process with mutation is a probability-measure-valued process whose moment dual is similar to that of the classical Fleming–Viot process except that Kingman’s coalescent is replaced by the Ξ$\Xi$-coalescent, the coalescent with simultaneous multiple collisions. We first prove the existence of such a process for general mutation generator A$A$. We then investigate its reversibility. We also study both the weak and strong uniqueness of the solution to the associated stochastic partial differential equation.     

Piecewise Smooth Dynamical Systems Theory: The Case of the Missing Boundary Equilibrium Bifurcations

We present two codimension-one bifurcations that occur when an equilibrium collides with a discontinuity in a piecewise smooth dynamical system. These simple cases appear to have escaped recent classifications. We present them here to highlight some of the powerful results from Filippov’s book Differential Equations with Discontinuous Righthand Sides (Kluwer, 1988). Filippov classified the so-called boundary equilibrium collisions without providing their unfolding. We show the complete unfolding here, for the first time, in the particularly interesting case of a node changing its stability as it collides with a discontinuity. We provide a prototypical model that can be used to generate all codimension-one boundary equilibrium collisions, and summarize the elements of Filippov’s work that are important in achieving a full classification.     

Approximate evaluation of multi-location inventory models with lateral transshipments and hold back levels

We consider a continuous-time, single-echelon, multi-location inventory model with Poisson demand processes. In case of a stock-out at a local warehouse, a demand can be fulfilled via a lateral transshipment (LT). Each warehouse is assigned a pre-determined sequence of other warehouses where it will request for an LT. However, a warehouse can hold its last part(s) back from such a request. This is called a hold back pooling policy, where each warehouse has hold back levels determining whether a request for an LT by another warehouse is satisfied. We are interested in the fractions of demand satisfied from stock (fill rate), via an LT, and via an emergency procedure from an external source. From these, the average costs of a policy can be determined. We present a new approximation algorithm for the evaluation of a given policy, approximating the above mentioned fractions. Whereas algorithms currently known in the literature approximate the stream of LT requests from a warehouse by a Poisson process, we use an interrupted Poisson process. This is a process that is turned alternatingly On and Off for exponentially distributed durations. This leads to the On/Off overflow algorithm. In a numerical study we show that this algorithm is significantly more accurate than the algorithm based on Poisson processes, although it requires a longer computation time. Furthermore, we show the benefits of hold back levels, and we illustrate how our algorithm can be used in a heuristic search for the setting of the hold back levels.     

The tree length of an evolving coalescent

A well-established model for the genealogy of a large population in equilibrium is Kingman??s coalescent. For the population together with its genealogy evolving in time, this gives rise to a time-stationary tree-valued process. We study the sum of the branch lengths, briefly denoted as tree length, and prove that the (suitably compensated) sequence of tree length processes converges, as the population size tends to infinity, to a limit process with càdlàg paths, infinite infinitesimal variance, and a Gumbel distribution as its equilibrium.     

On Maximizing Discrimination in Multiple Criteria Decision Making

We examine an LP/DEA-based technique for establishing an overall ranking of alternatives that are ranked on multiple criteria, which themselves are ranked. This two-stage process involves one LP in the first stage, and N LPs in the second stage to rank N alternatives. We find that the information from N + 1 LPs can be obtained by solving two LPs. In many cases, the solution of one LP, which can be done by inspection, is almost as informative as the two-stage procedure. We also indicate when the second stage would be redundant. If maximum technical discrimination between the alternatives is sought, we consider how this might be achieved by aggressive cross-evaluation via N LPs. We also show how to identify a subset of the alternatives that would be ranked in the first place under any ordering of the criteria, and thus play an important role in the evaluation procedure.     

Achieving sharp deliveries in supply chains through variance pool allocation

Variability reduction and business process synchronization are acknowledged as key to achieving sharp and timely deliveries in supply chain networks. In this paper, we develop an approach that facilitates variability reduction and business process synchronization for supply chains in a cost effective way. The approach developed is founded on an analogy between mechanical design tolerancing and supply chain lead time compression. We first present a motivating example to describe this analogy. Next, we define, using process capability indices, a new index of delivery performance called delivery sharpness which, when used with the classical performance index delivery probability, measures the accuracy as well as the precision with which products are delivered to the customers. Following this, we solve the following specific problem: how do we compute the allowable variability in lead time for individual stages of the supply chain so that specified levels of delivery sharpness and delivery probability are achieved in a cost-effective way? We call this the variance pool allocation (VPA) problem. We suggest an efficient heuristic approach for solving the VPA problem and also show that a variety of important supply chain design problems can be posed as instances of the VPA problem. One such problem, which is addressed in this paper, is the supply chain partner selection problem. We formulate and solve the VPA problem for a plastics industry supply chain and demonstrate how the solution can be used to choose the best mix of supply chain partners.     

Global divergence of spatial coalescents

We study several fundamental properties of a class of stochastic processes called spatial Λ-coalescents. In these models, a number of particles perform independent random walks on some underlying graph G. In addition, particles on the same vertex merge randomly according to a given coalescing mechanism. A remarkable property of mean-field coalescent processes is that they may come down from infinity, meaning that, starting with an infinite number of particles, only a finite number remains after any positive amount of time, almost surely. We show here however that, in the spatial setting, on any infinite and bounded-degree graph, the total number of particles will always remain infinite at all times, almost surely. Moreover, if ${G\,=\,\mathbb{Z}^d}$ , and the coalescing mechanism is Kingman’s coalescent, then starting with N particles at the origin, the total number of particles remaining is of order (log* N) ^d at any fixed positive time (where log* is the inverse tower function). At sufficiently large times the total number of particles is of order (log* N) ^d-2, when d?>?2. We provide parallel results in the recurrent case d?=?2. The spatial Beta-coalescents behave similarly, where log log N is replacing log* N.     

On the approximation of spectra of linear operators on Hilbert spaces

We present several new techniques for approximating spectra of linear operators (not necessarily bounded) on an infinite-dimensional, separable Hilbert space. Our approach is to take well-known techniques from finite-dimensional matrix analysis and show how they can be generalized to an infinite-dimensional setting to provide approximations of spectra of elements in a large class of operators. We conclude by proposing a solution to the general problem of approximating the spectrum of an arbitrary bounded operator by introducing the n-pseudospectrum and argue how that can be used as an approximation to the spectrum.     

Aggregation and heterogeneity from the nonlinear dynamic interaction of birth,maturation and spatial migration

We consider a single species structured population distributed in two identical patches connected by spatial dispersal. Assuming that the maturation time for each individual is a random variable with a gamma distribution and that the spatial dispersal rate is constant, we obtain from a hyperbolic differential equation a system of six ordinary differential equations for the matured populations and their moments. Our qualitative analysis and numerical simulations show that the nonlinear interaction of birth process, the maturation delay and the spatial dispersal can lead to a new mechanism for individual aggregation in the form of the existence of multiple stable heterogeneous equilibria, even though the spatial dispersal is assumed to be proportional to the population gradients with a constant rate.     

Sojourn times in a processor sharing queue with multiple vacations

We study an M/G/1 processor sharing queue with multiple vacations. The server only takes a vacation when the system has become empty. If he finds the system still empty upon return, he takes another vacation, and so on. Successive vacations are identically distributed, with a general distribution. When the service requirements are exponentially distributed we determine the sojourn time distribution of an arbitrary customer. We also show how the same approach can be used to determine the sojourn time distribution in an M/M/1-PS queue of a polling model, under the following constraints: the service discipline at that queue is exhaustive service, the service discipline at each of the other queues satisfies a so-called branching property, and the arrival processes at the various queues are independent Poisson processes. For a general service requirement distribution we investigate both the vacation queue and the polling model, restricting ourselves to the mean sojourn time.     

Asymptotic results for coalescent processes without proper frequencies and applications to the two-parameter Poisson–Dirichlet coalescent

The class of coalescent processes with simultaneous multiple collisions (Ξ$\Xi$-coalescents) without proper frequencies is considered. We study the asymptotic behavior of the external branch length, the total branch length and the number of mutations on the genealogical tree as the sample size n$n$ tends to infinity. The limiting random variables arising are characterized via exponential integrals of the subordinator associated with the frequency of singletons of the coalescent. The proofs are based on decompositions into external and internal branches. The asymptotics of the external branches is treated via the method of moments. The internal branches do not contribute to the limiting variables since the number _Cn$C_n$ of collisions for coalescents without proper frequencies is asymptotically negligible compared to n$n$. The results are applied to the two-parameter Poisson–Dirichlet coalescent indicating that this particular class of coalescent processes in many respects behaves approximately as the star-shaped coalescent.     

Determining supply requirement in the sales-and-operations-planning (S&OP) process under demand uncertainty: a stochastic programming formulation and a spreadsheet implementation

We show how to extend the demand-planning stage of the sales-and-operations-planning (S&OP) process with a spreadsheet implementation of a stochastic programming model that determines the supply requirement while optimally trading off risks of unmet demand, excess inventory, and inadequate liquidity in the presence of demand uncertainty. We first present the model that minimizes the weighted sum of respective conditional value-at-risk (cVaR) metrics over demand scenarios in the form of a binomial tree. The output of this model is the supply requirement to be used in the supply-planning stage of the S&OP process. Next we show how row-and-column aggregation of the model reduces its size from exponential (2 ^T ) in the number of time periods T in the planning horizon to merely square (T²). Finally, we demonstrate the tractability of this aggregated model in an Excel spreadsheet implementation with a numerical example with 26 time periods.