Search

We obtain discrete mixture representations for parametric families of probability distributions on Euclidean spheres, such as the von Mises--Fisher, the Watson and the angular Gaussian families. In addition to several special results we present a general approach to isotropic distribution families that is based on density expansions in terms of special surface harmonics. We discuss the connections to stochastic processes on spheres, in particular random walks, discrete mixture representations derived from spherical diffusions, and the use of Markov representations for the mixing base to obtain representations for families of spherical distributions., Comment: Accepted for publication in "Statistical Papers"

We introduce and discuss a multivariate version of the classical median that is based on an equipartition property with respect to quarter spaces. These arise as pairwise intersections of the half-spaces associated with the coordinate hyperplanes of an orthogonal basis. We obtain results on existence, equivariance, and asymptotic normality.

With any symmetric distribution $\mu$ on the real line we may associate a parametric family of noncentral distributions as the distributions of $(X+\delta)^2$, $\delta\not=0$, where $X$ is a random variable with distribution $\mu$. The classical case arises if $\mu$ is the standard normal distribution, leading to the noncentral chi-squared distributions. It is well-known that these may be written as Poisson mixtures of the central chi-squared distributions with odd degrees of freedom. We obtain such mixture representations for the logistic distribution and for the hyperbolic secant distribution. We also derive alternative representations for chi-squared distributions and relate these to representations of the Poisson family. While such questions originated in parametric statistics they also appear in the context of the generalized second Ray-Knight theorem, which connects Gaussian processes and local times of Markov processes.

We investigate existence and properties of discrete mixture representations $P_{\theta }=\sum _{i\in E}w_{\theta }(i)\,Q_{i}$ for a given family $P_{\theta }$, $\theta \in \Theta $, of probability measures. The noncentral chi-squared distributions provide a classical example. We obtain existence results and results about geometric and statistical aspects of the problem, the latter including loss of Fisher information, Rao-Blackwellization, asymptotic efficiency and nonparametric maximum likelihood estimation of the mixing probabilities.

Author(s): Evans, SN; Grubel, R; Wakolbinger, A | Abstract: Remy's algorithm is a Markov chain that iteratively generates a sequence of random trees in such a way that the nth 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 nth 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 ℝ-tree that is rooted and binary in a suitable sense, a diffuse probability measure on the R-tree that allows us to make sense of sampling points from it, and a kernel on the 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. Two such ensembles represent the same point in the boundary if for each m the random, rooted, planar, binary trees spanned by m + 1 independent points chosen according to the respective probability measures have the same distribution. Also, the Doob-Martin boundary corresponds bijectively to the set of extreme point of the closed convex set of nonnegative harmonic functions that take the value 1 at the binary tree with 3 vertices; 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.

Let $W_{\infty}(\beta)$ be the limit of the Biggins martingale $W_n(\beta)$ associated to a supercritical branching random walk with mean number of offspring $m$. We prove a functional central limit theorem stating that as $n\to\infty$ the process $$ D_n(u):= m^{\frac 12 n} \left(W_{\infty}\left(\frac{u}{\sqrt n}\right) - W_{n}\left(\frac{u}{\sqrt n}\right) \right) $$ converges weakly, on a suitable space of analytic functions, to a Gaussian random analytic function with random variance. Using this result we prove central limit theorems for the total path length of random trees. In the setting of binary search trees, we recover a recent result of R. Neininger [Refined Quicksort Asymptotics, Rand. Struct. and Alg., to appear], but we also prove a similar theorem for uniform random recursive trees. Moreover, we replace weak convergence in Neininger's theorem by the almost sure weak (a.s.w.) convergence of probability transition kernels. In the case of binary search trees, our result states that $$ L\left\{\sqrt{\frac{n}{2\log n}} \left(EPL_{\infty} - \frac{EPL_n-2n\log n}{n}\right)\Bigg | G_{n}\right\} \to \{\omega\mapsto N_{0,1}\}, \quad \text{a.s.w.},$$ where $EPL_n$ is the external path length of a binary search tree $X_n$ with $n$ vertices, $EPL_{\infty}$ is the limit of the R\'egnier martingale, and $L(\,\cdot\, |G_n)$ denotes the conditional distribution w.r.t. the $\sigma$-algebra $G_n$ generated by $X_1,\ldots,X_n$. A.s.w. convergence is stronger than weak and even stable convergence. We prove several basic properties of the a.s.w. convergence and study a number of further examples in which the a.s.w. convergence appears naturally. These include the classical central limit theorem for Galton-Watson processes and the P\'olya urn., Comment: 34 pages, no figures

