On runs of length exceeding a threshold: normal approximation

Run statistics denoting number of runs and sum of run lengths are defined on binary sequences and their asymptotic normality is established by a simple unified way for Bernoulli sequences. All the considered statistics share a common feature; they refer to runs of length exceeding a specific length (a threshold). Asymptotic results of associated statistics denoting run lengths and waiting times are derived as well. Specific probabilities of the examined statistics are used in applications in the fields of system reliability and molecular biology. The study is illustrated by an extensive numerical experimentation.     

Run statistics in a sequence of arbitrarily dependent binary trials

Let {Z _i } _i≥1 be an arbitrary sequence of trials with two possible outcomes either success (1) or failure (0). General expressions for the exact distributions of runs, both success and failure, in Z ₁, . . . , Z _n are presented. Our method is based on the use of joint distribution of success and failure run lengths and unifies the results on distribution of runs. As a special case of our results we obtain the distributions of runs for various binary sequences. As illustrated in the paper the results enable us to derive the distribution of runs for binary trials arising in urn models.     

Distributions of Runs and Scans on Higher-Order Markov Trees

In this article, we consider the distributions of the number of success runs of specified length and scans on a higher-order Markov tree under three different enumeration schemes (the “non overlapping”, the “at least”, and the “overlapping” scheme). Recursive formulae for the evaluation of their probability generating functions are established. We provide a proper framework for extending the exact distribution theory of runs and scans from based on sequences to based on directed trees. Some numerical results for the run and scan statistics are given in order to illustrate the computational aspects and the feasibility of our theoretical results. Finally, two special reliability systems are considered, which are closely related to our general results.     

Distribution of the length of the longest common subsequence of two multi-state biological sequences

The length of the longest common subsequence (LCS) among two biological sequences has been used as a measure of similarity, and the application of this statistic is of importance in genomic studies. Even for the simple case of two sequences of equal length and composed of binary elements with equal state probabilities, the exact distribution of the length of the LCS remains an open question. This problem is also known as an NP-hard problem in computer science. Apart from combinatorial analysis, using the finite Markov chain imbedding technique, we derive the exact distribution for the length of the LCS between two multi-state sequences of different lengths. Numerical results are provided to illustrate the theoretical results.     

On the distribution and expectation of success runs in nonhomogeneous Markov dependent trials

The number of success runs for nonhomogeneous markov dependent trials are represented as the sum of Bernoulli trials and the expected value of runs are obtained by using this representation. The distribution and bounds for the distribution of the longest run are derived for markov dependent trials.     

Central Limit Theorem approximations for the number of runs in Markov-dependent binary sequences

We consider Markov-dependent binary sequences and study various types of success runs (overlapping, non-overlapping, exact, etc.) by examining additive functionals based on state visits and transitions in an appropriate Markov chain. We establish a multivariate Central Limit Theorem for the number of these types of runs and obtain its covariance matrix by means of the recurrent potential matrix of the Markov chain. Explicit expressions for the covariance matrix are given in the Bernoulli and a simple Markov-dependent case by expressing the recurrent potential matrix in terms of the stationary distribution and the mean transition times in the chain. We also obtain a multivariate Central Limit Theorem for the joint number of non-overlapping runs of various sizes and give its covariance matrix in explicit form for Markov dependent trials.     

Generalized run tests for statistical process control

ABSTRACT

In a sequence of elements, a run is defined as a maximal subsequence of like elements. The number of runs or the length of the longest run has been widely used to test the randomness of an ordered sequence. Based on two different sampling methods and two types of test statistics used, run tests can be classified into one of four cases. Numerous researchers have derived the probability distributions in many different ways, treating each case separately. In the paper, we propose a unified approach which is based on recurrence arguments of two mutually exclusive sub-sequences. We also consider the sequence of nominal data that has more than two classes. Thus, the traditional run tests for a binary sequence are special cases of our generalized run tests. We finally show that the generalized run tests can be applied to many quality management areas, such as testing changes in process variation, developing non-parametric multivariate control charts, and comparing the shapes and locations of more than two process distributions.     

Mean success run length

In this paper we consider mean of success run lengths appearing in a sequence of binary trials. We derive the exact and limiting distributions of mean success run length for i.i.d. Bernoulli trials. The exact distribution of the corresponding random variable is also derived for a sequence of Markov-dependent Bernoulli trials. In addition, a combinatorial formula for the distribution of any success run statistic defined on Markov-dependent trials is presented.     

Statistical morphology

This paper first introduces a parametric model for the generation of stationary random correlated binary sequences. The parameters of the model include the probability that a pixel is a binary one pixel and the length of the structuring element which dilates the initially spatially uncorrelated sequence. The spatial statistics of such eroded, dilated, opened and closed correlated binary sequences are derived in terms of the spatial statistics of the input binary sequence. Understanding of such one-dimensional processing is a precondition for understanding what happens in the more interesting two- dimensional case.     

