The Exact and Limiting Distributions for the Number of Successes in Success Runs Within a Sequence of Markov-Dependent Two-State Trials

The total number of successes in success runs of length greater than or equal to k in a sequence of n two-state trials is a statistic that has been broadly used in statistics and probability. For Bernoulli trials with k equal to one, this statistic has been shown to have binomial and normal distributions as exact and limiting distributions, respectively. For the case of Markov-dependent two-state trials with k greater than one, its exact and limiting distributions have never been considered in the literature. In this article, the finite Markov chain imbedding technique and the invariance principle are used to obtain, in general, the exact and limiting distributions of this statistic under Markov dependence, respectively. Numerical examples are given to illustrate the theoretical results.     

On the distribution of the total number of run lengths

In the present paper, we study the distribution of a statistic utilizing the runs length of “reasonably long” series of alike elements (success runs) in a sequence of binary trials. More specifically, we are looking at the sum of exact lengths of subsequences (strings) consisting ofk or more consecutive successes (k is a given positive integer). The investigation of the statistic of interest is accomplished by exploiting an appropriate generalization of the Markov chain embedding technique introduced by Fu and Koutras (1994,J. Amer. Statist. Assoc.,89, 1050–1058) and Koutras and Alexandrou (1995,Ann. Inst. Statist. Math.,47, 743–766). In addition, we explore the conditional distribution of the same statistic, given the number of successes and establish statistical tests for the detection of the null hypothesis of randomness versus the alternative hypothesis of systematic clustering of successes in a sequence of binary outcomes. Research supported by General Secretary of Research and Technology of Greece under grand PENED 2001.     

Stochastic Ordering Among Success Runs Statistics in a Sequence of Exchangeable Binary Trials

A new scheme-distribution-based representation is presented for the cumulative distribution function of the number of success runs of length k in a sequence of exchangeable binary trials. By utilizing this new representation, some stochastic ordering results are obtained to compare success runs. The results are illustrated for beta-binomial distributions of order k.     

Waiting time distributions of runs in higher order Markov chains

We consider a {0,1}-valuedm-th order stationary Markov chain. We study the occurrences of runs where two 1’s are separated byat most/exactly/at least k 0’s under the overlapping enumeration scheme wherek≥0 and occurrences of scans (at leastk ₁ successes in a window of length at mostk, 1≤k ₁≤k) under both non-overlapping and overlapping enumeration schemes. We derive the generating function of first two types of runs. Under the conditions, (1) strong tendency towards success and (2) strong tendency towards reversing the state, we establish the convergence of waiting times of ther-th occurrence of runs and scans to Poisson type distributions. We establish the central limit theorem and law of the iterated logarithm for the number of runs and scans up to timen.     

Joint distributions of numbers of success-runs and failures until the first consecutivek successes

Joint distributions of the numbers of failures, successes and success-runs of length less thank until the first consecutivek successes are obtained for some random sequences such as a sequence of independent and identically distributed integer valued random variables, a {0, 1}-valued Markov chain and a binary sequence of orderk. There are some ways of counting numbers of runs with a specified length. This paper studies the joint distributions based on three ways of counting numbers of runs, i.e., the number of overlapping runs with a specified length, the number of non-overlapping runs with a specified length and the number of runs with a specified length or more. Marginal distributions of them can be derived immediately, and most of them are surprisingly simple.This research was partially supported by the ISM Cooperative Research Program (93-ISM-CRP-8).     

Numbers of Success-Runs of Specified Length Until Certain Stopping Time Rules and Generalized Binomial Distributions of Order k

A new distribution called a generalized binomial distribution of order k is defined and some properties are investigated. A class of enumeration schemes for success-runs of a specified length including non-overlapping and overlapping enumeration schemes is rigorously studied. For each nonnegative integer less than the specified length of the runs, an enumeration scheme called -overlapping way of counting is defined. Let k and be positive integers satisfying < k. Based on independent Bernoulli trials, it is shown that the number of (– 1)-overlapping occurrences of success-run of length k until the n-th overlapping occurrence of success-run of length follows the generalized binomial distribution of order (k–). In particular, the number of non-overlapping occurrences of success-run of length k until the n-th success follows the generalized binomial distribution of order (k– 1). The distribution remains unchanged essentially even if the underlying sequence is changed from the sequence of independent Bernoulli trials to a dependent sequence such as higher order Markov dependent trials. A practical example of the generalized binomial distribution of order k is also given.     

