Runs and patterns, coupon collecting and permutations

点击翻译按钮获取中文摘要

The distribution theory of runs and patterns in sequences of multi-state trials has a long and rich history and has applications in genetics (particularly biological sequences), reliability theory, game theory, health sciences and general statistical inference. The exact distribution for a large class of these runs and patterns may be found by a finite Markov imbedding technique. In general, we consider the exact distribution of the number of occurrences of patterns in a large number of trials. In many cases, however, the resulting state spaces for these Markov chains are prohibitively large and exact probability calculations become difficult from both a time and space perspective. In this research we propose to study new approximation methods for these probabilities. We have developed approximations for extreme left-tail probabilities which outperform the usual Gaussian and Poisson approximations for these types of problems. Here, we intend to develop similar results for extreme right-tail probabilities. These are important for many reasons. In biological sequences (DNA, RNA and protein sequences, for example), patterns which occur much more often than expected (or much less often than suspected) may have some biological function and hence identifying these are important. I will also investigate the distribution of runs and patterns in permutations and permutations of multi-sets. The additional difficulty here lies with dependence structure among elements of the permutations. Here, I intend to not only study specific cases, but also to study more general methods that will be applicable for a wide variety of runs and patterns in permutations. Runs and patterns in permutations have many of the same applications as those listed above. Some secondary structures in RNA, for example, can be linked to permutations. The final area of research in this proposal involves some generalizations of the classic coupon collector's problem and these have applications such as network security, capture/mark/recapture experiments, and reliability theory. Many of the techniques used for runs and patterns in multi-state trials and permutations also have applications to these types of extensions.