Joint Distributions of Numbers of Runs of Specified Lengths in a Sequence of Markov Dependent Multistate Trials

Let Z ₀, Z ₁,...,Z _n be a sequence of Markov dependent trials with state space Ω = {F ₁,...,F _λ, S ₁,...,S _ν}, where we regard F ₁,...,F _λ as failures and S ₁,...,S _ν as successes. In this paper, we study the joint distribution of the numbers of S _i -runs of lengths k _ij (i = 1,2,...,ν, j = 1,2,...,r _i ) based on four different enumeration schemes. We present formulae for the evaluation of the probability generating functions and the higher order moments of this distribution. In addition, when the underlying sequence is i.i.d. trials, the conditional distribution of the same run statistics, given the numbers of success and failure is investigated. We give further insights into the multivariate run-related problems arising from a sequence of the multistate trials. Besides, our results have potential applications to problems of various research areas and will come to prominence in the future. This research was partially supported by the ISM Cooperative Research Program (2004-ISM·CRP-2007).     

Recursive merge sort with erroneous comparisons

In this paper, we analyze the recursive merge sort algorithm and quantify the deviation of the output from the correct sorted order if the outcomes of one or more comparisons are in error. The disorder in the output sequence is quantified by four measures: the number of runs, the smallest number of integers that need to be removed to leave the sequence sorted, the number of inversions, and the smallest number of successive exchanges needed to sort the sequence. For input sequences whose length is large compared to the number of errors, a comparison is made between the robustness to errors of bubble sort, straight insertion sort, and recursive merge sort.     

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.      

Application of auxiliary Markov chains to start-up demonstration tests

We use auxiliary Markov chains to derive probabilistic results for five types of start-up demonstration tests, with start-ups that are Markovian of a general order. Four of the tests are based on consecutive (or total) successful start-ups and consecutive (or total) failures; the fifth has two rejection criteria. For each test type, we obtain the probability of the test ending with acceptance of the unit, the probability distribution and moments of the number of start-ups in the test, the probability of acceptance (or rejection) of the equipment in a specified number of trials, and the conditional distribution of the number of start-ups in the test given that the unit is accepted or rejected. Numerical examples are given. Though the results are for these specific types of start-up demonstration tests, the method of derivation may be used for tests with other stopping criteria, and in other situations as well.     

Statistical Process Control using Shewhart Control Charts with Supplementary Runs Rules

The aim of this paper is to present the basic principles and recent advances in the area of statistical process control charting with the aid of runs rules. More specifically, we review the well known Shewhart type control charts supplemented with additional rules based on the theory of runs and scans. The motivation for this article stems from the fact that during the last decades, the performance improvement of the Shewhart charts by exploiting runs rules has attracted continuous research interest. Furthermore, we briefly discuss the Markov chain approach which is the most popular technique for studying the run length distribution of run based control charts.      

On the Resolution of Path Ideals of Cycles

We give a formula to compute all the top degree graded Betti numbers of the path ideal of a cycle. Also we will find a criterion to determine when Betti numbers of this ideal are nonzero and give a formula to compute its projective dimension and regularity.     

Improving the Performance of the Chi-square Control Chart via Runs Rules

The most popular multivariate process monitoring and control procedure used in the industry is the chi-square control chart. As with most Shewhart-type control charts, the major disadvantage of the chi-square control chart, is that it only uses the information contained in the most recently inspected sample; as a consequence, it is not very efficient in detecting gradual or small shifts in the process mean vector. During the last decades, the performance improvement of the chi-square control chart has attracted continuous research interest. In this paper we introduce a simple modification of the chi-square control chart which makes use of the notion of runs to improve the sensitivity of the chart in the case of small and moderate process mean vector shifts.