Simultaneous Occurrences of Runs in Independent Markov Chains

We observe m independent and identically distributed binary Markov chains and look for simultaneous occurrences of runs in several of them. We are interested in the distribution of the maximum number of simultaneous runs on finite time intervals. First we introduce a natural exact approach and also explain why it fails to calculate the required probabilities. Then we find exact upper and lower bounds for the probability of interest. We apply these results to detect genomic deletions in cancer patients.      

Joint distributions of numbers of success runs of specified lengths in linear and circular sequences

In this paper, we study two joint distributions of the numbers of success runs of several lengths in a sequence ofn Bernoulli trials arranged on a line (linear sequence) or on a circle (circular sequence) based on four different enumeration schemes. We present formulae for the evaluation of the joint probability functions, the joint probability generating functions and the higher order moments of these distributions. Besides, the present work throws light on the relation between the joint distributions of the numbers of success runs in the circular and linear binomial model. We give further insights into the run-related problems arisen from the circular sequence. Some examples are given in order to illustrate our theoretical results. Our results have potential applications to other problems such as statistical run tests for randomness and reliability theory. This research was partially supported by the ISM Cooperative Research Program (2003-ISM.CRP-2007).     

Long repetitive patterns in random sequences

Summary Appearances of long repetitive sequences such as 00...0 or 1010...101 in random sequences are studied. The expected length of the longest repetitive run of any specified type in a random binary sequence of length n is shown to tend to the binary logarithm of n plus a periodic function of log n. Necessary and sufficient conditions are derived to ensure that with probability 1 an infinite random sequence should contain repetitive runs of specified lengths in given initial segments. Finally, the number of long repetitive runs of a specified kind that occur in a random sequence is studied. These results are derived from simple expressions for the generating functions for the probabilities of occurrences of various repetitive runs. These generating functions are rational, and lead to sharp asymptotic estimates for the probabilities.     

Distributions of numbers of runs and scans on directed acyclic graphs with generation

In this paper, we introduce a class of a directed acyclic graph on the assumption that the collection of random variables indexed by the vertices has a Markov property. We present a flexible approach for the study of the exact distributions of runs and scans on the directed acyclic graph by extending the method of conditional probability generating functions. The results presented here provide a wide framework for developing the exact distribution theory of runs and scans on the graphical models. We also show that our theoretical results can easily be carried out through some computer algebra systems and give some numerical examples in order to demonstrate the feasibility of our theoretical results. As applications, two special reliability systems are considered, which are closely related to our general results. Finally, we address the parameter estimation in the distributions of runs and scans.     

Sooner and Later Waiting Time Problems for Runs in Markov Dependent Bivariate Trials

In this paper we study exact distributions of sooner and later waiting times for runs in Markov dependent bivariate trials. We give systems of linear equations with respect to conditional probability generating functions of the waiting times. By considering bivariate trials, we can treat very general and practical waiting time problems for runs of two events which are not necessarily mutually exclusive. Numerical examples are also given in order to illustrate the feasibility of our results.     

On Number of Occurrences of Success Runs of Specified Length in a Higher-Order Two-State Markov Chain

Let X^-m+1, X^-m+2,..., X⁰, X¹, X²,..., Xⁿ be a time-homogeneous {0, 1}-valued m-th order Markov chain. The probability distributions of numbers of runs of "1" of length k (k m) and of "1" of length k (k < m) in the sequence of a {0, 1}-valued m-th order Markov chain are studied. There are some ways of counting numbers of runs with length k. This paper studies the distributions based on four ways of counting numbers of runs, i.e., the number of non-overlapping runs of length k, the number of runs with length greater than or equal to k, the number of overlapping runs of length k and the number of runs of length exactly k.     

Whitworth runs on a circle

Summary Suppose different classes of items, for example, beads of different colours, are placed in a circle. Two probability models have been proposed, which lead to different distributions of runs, i.e. sequences of one colour. Barton and David [3] have called these Whitworth runs and Jablonski runs, and have tabulated the distributions for small samples. Asano [1] has extended the tabulations for Jablonski runs. In this paper, Whitworth runs are examined, particularly some approximations to the distributions which avoid extensive tabulations. Some potential uses of Whitworth runs are also pointed out.     

Conditional waiting time distributions of runs and patterns and their applications

In this paper, a simple and general method based on the finite Markov chain imbedding technique is proposed to determine the exact conditional distributions of runs and patterns in a sequence of Bernoulli trials given the total number of successes. The idea is that given the total number of successes, the Bernoulli trials are viewed as random permutations. Then, we extend the result to multistate trials. The conditional distributions studied here lead to runs and patterns-type distribution-free tests whose applications are widespread. Two applications are considered. First, a distribution-free test for randomness is applied to rainfall data at Oxford from 1858 to 1952. The second application is to develop runs and patterns-type distribution-free control charts which can be used as Phase I and/or Phase II control charts. Numerical results for two commonly used runs-type statistics, the longest run and scan statistics, are also given.

     

A discrete time model for software reliability with application to a flight control software

This work is motivated by a particular software reliability problem in a unit of flight control software developed by the Indian Space Research Organization (ISRO), in which the testing of the software is carried out in multiple batches, each consisting of several runs. As the errors are found during the runs within a batch, they are noted, but not debugged immediately; they are debugged only at the end of that particular batch of runs. In this work, we introduce a discrete time model suitable for this type of periodic debugging schedule and describe maximum likelihood estimation for the model parameters. This model is used to estimate the reliability of the software. We also develop a method to determine the additional number of error‐free test runs required for the estimated reliability to achieve a specific target with some high probability. We analyze the test data on the flight control software of ISRO. Copyright © 2011 John Wiley & Sons, Ltd.     