A well-studied randomized election algorithm proceeds as follows: In each round the remaining candidates each toss a coin and leave the competition if they obtain heads. Of interest is the number of rounds required and the number of winners, both related to maxima of geometric random samples, as well as the number of remaining participants as a function of the number of rounds. We introduce two related Markov chains and use ideas and methods from discrete potential theory to analyse the respective asymptotic behaviour as the initial number of participants grows. One of the tools used is the approach via the R\'enyi-Sukhatme representation of exponential order statistics, which was first used in the leader election context by Bruss and Gr\"ubel in \cite{BrGr03}.

Wir behandeln ein aktuelles Teilgebiet der probabilistischen Kombinatorik, die Verwendung von Markov-Ketten bei der Analyse von kombinatorischen Familien. Solche Ketten sind zufallige dynamische Strukturen, die beispielsweise als Output von sequentiellen Algorithmen mit zufalligem Input entstehen. Wir erklaren, wie Methoden der diskreten Potentialtheorie uber Kompaktifizierungen des Zustandsraums zu starken Grenzwertsatzen und strukturellen Ergebnissen bei zufalligen Permutationen, Zahlenpartitionen, binaren Baumen und Ulam-Harris-Baumen fuhren.

Customers arrive sequentially at times x 1 < x 2 < · · · < x n and stay for independent random times Z 1, …, Z n > 0. The Z-variables all have the same distribution Q. We are interested in situations where the data are incomplete in the sense that only the order statistics associated with the departure times x i + Z i are known, or that the only available information is the order in which the customers arrive and depart. In the former case we explore possibilities for the reconstruction of the correct matching of arrival and departure times. In the latter case we propose a test for exponentiality.

Let (X i ) i∈ℕ be a sequence of independent and identically distributed random variables with values in the set ℕ0 of nonnegative integers. Motivated by applications in enumerative combinatorics and analysis of algorithms we investigate the number of gaps and the length of the longest gap in the set {X 1,…,X n } of the first n values. We obtain necessary and sufficient conditions in terms of the tail sequence (q k ) k∈ℕ0 , q k =P(X 1≥ k), for the gaps to vanish asymptotically as n→∞: these are ∑ k=0 ∞ q k+1/q k k→∞ q k+1/q k =0 for convergence almost surely and convergence in probability, respectively. We further show that the length of the longest gap tends to ∞ in probability if q k+1/q k → 1. For the family of geometric distributions, which can be regarded as the borderline case between the light-tailed and the heavy-tailed situations and which is also of particular interest in applications, we study the distribution of the length of the longest gap, using a construction based on the Sukhatme–Rényi representation of exponential order statistics to resolve the asymptotic distributional periodicities.

Motivated by applications in enumerative combinatorics and the analysis of algorithms we investigate the number of gaps and the length of the longest gap in a discrete random sample from a general distribution. We obtain necessary and sufficient conditions on the underlying distribution for the gaps to vanish asymptotically (with probability 1, or in probability), and we study the limiting distributional behavior of these random variables in the geometric case.

We consider the problem of estimating the size of a random digital search tree on the basis of the maximal node depth observed along a specific path. We show that the maximum likelihood estimator exists and we investigate its properties. A similar problem arises in the context of approximate counting. In both cases a simple pure birth process plays a central role. We also construct confidence bounds.

Computerbasierte Methoden haben die Anwendungsbreite der Statistik enorm erweitert. Simulationstechniken erlauben neue Zugange zu komplexen Fragestellungen, die traditionell nur unter sehr restriktiven Annahmen moglich waren. Implementierung und Anwendung von rechenintensiven Algorithmen bieten neue Moglichkeiten, das fur die Inferenzstatistik zentrale Konzept der Stichprobenverteilung transparenter und besser greifbar zu machen. Der Aufsatz diskutiert didaktischen Nutzen und mathematische Aspekte des Bootstrap-Verfahrens. Wir illustrieren das Verfahren mit einem Beispiel aus der Publikationsgeschichte der Semesterberichte.

Wir betrachten einige klassische Such- und Sortieralgorithmen bei zufalligem Input. Zahlt Xn, wie viele Operationen eines bestimmten Typs bei einem Datensatz vom Umfang n benotigt werden, so geht es bei der average-case Analyse um den Erwartungswert EXn dieser Zufallsgrose und insbesondere um das Verhalten von EXn mit n→∞. Wir stellen verschiedene Methoden vor, mit denen in vielen solchen Fallen das asymptotische Verhalten der gesamten Verteilung von Xn bestimmt werden kann. Aussagen uber die Verteilungskonvergenz lassen sich beispielsweise verwenden, um die Wahrscheinlichkeit exzessiv langer Laufzeiten zu approximieren.

We discuss two Monte Carlo algorithms for finding the global maximum of a simple random walk with negative drift. This problem can be used to connect the analysis of random input Monte Carlo algorithms with ideas and principles from mathematical statistics.