Exact Laws for Sums of Order Statistics from a Generalized Pareto Distribution

Abstract

We select the kth order statistic from each row from a sequence of independent and identically distributed random variables from a distribution that generalizes the Pareto distribution. We then examine weighted sums of these order statistics to see whether or not Laws of Large Numbers with nonzero limits exist.     

Distributions of numbers of failures and successes until the first consecutivek successes

Exact distributions of the numbers of failures, successes and successes with indices no less thanl (1lk–1) until the first consecutivek successes are obtained for some {0, 1}-valued random sequences such as a sequence of independent and identically distributed (iid) trials, a homogeneous Markov chain and a binary sequence of orderk. The number of failures until the first consecutivek successes follows the geometric distribution with an appropriate parameter for each of the above three cases. When the {0, 1}-sequence is an iid sequence or a Markov chain, the distribution of the number of successes with indices no less thanl is shown to be a shifted geometric distribution of orderk - l. When the {0, 1}-sequence is a binary sequence of orderk, the corresponding number follows a shifted version of an extended geometric distribution of orderk - l.This research was partially supported by the ISM Cooperative Research Program (92-ISM-CRP-16) of the Institute of Statistical Mathematics.     

Compound Poisson Approximation for Multiple Runs in a Markov Chain

We consider a sequence X ₁, ..., X _n of r.v.'s generated by a stationary Markov chain with state space A = {0, 1, ..., r}, r 1. We study the overlapping appearances of runs of k _i consecutive i's, for all i = 1, ..., r, in the sequence X ₁,..., X _n. We prove that the number of overlapping appearances of the above multiple runs can be approximated by a Compound Poisson r.v. with compounding distribution a mixture of geometric distributions. As an application of the previous result, we introduce a specific Multiple-failure mode reliability system with Markov dependent components, and provide lower and upper bounds for the reliability of the system.     

Reliability formula &; limit law of the failure time of “<Emphasis Type="Italic">m</Emphasis>-consecutive-<Emphasis Type="Italic">k</Emphasis>-out-of-<Emphasis Type="Italic">n</Emphasis>:<Emphasis Type="Italic">F</Emphasis> system”

An “m-consecutive-k-out-of-n:F system” consists of n components ordered on a line; the system fails if and only if there are at least m nonoverlapping runs of k consecutive failed components. In this paper, we give a recursive formula to compute the reliability of such a system. Thereafter, we state two asymptotic results concerning the failure time Z _n of the system. The first result concerns a limit theorem for Z _n when the failure times of components are not necessarily with identical failure distributions. In the second one, we prove that, for an arbitrary common failure distribution of components, the limit system failure distribution is always of the Poisson class.      

Maximizing the descent statistic