Distributions of Numbers of Success Runs of Fixed Length in Markov Dependent Trials

Let {Z _n , n 1} be a time-homogeneous {0, 1}-valued Markov chain, and let N _n be a random variable denoting the number of runs of "1" of length k in the first n trials. In this article we conduct a systematic study of N _n by establishing formulae for the evaluation of its probability generating function, probability mass function and moments. This is done in three different enumeration schemes for counting runs of length k, the "non-overlapping", the "overlapping" and the "at least" scheme. In the special case of i.i.d. trials several new results are established.     

Probability Distribution Functions of Succession Quotas in the Case of Markov Dependent Trials

The exact probability distribution functions (pdf's) of the sooner andlater waiting time random variables (rv's) for the succession quota problemare derived presently in the case of Markov dependent trials. This is doneby means of combinatorial arguments. The probability generating functions(pgf's) of these rv's are then obtained by means of enumerating generatingfunctions (enumerators). Obvious modifications of the proofs provideanalogous results for the occurrence of frequency quotas and such a resultis established regarding the pdf of a frequency and succession quotas rv.Longest success and failure runs are also considered and their jointcumulative distribution function (cdf) is obtained.     

Stationary patterns of strongly coupled prey-predator models

We study some elliptic systems arising from 3-component predator-prey models, where cross-diffusions are included in such a way that predator chases the prey and the prey runs away from the predator. We establish the existence and non-existence of non-constant positive solutions. Our results show that the cross-diffusions can create the stationary patterns.     

Joint Distributions of Runs in a Sequence of Multi-State Trials

In this paper we introduce a Markov chain imbeddable vector of multinomial type and a Markov chain imbeddable variable of returnable type and discuss some of their properties. These concepts are extensions of the Markov chain imbeddable random variable of binomial type which was introduced and developed by Koutras and Alexandrou (1995, Ann. Inst. Statist. Math., 47, 743–766). By using the results, we obtain the distributions and the probability generating functions of numbers of occurrences of runs of a specified length based on four different ways of counting in a sequence of multi-state trials. Our results also yield the distribution of the waiting time problems.     

A note on runs of geometrically distributed random variables

Recently, Grabner et al. [Combinatorics of geometrically distributed random variables: run statistics, Theoret. Comput. Sci. 297 (2003) 261-270] and Louchard and Prodinger [Ascending runs of sequences of geometrically distributed random variables: a probabilistic analysis, Theoret. Comput. Sci. 304 (2003) 59-86] considered the run statistics of geometrically distributed independent random variables. They investigated the asymptotic properties of the number of runs and the longest run using the corresponding probability generating functions and a Markov chain approach. In this note, we reconsider the asymptotic properties of such statistics using another approach. Our approach of finding the asymptotic distributions is based on the construction of runs in a sequence of m-dependent random variables. This approach enables us to find the asymptotic distributions of many run statistics via the theorems established for m-dependent sequence of random variables. We also provide the asymptotic distribution of the total number of non-decreasing runs and the longest non-decreasing run.     

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.     

Bayesian analysis of definitive screening designs when the response is nonnormal

Definitive screening designs (DSDs) are a class of experimental designs that allow the estimation of linear, quadratic, and interaction effects with little experimental effort if there is effect sparsity. The number of experimental runs is twice the number of factors of interest plus one. Many industrial experiments involve nonnormal responses. Generalized linear models (GLMs) are a useful alternative for analyzing these kind of data. The analysis of GLMs is based on asymptotic theory, something very debatable, for example, in the case of the DSD with only 13 experimental runs. So far, analysis of DSDs considers a normal response. In this work, we show a five‐step strategy that makes use of tools coming from the Bayesian approach to analyze this kind of experiment when the response is nonnormal. We consider the case of binomial, gamma, and Poisson responses without having to resort to asymptotic approximations. We use posterior odds that effects are active and posterior probability intervals for the effects and use them to evaluate the significance of the effects. We also combine the results of the Bayesian procedure with the lasso estimation procedure to enhance the scope of the method. Copyright © 2016 John Wiley & Sons, Ltd.     

Recursive equations in finite Markov chain imbedding

In this paper, recursive equations for waiting time distributions of r-th occurrence of a compound pattern are studied via the finite Markov chain imbedding technique under overlapping and non-overlapping counting schemes in sequences of independent and identically distributed (i.i.d.) or Markov dependent multi-state trials. Using the relationship between number of patterns and r-th waiting time, distributions of number of patterns can also be obtained. The probability generating functions are also obtained. Examples and numerical results are given to illustrate our theoretical results.     

Success runs of lengthk in Markov dependent trials

The geometric type and inverse Polýa-Eggenberger type distributions of waiting time for success runs of lengthk in two-state Markov dependent trials are derived by using the probability generating function method and the combinatorial method. The second is related to the minimal sufficient partition of the sample space. The first two moments of the geometric type distribution are obtained. Generalizations to ballot type probabilities of which negative binomial probabilities are special cases are considered. Since the probabilities do not form a proper distribution, a modification is introduced and new distributions of orderk for Markov dependent trials are developed.