In this paper we study different types of planar random motions (performed with constant velocity) with three directions, defined by the vectors dj = (cos(2πj/3), sin(2πj/3)) for j = 0, 1, 2, changing at Poisson-paced times. We examine the cyclic motion (where the change of direction is deterministic), the completely uniform motion (where at each Poisson event each direction can be taken with probability ) and the symmetrically deviating case (where the particle can choose all directions except that taken before the Poisson event). For each of the above random motions we derive the explicit distribution of the position of the particle, by using an approach based on order statistics. We prove that the densities obtained are solutions of the partial differential equations governing the processes. We are also able to give the explicit distributions on the boundary and, for the case of the symmetrically deviating motion, we can write it as the distribution of a telegraph process. For the symmetrically deviating motion we use a generalization of the Bose-Einstein statistics in order to determine the distribution of the triple (N0, N1, N2) (conditional on N(t) = k, with N0 + N1 + N2 = N(t) + 1, where N(t) is the number of Poisson events in [0, t]), where Nj denotes the number of times the direction dj (j = 0, 1, 2) is taken. Possible extensions to four directions or more are briefly considered.

We investigate the limit distributions associated with cost measures in Sattolo's algorithm for generating random cyclic permutations. The number of moves made by an element turns out to be a mixture of 1 and 1 plus a geometric distribution with parameter ½, where the mixing probability is the limiting ratio of the rank of the element being moved to the size of the permutation. On the other hand, the raw distance traveled by an element to its final destination does not converge in distribution without norming. Linearly scaled, the distance converges to a mixture of a uniform and a shifted product of a pair of independent uniforms. The results are obtained via randomization as a transform, followed by derandomization as an inverse transform. The work extends analysis by Prodinger.

Consider the classical coupon-collector's problem in which items of m distinct types arrive in sequence. An arriving item is installed in system i ≥ 1 if i is the smallest index such that system i does not contain an item of the arrival's type. We study the expected number of items in system j at the moment when system 1 first contains an item of each type

This paper studies path lengths in random binary search trees under the random permutation model. It is known that the total path length, when properly normalized, converges almost surely to a nondegenerate random variable Z. The limit distribution is commonly referred to as the ‘quicksort distribution’. For the class 𝒜m of finite binary trees with at most m nodes we partition the external nodes of the binary search tree according to the largest tree that each external node belongs to. Thus, the external path length is divided into parts, each part associated with a tree in 𝒜m. We show that the vector of these path lengths, after normalization, converges almost surely to a constant vector times Z.

In this paper, we investigate sooner and later waiting time problems for patterns S0 and S1 in multistate Markov dependent trials. The probability functions and the probability generating functions of the sooner and later waiting time random variables are studied. Further, the probability generating functions of the distributions of distances between successive occurrences of S0 and between successive occurrences of S0 and S1 and of the waiting time until the rth occurrence of S0 are also given.

In this paper, we introduce a compound random mapping model which can be viewed as a generalization of the basic random mapping model considered by Ross and by Jaworski. We investigate a particular example, the Poisson compound random mapping, and compare results for this model with results known for the well-studied uniform random mapping model. We show that, although the structure of the components of the random digraph associated with a Poisson compound mapping differs from the structure of the components of the random digraph associated with the uniform model, the limiting distribution of the normalized order statistics for the sizes of the components is the same as in the uniform case, i.e. the limiting distribution is the Poisson-Dirichlet (½) distribution on the simplex {{xi} : ∑ xi ≤ 1, xi ≥ xi+1 ≥ 0 for every i ≥ 1}.

Uniform sequential tree-building aggregation of n particles is analyzed together with the effect of the avalanche that takes place when a subtree rooted at a uniformly chosen vertex is removed. For large n, the expected subtree size is found to be ≃ logn both for the tree of size n and the tree that remains after an avalanche. Repeated breakage-restoration cycles are seen to give independent avalanches which attain size k(1 ≤ k ≤ n-1) with probability (k(k+1))-1 and restored trees that are recursive.

The coupon subset collection problem is a generalization of the classical coupon collecting problem, in that rather than collecting individual coupons we obtain, at each time point, a random subset of coupons. The problem of interest is to determine the expected number of subsets needed until each coupon is contained in at least one of these subsets. We provide bounds on this number, give efficient simulation procedures for estimating it, and then apply our results to a reliability problem.

The problem of finding bounds for P(A1 ∪ ⋯ ∪ An) based on P(Ak1 ∩ ⋯ ∩ Aki) (1 ≤ k1 < ⋯ < ki ≤ n, i = 1,…,d) goes back to Boole (1854), (1868) and Bonferroni (1937). In this paper upper bounds are presented using methods in graph theory. The main theorem is a common generalization of the earlier results of Hunter, Worsley and recent results of Prékopa and the author. Algorithms are given to compute bounds. Examples for bounding values of multivariate normal distribution functions are presented.

Optical mapping is a new technique to generate restriction maps of DNA easily and quickly. DNA restriction maps can be aligned by comparing corresponding restriction fragment lengths. To relate, organize, and analyse these maps it is necessary to rapidly compare maps. The issue of the statistical significance of approximately matching maps then becomes central, as in BLAST with sequence scoring. In this paper, we study the approximation to the distribution of counts of matched regions of specified length when comparing two DNA restriction maps. Distributional results are given to enable us to compute p-values and hence to determine whether or not the two restriction maps are related. The key tool used is the Chen-Stein method of Poisson approximation. Certain open problems are described.