For a subsetS, let the descent statistic (S) be the number of permutations that have descent setS. We study inequalities between the descent statistics of subsets. Each subset (and its complement) is encoded by a list containing the lengths of the runs. We define two preorders that compare different lists based on the descent statistic. Using these preorders, we obtain a complete order on lists of the form (k ⁱ ,P,k ^n–i , whereP is a palindrome, whose first entry is larger thank. We prove a conjecture due to Gessel, which determines the list that maximizes the descent statistic, among lists of a given size and given length. We also have a generalization of the boustrophedon transform of Millar, Sloane and Young.     

An application of the method of finite Markov chain imbedding to runs tests

The method of finite Markov chain imbedding developed by Fu and Koutras (1994) has become a popular and useful tool for studying runs and patterns-related problems. In this article, their approach is used as an alternative for obtaining the exact conditional distribution of the success runs statistic given the number of successes in a sequence of n i.i.d. Bernoulli trials, which, in the past, was computed mainly from traditional combinatorics.     

A Combinatorial Proof of the Log-Concavity of the Numbers of Permutations with k Runs

We combinatorially prove that the number R(n, k) of permutations of length n having k runs is a log-concave sequence in k, for all n. We also give a new combinatorial proof for the log-concavity of the Eulerian numbers.     

Asymptotic behaviour and optimal word size for exact and approximate word matches between random sequences

The present work is concerned with a fast and accurate sequence comparison method: the count of the number of words of length k letters shared by two sequences, also known as the D2 statistic. We link recent theoretical advances in the characterization of D2 asymptotic distributions with applications to biological sequences. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Partially Ordered Generalized Patterns and <Emphasis Type="Italic">k</Emphasis>-ary Words

Recently, Kitaev [9] introduced partially ordered generalized patterns (POGPs) in the symmetric group, which further generalize the generalized permutation patterns introduced by Babson and Steingrímsson [1]. A POGP p is a GP some of whose letters are incomparable. In this paper, we study the generating functions (g.f.) for the number of k-ary words avoiding some POGPs. We give analogues, extend and generalize several known results, as well as get some new results. In particular, we give the g.f. for the entire distribution of the maximum number of non-overlapping occurrences of a pattern p with no dashes (which is allowed to have repetition of letters), provided we know the g.f. for the number of k-ary words that avoid p.AMS Subject Classification: 05A05, 05A15.     

Remarks on the <Emphasis Type="Italic">k</Emphasis>-error linear complexity of <Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>-periodic sequences

Recently the first author presented exact formulas for the number of 2 ⁿ -periodic binary sequences with given 1-error linear complexity, and an exact formula for the expected 1-error linear complexity and upper and lower bounds for the expected k-error linear complexity, k ≥ 2, of a random 2 ⁿ -periodic binary sequence. A crucial role for the analysis played the Chan–Games algorithm. We use a more sophisticated generalization of the Chan–Games algorithm by Ding et al. to obtain exact formulas for the counting function and the expected value for the 1-error linear complexity for p ⁿ -periodic sequences over prime. Additionally we discuss the calculation of lower and upper bounds on the k-error linear complexity of p ⁿ -periodic sequences over .      

Measures of affinity of a sequence for a number

We define strong and weak affinities of a number a for a sequence (x_k ) denoted by L (a,(x_k )) and U (a, (x_k )) respectively. We show U (a,(x_k )) > 0 if and only if the number a is a statistical limit point of the sequence (x_k ). We consider the distribution of sequences with positive weak and strong measures of affinity within the space l ^∞ of bounded sequences. The main result is that the set of bounded sequences with U (a,(x_k )) > 0, that is, the set of sequences with statistical limit points, is a dense subset in l ^∞ of the first category. We also show the set of sequences with positive strong affinities is a nowhere dense subset of l ^∞.     

Estimation with Sequential Order Statistics from Exponential Distributions

The lifetime of an ordinary k-out-of-n system is described by the (n–k+1)-st order statistic from an iid sample. This set-up is based on the assumption that the failure of any component does not affect the remaining ones. Since this is possibly not fulfilled in technical systems, sequential order statistics have been proposed to model a change of the residual lifetime distribution after the breakdown of some component. We investigate such sequential k-out-of-n systems where the corresponding sequential order statistics, which describe the lifetimes of these systems, are based on one- and two-parameter exponential distributions. Given differently structured systems, we focus on three estimation concepts for the distribution parameters. MLEs, UMVUEs and BLUEs of the location and scale parameters are presented. Several properties of these estimators, such as distributions and consistency, are established. Moreover, we illustrate how two sequential k-out-of-n systems based on exponential distributions can be compared by means of the probability P(X < Y). Since other models of ordered random variables, such as ordinary order statistics, record values and progressive type II censored order statistics can be viewed as sequential order statistics, all the results can be applied to these situations as well.     

On Success Runs of Length Exceeded a Threshold

Consider a sequence of n two state (success-failure) trials with outcomes arranged on a line or on a circle. The elements of the sequence are independent (identical or non identical distributed), exchangeable or first-order Markov dependent (homogeneous or non homogeneous) random variables. The statistic denoting the number of success runs of length at least equal to a specific length (a threshold) is considered. Exact formulae, lower/upper bounds and approximations are obtained for its probability distribution. The mean value and the variance of it are derived in an exact form. The distributions and the means of an associated waiting time and the length of the longest success run are provided. The reliability function of certain general consecutive systems is deduced using specific probabilities of the studied statistic. Detailed application case studies, covering a wide variety of fields, are combined with extensive numerical experimentation to illustrate further the theoretical results.