Distribution Theory of Runs and Patterns and Its Applications

The following sections are included:

• Preface

• Contents

The occurrence of runs and patterns in a sequence of discrete trial outcomes or random permutations is an important concept in various areas of science, including reliability engineering, quality control, psychology, sociology, DNA sequence matching, and hypothesis testing. Results for the probability distributions of elementary runs and patterns were derived sporadically in the literature until about the 1940s, when a number of pioneering studies on more complex runs and patterns were published: for example, Wishart and Hirshfeld (1936), Cochran (1938), Mood (1940), Wald and Wolfowitz (1940), Mosteller (1941), and Wolfowitz (1943). Most of these studies focused on finding the conditional distribution of success runs given the total number of successes in a sequence of two-state trials. A recent book by Balakrishnan and Koutras (2002) provides an excellent, comprehensive review of historical and current developments in the distribution theory of runs and scan statistics…

The following sections are included:

• Finite Markov Chain

• Chapman-Kolmogorov Equation

• Tree-Structured Markov Chain

• Runs and Patterns

• Finite Markov Chain Imbedding

• Absorbing State

• First-Entry Probability

The following sections are included:

• Introduction

• Number of Non-Overlapping Consecutive k Successes

• Number of Success Runs of Length Greater Than or Equal to k

• Number of Overlapping Consecutive k Successes

• Number of Runs of Exactly k Successes

• The Distribution of the Longest Success Run

• Waiting-Time Distribution of a Success Run

• Numerical Examples

• Number of Successes in Success Runs of Length Greater Than or Equal to k

The following sections are included:

• Introduction

• Forward and Backward Principle with Non-Overlap Counting

• Overlap Counting

• Series Pattern

• Joint Distribution

The following sections are included:

• Introduction

• The Waiting Time of A Simple Pattern

• The Waiting Time of A Compound Pattern

• Probability Generating Function

• Mean of Waiting Time W(Λ)

• More About Generating Functions

• Spectrum Analysis and Large Deviation Approximation

• Probability Generating Function of W(r, Λ)

• Scan Statistics

The following sections are included:

• Introduction

• Successions

• Eulerian and Simon Newcomb Numbers

The following sections are included:

• Introduction

• System Reliability
  • Consecutive-k-out-of-n:F System
  • Linearly Connected System

• Hypothesis Testing

• Sequential Continuity

• Quality Control Schemes
  • Simple Control Schemes
  • Compound Control Schemes

The following sections are included:

• Bibliography

• Index