In designing a network to link n points in a square of area n, we might be guided by the following two desiderata. First, the total network length should not be much greater than the length of the shortest network connecting all points. Second, the average route length (taken over source-destination pairs) should not be much greater than the average straight-line distance. How small can we make these two excesses? Speaking loosely, for a nondegenerate configuration, the total network length must be at least of order n and the average straight-line distance must be at least of order n1/2, so it seems implausible that a single network might exist in which the excess over the first minimum is o(n) and the excess over the second minimum is o(n1/2). But in fact we can do better: for an arbitrary configuration, we can construct a network where the first excess is o(n) and the second excess is almost as small as O(log n). The construction is conceptually simple and uses stochastic methods: over the minimum-length connected network (Steiner tree) superimpose a sparse stationary and isotropic Poisson line process. Together with a few additions (required for technical reasons), the mean values of the excess for the resulting random network satisfy the above asymptotics; hence, a standard application of the probabilistic method guarantees the existence of deterministic networks as required (speaking constructively, such networks can be constructed using simple rejection sampling). The key ingredient is a new result about the Poisson line process. Consider two points a distance r apart, and delete from the line process all lines which separate these two points. The resulting pattern of lines partitions the plane into cells; the cell containing the two points has mean boundary length approximately equal to 2r + constant(log r). Turning to lower bounds, consider a sequence of networks in satisfying a weak equidistribution assumption. We show that if the first excess is O(n) then the second excess cannot be

Let D be the punctured unit disk. It is easy to see that no pair x, y in D can cover D in the sense that D cannot be contained in the union of the unit disks centred at x and y. With this fact in mind, let Vn = {X1, X2, …, Xn}, where X1, X2, … are random points sampled independently from a uniform distribution on D. We prove that, with asymptotic probability 1, there exist two points in Vn that cover all of Vn.

We discuss the determination of the mean normal measure of a stationary random set Z ⊂ ℝd by taking measurements at the intersections of Z with k-dimensional planes. We show that mean normal measures of sections with vertical planes determine the mean normal measure of Z if k ≥ 3 or if k = 2 and an additional mild assumption holds. The mean normal measures of finitely many flat sections are not sufficient for this purpose. On the other hand, a discrete mean normal measure can be verified (i.e. an a priori guess can be confirmed or discarded) using mean normal measures of intersections with m suitably chosen planes when m ≥ ⌊d / k⌋ + 1. This even holds for almost all m-tuples of k-dimensional planes are viable for verification. A consistent estimator for the mean normal measure of Z, based on stereological measurements in vertical sections, is also presented.

A random tessellation of ℝd is said to be homogeneous if its distribution is invariant under all shifts of ℝd. The iteration of homogeneous random tessellations is described in a new manner that makes it evident that the resulting random tessellation is homogeneous again. Furthermore, a tessellation-valued process is constructed, the random states of which are homogeneous random tessellations stable under iteration (STIT). It can be interpreted as a process of subsequent division of cells.