New bounds are found for the reliability of consecutive-k-out-of-n:F systems with equal component failure probabilities. The expressions involved are simple, thus allowing a direct use in the derivation of theoretical properties.

These bounds can also be employed in numerical computations when the value of n or k is so large that the exact calculation of the reliability is not achievable. Comparisons show that the approximation errors exhibited by these new formulas are lower than those of other widely used bounds.

Extending the cascade model for food webs, we introduce a cyclic cascade model which is a random generation model of cyclic dominance relations. Put n species as n points Q1,Q2,…, Qn on a circle. If the counterclockwise way from Qi to Qj on the circle is shorter than the clockwise way, we say Qi dominates Qj. Consider a tournament whose dominance relations are generated from the points on a circle by this rule. We show that when we take n mutually independently distributed points on the circle, the probability of getting a regular tournament of order 2r+1 as the largest regular tournament is equal to (n/(2r+1))/2n-1. This probability distribution is for the number of existing species after a sufficiently long period, assuming a Lotka-Volterra cyclic cascade model.

In a cubic multigraph certain restrictions on the paths are made to define what is called a railway. On the tracks in the railway (edges in the multigraph) an equivalence relation is defined. The number of equivalence classes induced by this relation is investigated for a random railway achieved from a random cubic multigraph, and the asymptotic distribution of this number is derived as the number of vertices tends to infinity.

We approach sphere of influence graphs (SIGs) from a probabilistic perspective. Ordinary SIGs were first introduced by Toussaint as a type of proximity graph for use in pattern recognition, computer vision and other low-level vision tasks. A random sphere of influence graph (RSIG) is constructed as follows. Consider n points uniformly and independently distributed within the unit square in d dimensions. Around each point, Xi, draw an open ball (‘sphere of influence’) with radius equal to the distance to Xi's nearest neighbour. Finally, draw an edge between two points if their spheres of influence intersect. Asymptotically exact values for the expected number of edges in a RSIG are determined for all values of d; previously, just upper and lower bounds were known for this quantity. A modification of the Azuma-Hoeffding exponential inequality is employed to exhibit the sharp concentration of the number of edges around its expected value.

Expressions for the multi-dimensional densities of Brownian excursion local time are derived by two different methods: a direct method based on Kac's formula for Brownian functionals and an indirect one based on a limit theorem for Galton–Watson trees.

A general analytic scheme for Poisson approximation to discrete distributions is studied in which the asymptotic behaviours of the generalized total variation, Fortet-Mourier (or Wasserstein), Kolmogorov and Matusita (or Hellinger) distances are explicitly characterized. Applications of this result include many number-theoretic functions and combinatorial structures. Our approach differs from most of the existing ones in the literature and is easily amended for other discrete approximations; arithmetic and combinatorial examples for Bessel approximation are also presented. A unified approach is developed for deriving uniform estimates for probability generating functions of the number of components in general decomposable combinatorial structures, with or without analytic continuation outside their circles of convergence.

We present a general recurrence model which provides a conceptual framework for well-known problems such as ascents, peaks, turning points, Bernstein's urn model, the Eggenberger–Pólya urn model and the hypergeometric distribution. Moreover, we show that the Frobenius-Harper technique, based on real roots of a generating function, can be applied to this general recurrence model (under simple conditions), and so a Berry–Esséen bound and local limit theorems can be found. This provides a simple and unified approach to asymptotic theory for diverse problems hitherto treated separately.

The study of the distribution of the distance between words in a random sequence of letters is interesting in view of application in genome sequence analysis. In this paper we give the exact distribution probability and cumulative distribution function of the distances between two successive occurrences of a given word and between the nth and the (n+m)th occurrences under three models of generation of the letters: i.i.d. with the same probability for each letter, i.i.d. with different probabilities and Markov process. The generating function and the first two moments are also given. The point of studying the distances instead of the counting process is that we get some knowledge not only about the frequency of a word but also about its longitudinal distribution in the sequence.

Generalizing the classical Banach matchbox problem, we consider the process of removing two types of ‘items’ from a ‘pile’ with selection probabilities for the type of the next item to be removed depending on the current numbers of remaining items, and thus changing sequentially. Under various conditions on the probability pn1,n2 that the next removal will take away an item of type I, given that n1 and n2 are the current numbers of items of the two types, we derive asymptotic formulas (as the initial pile size tends to infinity) for the probability that the items of type I are completely removed first and for the number of items left. In some special cases we also obtain explicit results.

We consider an allocation of n balls into N cells according to probabilities pi. Assuming that the balls are allocated successively, denote by φ(n,N) the number of such balls which go into an already occupied cell. If n = 2 the probability that two balls will occupy the same cell is equal to the so-called match probability MP = p21 + … + p2N. An upper estimate for the probability ℙ(φ(n,N) ≤ m) which depends only on n and MP is derived. Such inequalities are important for estimation of the reliability of DNA fingerprinting, a new method of crime investigation which is currently much debated.