Waiting Time Distributions for Competing Compound Patterns in Higher Order Markovian Sequences

Abstract

In recent years, there has been significant research on the calculation of waiting time distributions for runs and patterns in sequences of elements from a Markov chain (first order Markovian sequence). These distributions include the waiting time until the first occurrence of a run of a specific length in a binary state space, the waiting time until the r'th occurrence, and the waiting time until the first occurrence of a simple or compound pattern in a more general finite state space. Here, using the technique of Finite Markov Chain Imbedding (Fu and Koutras, 1994), methods to generate waiting time distributions when the sequence is a higher order Markovian sequence will be established. Included distributions will be the extension of those above, and also the case of the r'th occurrence of a compound pattern in a finite state space. These distributions lead to a more general problem - waiting time distributions for competing patterns. Competing patterns are compound patterns that compete to be the first to occur pattern-specific numbers of times. They represent a generalisation of the sooner waiting time problem and of start-up demonstration tests with both acceptance and rejection criteria. Also all the distributions established above can be seen as special cases. An algorithm for calculating the waiting time distribution of competing patterns in multi-state trials that are Markovian of general order is derived. Also obtained are probabilities that each particular competing pattern will be the first to occur its respective prescribed number of times, both in finite time and in the limit. Joint work with Donald Martin