Multivariate stochastic processes with Poisson marginals are of interest in insurance and finance; they can be used to model the joint behaviour of several claim arrival processes, for example. We discuss various methods for the construction of such models, with particular emphasis on the use of copulas. An important class of multivariate counting processes with Poisson marginals arises if the events of a background Poisson process with constant intensity are moved forward in time by a random amount and possibly deleted; here we think of the events of the background process as triggering later claims in different categories. We discuss structural aspects of these models, their dependence properties together with stochastic order aspects, and also some related computational issues. Various actuarial applications are indicated.

We generalize a theorem due to Keilson on the approximate exponentiality of waiting times for rare events in regenerative processes. We use the result to investigate the limit distribution for a family of first entrance times in a sequence of Ehrenfest urn models. As a second application, we consider approximate pattern matching, a problem arising in molecular biology and other areas.

Given a sample from a discrete compound Poisson distribution, we consider variants of plug-in and likelihood estimators for the corresponding base distribution. These proceed recursively with an intermediate truncation step. We discuss the asymptotic behaviour of the estimators and give some numerical examples. Both procedures compare favourably with the straightforward and the naively projected plug-in estimator that we introduced in Buchmann and Grubel (2003,The Annals of Statistics,31, 1054–1074).

We generalize Banach's matchbox problem: demands of random size are made on one of two containers, both initially with content t, where the container is selected at random in the successive steps. Let Z t be the content of the other container at the moment when the selected container is found to be insufficient. We obtain the asymptotic distribution of Z t as t → ∞ under quite general conditions. The case of exponentially distributed demands is considered in more detail.

The successive discrete structures generated by a sequential algorithm from random input constitute a Markov chain that may exhibit long term dependence on its first few input values. Using examples from random graph theory and search algorithms we show how such persistence of randomness can be detected and quantified with techniques from discrete potential theory. We also show that this approach can be used to obtain strong limit theorems in cases where previously only distributional convergence was known., Comment: Official journal file

We consider random binary trees that appear as the output of certain standard algorithms for sorting and searching if the input is random. We introduce the subtree size metric on search trees and show that the resulting metric spaces converge with probability 1. This is then used to obtain almost sure convergence for various tree functionals, together with representations of the respective limit random variables as functions of the limit tree., Published in at http://dx.doi.org/10.1214/13-AAP948 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We consider the sum S d of record values in a sequence of independent random variables that are uniformly distributed on 1,…,d. This sum can be interpreted as the total amount of time spent in record lifetimes in the standard renewal theoretic setup. We investigate the distributional limit of S d and some related quantities as d→∞. Some explicit values are given for d=6, a case that can be interpreted as a simple game of chance.

The standard methods for the calculation of total claim size distributions and ruin probabilities, Panjer recursion and algorithms based on transforms, both apply to lattice-type distributions only and therefore require an initial discretization step if continuous distribution functions are of interest. We discuss the associated discretization error and show that it can often be reduced substantially by an extrapolation technique.

For a distribution μ on the unit interval we define the associated perpetuity Ψ(μ) as the distribution of 1+X1+X1X2+X1X2X3+…, where (Xn)n∈N is a sequence of independent random variables with distribution μ. Such quantities arise in insurance mathematics and in many other areas. We prove the differentiability of the perpetuity functionalψ with respect to integral and supremum norms. These results are then used to investigate the statistical properties of empirical perpetuities, including the behaviour of bootstrap confidence regions.

We consider stochastic equations of the form X = d W1X + W2X′,where (W1, W2), X and X′ are independent, '=d' denotes equality indistribution, EW1 + EW2 = 1 and X =d X′. We discuss existence,uniqueness and stability of the solutions, using contraction arguments andan approach based on moments. The case of {0, 1}-valued W1 and constant W2leads to a characterization of exponential distributions.

Let ?(u) be the probability of eventual ruin in the classical Sparre Andersen model of risk theory if the initial risk reserve is u. For a large class of such models ?(u) behaves asymptotically like a multiple of exp (–Ru) where R is the adjustment coefficient; R depends on the premium income rate, the claim size distribution and the distribution of the time between claim arrivals. Estimation of R has been considered by many authors. In the present paper we deal with confidence bounds for R. A variety of methods is used, including jackknife estimation of asymptotic variances and the bootstrap. We show that, under certain assumptions, these procedures result in interval estimates that have asymptotically the correct coverage probabilities. We also give the results of a simulation study that compares the different techniques in some particular cases.

We investigate the behaviour of P(R ≧ r) and P(R ≦ −r) as r → ∞for the random variable where is an independent, identically distributed sequence with P(− 1 ≦ M ≦ 1) = 1. Random variables of this type appear in insurance mathematics, as solutions of stochastic difference equations, in the analysis of probabilistic algorithms and elsewhere. Exponential and Poissonian tail behaviour can arise.

De Studentized bootstrap methode in de accountantscontrole

