Applications of Renewal Theory to Pattern Analysis

In this thesis, renewal theory is used to analyze patterns of outcomes for discrete random variables. We start by introducing the concept of a renewal process and by giving some examples. It is then shown that we may obtain the distribution of the number of renewals by time t and compute its expectation, the renewal function. We then proceed to state and illustrate the basic limit theorems for renewal processes and make use of Wald’s equation to give a proof of the Elementary Renewal Theorem. The concept of a delayed renewal process is introduced for the purpose of studying the patterns mentioned above. The mean and variance of the number of trials necessary to obtain the first occurrence of the desired pattern are found as well as how these quantities change in cases where a pattern may overlap itself. In addition to this, we explore the expected number of trials between consecutive occurrences of the pattern. If our attention is restricted to patterns from a given finite set, the winning pattern may be defined to be the one which occurs first and the game ends once a winner has been declared. We compute the probability that a given pattern is the winner as well as the expected length of the game. In concluding our discussion, we explore the expected waiting time until we obtain a complete run of distinct or increasing values