Statistical morphology

This paper first introduces a parametric model for the generation of stationary random correlated binary sequences. The parameters of the model include the probability that a pixel is a binary one pixel and the length of the structuring element which dilates the initially spatially uncorrelated sequence. The spatial statistics of such eroded, dilated, opened and closed correlated binary sequences are derived in terms of the spatial statistics of the input binary sequence. Understanding of such one-dimensional processing is a precondition for understanding what happens in the more interesting two- dimensional case.     

On binomial and circular binomial distributions of orderk forl-overlapping success runs of lengthk

The number ofl-overlapping success runs of lengthk inn trials, which was introduced and studied recently, is presently reconsidered in the Bernoulli case and two exact formulas are derived for its probability distribution function in terms of multinomial and binomial coefficients respectively. A recurrence relation concerning this distribution, as well as its mean, is also obtained. Furthermore, the number ofl-overlapping success runs of lengthk inn Bernoulli trials arranged on a circle is presently considered for the first time and its probability distribution function and mean are derived. Finally, the latter distribution is related to the first, two open problems regarding limiting distributions are stated, and numerical illustrations are given in two tables. All results are new and they unify and extend several results of various authors on binomial and circular binomial distributions of orderk.     

Contributions to adaptive estimation

There are many statistics which can be used to characterize data sets and provide valuable information regarding the data distribution, even for large samples. Traditional measures, such as skewness and kurtosis, mentioned in introductory statistics courses, are rarely applied. A variety of other measures of tail length, skewness and tail weight have been proposed, which can be used to describe the underlying population distribution. Adaptive statistical procedures change the estimator of location, depending on sample characteristics. The success of these estimators depends on correctly classifying the underlying distribution model. Advocates of adaptive distribution testing propose to proceed by assuming (1) that an appropriate model, say Omega , is such that Omega { Omega , Omega , i i 1 2 … , Omega }, and (2) that the character of the model selection process is statistically k independent of the hypothesis testing. We review the development of adaptive linear estimators and adaptive maximum-likelihood estimators.     

Distributions of statistics describing concentration of runs in non homogeneous Markov-dependent trials

In the first n, n ? 3, trials of a non homogeneous zero-one Markov chain of first order, we consider runs of ones of length exceeding a threshold. The article deals with statistics denoting, the length and the position of the shortest segment of the chain in which all such runs of ones are concentrated. The study provides recursive schemes for conditional distributions of these statistics. Numerical examples illustrate the theoretical results.     

Poisson approximation and dna sequence matching

The Poisson distribution is commonly used to model the number of occurrences of independent rare events. However, many instances arise where dependence exists, for example, in counting the length of long head runs in coin tossing, or matches between two DNA sequences. The Chen-Stein method of Poisson approximation yields bounds on the error incurred when approximating the number of occurrences of possibly dependent events by a Poisson random variable of the same mean. In addition to the problems related to the motivating examples from molecular biology involving runs and matches, the method may be applied to questions as varied as calculating probabilities involving extremes of sequences of random variables and approximating the probability of general birthday coincidences.     

On ℓ-overlapping Runs of Ones of Length k in Sequences of Independent Binary Random Variables

Consider a finite sequence of independent binary (zero-one) random variables ordered on a line or on a circle. The number of the ?-overlapping runs of ones of a fixed length k is studied for both types of the concerned ordering. Recurrences for the exact probability mass functions for these numbers are obtained via simple probabilistic arguments. Exact closed formulae, for the mean and variance of the studied numbers are obtained via their representations through properly defined indicators. Two application case studies, concerning record sequences and reliability of consecutive systems, clarify further the theoretical results.     

Refined solution to upper-bound problem for the expectations of order statistics from decreasing density on the average distributions

Rychlik [Metrika 77, 539–557, 2014] described sharp upper negative bounds for the expectations of low-rank order statistics, centered about the population mean and measured in the mean absolute deviation from the mean units, for the i.i.d. sequences with common distribution possessing decreasing density function on the average. The bounds coincide with the negatives of maximal values of complicated functions on the unit interval. Here, we provide more precise solutions to the maximization problems.     

Explicit Distributional Results In Pattern Formation II

The paper derives the joint generating function of a collection of pattern statistics associated with binary sequences. The models discussed cover independent and some dependent Bernoulli trials, including Markov dependent ones. The results cover, in particular, the moment generating function of the random search time for certain general binary patterns in the popular Knuth-Morris-Pratt algorithm and hence shed more light into its performance.     

Joint distribution of rises,falls, and number of runs in random sequences

By using the matrix formulation of the two-step approach to the distributions of runs, a recursive relation and an explicit expression are derived for the generating function of the joint distribution of rises and falls for multivariate random sequences in terms of generating functions of individual letters, from which the generating functions of the joint distribution of rises, falls, and number of runs are obtained. An explicit formula for the joint distribution of rises and falls with arbitrary specification is also obtained.