Consider a sequence of exchangeable or independent binary trials ordered on a line or on a circle. The statistics denoting the number of times an F-S string of length (at least) k1 + k2, that is, (at least) k1 failures followed by (at least) k2 successes in n such trials, are studied. The associated waiting time for the rth occurrence of an F-S string of length (at least) k1 + k2 in linearly ordered trials is also examined. Exact formulae, lower/upper bounds and approximations are derived for their distributions. Mean values and variances of the number of occurrences of F-S strings are given in exact formulae too. Particular exchangeable and independent sequences of binary random variables, used in applied research, combined with numerical examples clarify further the theoretical results.

Let Kn denote the number of types of a sample of size n taken from an exchangeable coalescent process (Ξ-coalescent) with mutation. A distributional recursion for the sequence (Kn)n∈ℕ is derived. If the coalescent does not have proper frequencies, i.e. if the characterizing measure Ξ on the infinite simplex Δ does not have mass at 0 and satisfies ∫Δ ∣x∣Ξ(dx)/(x,x)<∞, where ∣x∣:=∑i=1∞xi and (x,x)≔∑i=1∞xi2 for x=(x1,x2,…)∈Δ, then Kn/n converges weakly as n→∞ to a limiting variable K that is characterized by an exponential integral of the subordinator associated with the coalescent process. For so-called simple measures Ξ satisfying ∫ΔΞ(d x)/(x,x)<∞, we characterize the distribution of K via a fixed-point equation.

We will propose an alternative condition for stochastic domination. This condition differs in an essential way from the strong likelihood ratio property. We also show an example which satisfies the new condition, but does not satisfy the strong likelihood ratio property.

The lying oracle problem is a problem of finding the optimal strategies in a two-person game where an oracle predicts the outcomes of coin flips and a player bets on the outcomes. The oracle announces whether the coin will land heads or tails, but may at times lie. We analyze the variant of the game which uses a biased coin, where the probability p that the coin lands heads is common knowledge. We determine optimal strategies for both the oracle and player, and we give an explicit expression for the expected payoff to the player when the coin is flipped n times and the oracle may lie at most k times.

The probability that two randomly selected phylogenetic trees of the same size are isomorphic is found to be asymptotic to a decreasing exponential modulated by a polynomial factor. The number of symmetrical nodes in a random phylogenetic tree of large size obeys a limiting Gaussian distribution, in the sense of both central and local limits. The probability that two random phylogenetic trees have the same number of symmetries asymptotically obeys an inverse square-root law. Precise estimates for these problems are obtained by methods of analytic combinatorics, involving bivariate generating functions, singularity analysis, and quasi-powers approximations.

In an infinite sequence of independent Bernoulli trials with success probabilities pk=a/(a+b +k-1) for k=1,2,3,…, let Nr be the number of r≥2 consecutive successes. Expressions for the first two moments of Nr are derived. Asymptotics of the probability of no occurrence of r consecutive successes for large r are obtained. Using an embedding in a marked Poisson process, it is indicated how the distribution of Nr can be calculated for small r.

Let (Xi)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 {X1,…,Xn} of the first n values. We obtain necessary and sufficient conditions in terms of the tail sequence (qk)k∈ℕ0, qk=P(X1≥ k), for the gaps to vanish asymptotically as n→∞: these are ∑k=0∞qk+1/qk <∞ and limk→∞qk+1/qk=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 qk+1/qk→ 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.

In this work we give precise asymptotic expressions for the probability of the existence of fixed-size components at the threshold of connectivity for random geometric graphs.

In this paper we consider a class of quasi-birth-and-death processes for which explicit solutions can be obtained for the rate matrix R and the associated matrix G. The probabilistic interpretations of these matrices allow us to describe their elements in terms of paths on the two-dimensional lattice. Then determining explicit expressions for the matrices becomes equivalent to solving a lattice path counting problem, the solution of which is derived using path decomposition, Bernoulli excursions, and hypergeometric functions. A few applications are provided, including classical models for which we obtain some new results.

Mallows and Shepp (2008) developed the following necklace processes. Start with a necklace consisting of one white bead and one black bead, and insert, one at a time, under a deterministic rule, a white bead or a black bead between a randomly chosen adjacent pair. They studied the statistical properties of the number of white beads by investigating the nature of the moments and the expected number of gaps of given length between white beads. In this note we study the number of white beads via Pólya urns and give a classification of necklace processes for some general rules. Additionally, we discuss the number of runs, i.e. the number of consecutive same color beads, instead of the number of gaps.

A sequence of independent Bernoulli random variables with success probabilities a / (a + b + k − 1), k = 1, 2, 3, …, is embedded in a marked Poisson process with intensity 1. Using this, conditional Poisson limits follow for counts of failure strings.