Consider an infinite-source marked Poisson process to model end user inputs to a data network. At Poisson times, connections are initated. The connection is characterized by a triple (F, L, R) denoting the total quantity of transmitted data in a connection, the length or duration of the connection, and the transmission rate; the three quantities are related by F = LR. How critical is the dependence structure of the mark for network characteristics such as burstiness, distribution tails of cumulative input, and long-range dependence properties of traffic measured in consecutive time slots? In a previous publication (D'Auria and Resnick (2006)) we assumed that F and R were independent. Here we assume that L and R are independent. The change in dependence assumptions means that the model properties change dramatically: tails of cumulative input per time slot are dramatically heavier, traffic cannot be approximated by a Gaussian distribution, and the decay of dependence cannot be measured in the traditional way using correlation functions. Different network applications are likely to have different mark dependence structure. We argue that the present independence assumption on L and R is likely to be appropriate for network applications such as streaming media or peer-to-peer networks. Our conclusion is that it is desirable to separate network traffic by application and to model each application with its own appropriate dependence structure.

We consider decay properties including the decay parameter, invariant measures, invariant vectors, and quasistationary distributions of a Markovian bulk-arriving queue that stops immediately after hitting the zero state. Investigating such behavior is crucial in realizing the busy period and some other related properties of Markovian bulk-arriving queues. The exact value of the decay parameter λC is obtained and expressed explicitly. The invariant measures, invariant vectors, and quasistationary distributions are then presented. We show that there exists a family of invariant measures indexed by λ ∈ [0, λC]. We then show that, under some conditions, there exists a family of quasistationary distributions, also indexed by λ ∈ [0, λC]. The generating functions of these invariant measures and quasistationary distributions are presented. We further show that a stopped Markovian bulk-arriving queue is always λC-transient and some deep properties are revealed. The clear geometric interpretation of the decay parameter is explained. A few examples are then provided to illustrate the results obtained in this paper.

This paper presents new Gaussian approximations for the cumulative distribution function P(Aλ ≤ s) of a Poisson random variable Aλ with mean λ. Using an integral transformation, we first bring the Poisson distribution into quasi-Gaussian form, which permits evaluation in terms of the normal distribution function Φ. The quasi-Gaussian form contains an implicitly defined function y, which is closely related to the Lambert W-function. A detailed analysis of y leads to a powerful asymptotic expansion and sharp bounds on P(Aλ ≤ s). The results for P(Aλ ≤ s) differ from most classical results related to the central limit theorem in that the leading term Φ(β), with is replaced by Φ(α), where α is a simple function of s that converges to β as s tends to ∞. Changing β into α turns out to increase precision for small and moderately large values of s. The results for P(Aλ ≤ s) lead to similar results related to the Erlang B formula. The asymptotic expansion for Erlang's B is shown to give rise to accurate approximations; the obtained bounds seem to be the sharpest in the literature thus far.

We prove that the Heston volatility is Malliavin differentiable under the classical Novikov condition and give an explicit expression for the derivative. This result guarantees the applicability of Malliavin calculus in the framework of the Heston stochastic volatility model. Furthermore, we derive conditions on the parameters which assure the existence of the second Malliavin derivative of the Heston volatility. This allows us to apply recent results of Alòs (2006) in order to derive approximate option pricing formulae in the context of the Heston model. Numerical results are given.

This paper revisits a general optimal stopping problem that often appears as a special case in some finance applications. The problem is essentially of the same form as the investment-timing problem of McDonald and Siegel (1986) in which the underlying processes are two correlated geometric Brownian motions (GBMs) with drifts less than the discount rate. By contrast, we attempt to analyze the underlying optimal stopping problem to its full generality without imposing any restriction on the drifts of the GBMs. By extending the first passage time approach of Xia and Zhou (2007) to the current context, we manage to obtain a complete and explicit characterization of the solution to the problem on all possible drift domains. Our analysis leads to a new and interesting observation that the underlying optimal stopping problem admits a two-sided optimal continuation region on some certain parameter domains.

In this paper we investigate the ‘local’ properties of a random mapping model, TnD̂, which maps the set {1, 2, …, n} into itself. The random mapping TnD̂, which was introduced in a companion paper (Hansen and Jaworski (2008)), is constructed using a collection of exchangeable random variables D̂1, …, D̂n which satisfy In the random digraph, GnD̂, which represents the mapping TnD̂, the in-degree sequence for the vertices is given by the variables D̂1, D̂2, …, D̂n, and, in some sense, GnD̂ can be viewed as an analogue of the general independent degree models from random graph theory. By local properties we mean the distributions of random mapping characteristics related to a given vertex v of GnD̂ - for example, the numbers of predecessors and successors of v in GnD̂. We show that the distribution of several variables associated with the local structure of GnD̂ can be expressed in terms of expectations of simple functions of D̂1, D̂2, …, D̂n. We also consider two special examples of TnD̂ which correspond to random mappings with preferential and anti-preferential attachment, and determine, for these examples, exact and asymptotic distributions for the local structure variables considered in this paper. These distributions are also of independent interest.

Let S0 := 0 and Sk := ξ1 + ··· + ξk for k ∈ ℕ := {1, 2, …}, where {ξk : k ∈ ℕ} are independent copies of a random variable ξ with values in ℕ and distribution pk := P{ξ = k}, k ∈ ℕ. We interpret the random walk {Sk : k = 0, 1, 2, …} as a particle jumping to the right through integer positions. Fix n ∈ ℕ and modify the process by requiring that the particle is bumped back to its current state each time a jump would bring the particle to a state larger than or equal to n. This constraint defines an increasing Markov chain {Rk(n) : k = 0, 1, 2, …} which never reaches the state n. We call this process a random walk with barrier n. Let Mn denote the number of jumps of the random walk with barrier n. This paper focuses on the asymptotics of Mn as n tends to ∞. A key observation is that, under p1 > 0, {Mn : n ∈ ℕ} satisfies the distributional recursion M1 = 0 and for n = 2, 3, …, where In is independent of M2, …, Mn−1 with distribution P{In = k} = pk / (p1 + ··· + pn−1), k ∈ {1, …, n − 1}. Depending on the tail behavior of the distribution of ξ, several scalings for Mn and corresponding limiting distributions come into play, including stable distributions and distributions of exponential integrals of subordinators. The methods used in this paper are mainly probabilistic. The key tool is to compare (couple) the number of jumps, Mn, with the first time, Nn, when the unrestricted random walk {Sk : k = 0, 1, …} reaches a state larger than or equal to n. The results are applied to derive the asymptotics of the number of collision events (that take place until there is just a single block) for β(a, b)-coalescent processes with parameters 0 < a < 2 and b = 1.

Inference of evolutionary trees and rates from biological sequences is commonly performed using continuous-time Markov models of character change. The Markov process evolves along an unknown tree while observations arise only from the tips of the tree. Rate heterogeneity is present in most real data sets and is accounted for by the use of flexible mixture models where each site is allowed its own rate. Very little has been rigorously established concerning the identifiability of the models currently in common use in data analysis, although nonidentifiability was proven for a semiparametric model and an incorrect proof of identifiability was published for a general parametric model (GTR + Γ + I). Here we prove that one of the most widely used models (GTR + Γ) is identifiable for generic parameters, and for all parameter choices in the case of four-state (DNA) models. This is the first proof of identifiability of a phylogenetic model with a continuous distribution of rates.

We consider a branching particle system where an individual particle gives birth to a random number of offspring at the place where it dies. The probability distribution of the number of offspring is given by pk, k = 2, 3, …. The corresponding branching process is related to the semilinear partial differential equation for x ∈ ℝd, where A is the infinitesimal generator of a multiplicative semigroup and the pks, k = 2, 3, …, are nonnegative functions such that We obtain sufficient conditions for the existence of global positive solutions to semilinear equations of this form. Our results extend previous work by Nagasawa and Sirao (1969) and others.

We describe and implement a novel methodology for Monte Carlo simulation of one-dimensional killed diffusions. The proposed estimators represent an unbiased and efficient alternative to current Monte Carlo estimators based on discretization methods for the cases when the finite-dimensional distributions of the process are unknown. For barrier option pricing in finance, we design a suitable Monte Carlo algorithm both for the single barrier case and the double barrier case. Results from numerical investigations are in excellent agreement with the theoretical predictions.