We investigate the asymptotic behaviour of the distribution of the number of comparisons needed by a quicksort-style selection algorithm that finds the lth smallest in a set of n numbers. Letting n tend to infinity and considering the values l = 1, ···,n simultaneously we obtain a limiting stochastic process. This process admits various interpretations: it arises in connection with a representation of real numbers induced by nested random partitions and also in connection with expected path lengths of a random walk in a random environment on a binary tree.

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., 62 pages, 8 figures, revised to address referee's comments

Given a sequence of independent random variables with densityf we estimate quantities θ of the form θ=∫ φ(f(x))dx, φ a known function, by inserting histograms and kernel density estimators for the unknownf. We obtain conditions for consistency and asymptotic normality and discuss the choice of cell size and bandwidth.

Transform methods, together with the fast Fourier transform algorithm, can be used to compute various quantities of interest in risk theory and insurance mathematics. These include the total claim size distribution at a fixed time, the mean and variance of the claim size process as a function of time in the Sparre-Andersen model, and the probability of ruin. The associated discretization error can be reduced by applying Richardson's deferred approach to the limit. A theorem is given that puts the use of this technique on a mathematical basis in the context of compound distributions.

For random trees T generated by the binary search tree algorithm from uniformly distributed input we consider the subtree size profile, which maps k ∈ ℕ to the number of nodes in T that root a subtree of size k. Complementing earlier work by Devroye, by Feng, Mahmoud and Panholzer, and by Fuchs, we obtain results for the range of small k-values and the range of k-values proportional to the size n of T. In both cases emphasis is on the process view, i.e., the joint distributions for several k-values. We also show that the dynamics of the tree sequence lead to a qualitative difference between the asymptotic behaviour of the lower and the upper end of the profile.

A zero-one sequence describes a path through a rooted directed binary tree $T$; it also encodes a real number in $[0,1]$. We regard the level of the external node of $T$ along the path as a function on the unit interval, the silhouette of $T$. We investigate the asymptotic behavior of the resulting stochastic processes for sequences of trees that are generated by the binary search tree algorithm., Published in at http://dx.doi.org/10.1214/08-AAP593 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Given two independent samples of non-negative random variables with unknown distribution functions $F$ and $G$, respectively, we introduce and discuss two tests for the hypothesis that $F$ is less than or equal to $G$ in increasing convex order. The test statistics are based on the empirical stop-loss transform, critical values are obtained by a bootstrap procedure. It turns out that for the resampling a size switching is necessary. We show that the resulting tests are consistent against all alternatives and that they are asymptotically of the given size $\alpha$. A specific feature of the problem is the behavior of the tests `inside' the hypothesis, where $F\not=G$. We also investigate and compare this aspect for the two tests., Comment: Published in at http://dx.doi.org/10.3150/08-BEJ151 the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

The classical models in risk theory consider a single type of claim. In the insurance business, however, several business lines with separate claim arrival processes appear naturally, and the individual claim processes may not be independent. We introduce a new class of models for such situations, where the underlying counting process is a multivariate continuous-time Markov chain of pure-birth type and the dependency of the components arises from the fact that the birth rate for a specific claim type may depend on the number of claims in the other component processes. Under certain conditions, we obtain a fluid limit, i.e. a functional law of large numbers for these processes. We also investigate the consequences of such results for questions of interest in insurance applications. Several specific subclasses of the general model are discussed in detail and the Cramér asymptotics of the ruin probabilities are derived in particular cases.

We obtain a strong law of large numbers and a functional central limit theorem, as $t\to\infty$, for the number of records up to time $t$ and the Lebesgue measure (length) of the subset of the time interval $[0,t]$ during which the Poisson process is in a record lifetime., Comment: To appear in a Special Volume of Stochastics: An International Journal of Probability and Stochastic Processes (http://www.informaworld.com/openurl?genre=journal%26issn=1744-2508) edited by N.H. Bingham and I.V. Evstigneev which will be reprinted as Volume 57 of the IMS Lecture Notes Monograph Series (http://imstat.org/publications/lecnotes.htm)

We investigate the distribution of the depth of a node containing a specific key or, equivalently, the number of steps needed to retrieve an item stored in a randomly grown binary search tree. Using a representation in terms of mixed and compounded standard distributions, we derive approximations by Poisson and mixed Poisson distributions; these lead to asymptotic normality results. We are particularly interested in the influence of the key value on the distribution of the node depth. Methodologically our message is that the explicit representation may provide additional insight if compared to the standard approach that is based on the recursive structure of the trees. Further, in order to exhibit the influence of the key on the distributional asymptotics, a suitable choice of distance of probability distributions is important. Our results are also applicable in connection with the number of recursions needed in Hoare's [Comm. ACM 4 (1961) 321-322] selection algorithm Find., Published at http://dx.doi.org/10.1214/105051604000000611 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)