Recently, Makri, Philippou and Psillakis (2007b) studied the exact distribution of success run statistics defined on an urn model. They derived the exact distributions of various success run statistics for a sequence of binary trials generated by the Pólya-Eggenberger sampling scheme. In our study we derive the joint distributions of run statistics defined on the multicolor urn model using a simple unified combinatorial approach and extend some of the results of Makri, Philippou and Psillakis (2007b). As a consequence of our results, we obtain the joint distributions of success and failure runs defined on the two-color urn model. The results enable us to compute the characteristics of particular consecutive-type systems and start-up demonstration tests.

We study a process where balls are repeatedly thrown into n boxes independently according to some probability distribution p. We start with n balls, and at each step, all balls landing in the same box are fused into a single ball; the process terminates when there is only one ball left (coalescence). Let c := ∑jpj2, the collision probability of two fixed balls. We show that the expected coalescence time is asymptotically 2c−1, under two constraints on p that exclude a thin set of distributions p. One of the constraints is c = o(ln−2n). This ln−2n is shown to be a threshold value: for c = ω(ln−2n), there exists p with c(p) = c such that the expected coalescence time far exceeds c−1. Connections to coalescent processes in population biology and theoretical computer science are discussed.

We study the number of collisions, Xn, of an exchangeable coalescent with multiple collisions (Λ-coalescent) which starts with n particles and is driven by rates determined by a finite characteristic measure η(dx) = x−2Λ(dx). Via a coupling technique, we derive limiting laws of Xn, using previous results on regenerative compositions derived from stick-breaking partitions of the unit interval. The possible limiting laws of Xn include normal, stable with index 1 ≤ α < 2, and Mittag-Leffler distributions. The results apply, in particular, to the case when η is a beta(a − 2, b) distribution with parameters a > 2 and b > 0. The approach taken allows us to derive asymptotics of three other functionals of the coalescent: the absorption time, the length of an external branch chosen at random from the n external branches, and the number of collision events that occur before the randomly selected external branch coalesces with one of its neighbours.

We study a model arising in chemistry where n elements numbered 1, 2, …, n are randomly permuted and if i is immediately to the left of i + 1 then they become stuck together to form a cluster. The resulting clusters are then numbered and considered as elements, and this process keeps repeating until only a single cluster is remaining. In this article we study properties of the distribution of the number of permutations required.

We investigate the average similarity of random strings as captured by the average number of ‘cousins’ in the underlying tree structures. Analytical techniques including poissonization and the Mellin transform are used for accurate calculation of the mean. The string alphabets we consider are m-ary, and the corresponding trees are m-ary trees. Certain analytic issues arise in the m-ary case that do not have an analog in the binary case.

In a sequence of independent Bernoulli trials the probability of success in the kth trial is pk = a / (a + b + k − 1). An explicit formula for the binomial moments of the number of two consecutive successes in the first n trials is obtained and some consequences of it are derived.

We study collision probabilities concerning the simple balls-and-bins problem developed by Wendl (2003). In this article we give the factorial moment of the number of collisions. Moreover, we obtain a Poisson approximation for the number of collisions using the Chen-Stein method.

The distributions of the run occurrences for a sequence of independent and identically distributed (i.i.d.) experiments are usually obtained by combinatorial methods (see Balakrishnan and Koutras (2002, Chapter 5)) and the resulting formulae are often very tedious, while the distributions for non i.i.d. experiments are generally intractable. It is therefore of practical interest to find a suitable approximate model with reasonable approximation accuracy. In this paper we demonstrate that the negative binomial distribution is the most suitable approximate model for the number of k-runs: it outperforms the Poisson approximation, the general compound Poisson approximation as observed in Eichelsbacher and Roos (1999), and the translated Poisson approximation in Rollin (2005). In particular, its accuracy of approximation in terms of the total variation distance improves when the number of experiments increases, in the same way as the normal approximation improves in the Berry-Esseen theorem.

Detection of repeated sequences within complete genomes is a powerful tool to help understanding genome dynamics and species evolutionary history. To distinguish significant repeats from those that can be obtained just by chance, statistical methods have to be developed. In this paper we show that the distribution of the number of long repeats in long sequences generated by stationary Markov chains can be approximated by a Poisson distribution with explicit parameter. Thanks to the Chen-Stein method we provide a bound for the approximation error; this bound converges to 0 as soon as the length n of the sequence tends to ∞ and the length t of the repeats satisfies n2ρt = O(1) for some 0 < ρ < 1. Using this Poisson approximation, p-values can then be easily calculated to determine if a given genome is significantly enriched in repeats of length t.