Runs and patterns, coupon collecting and permutations

多状态试验序列中游程和模式的分布理论有着悠久而丰富的历史，在遗传学(特别是生物序列)、可靠性理论、博弈论、健康科学和一般统计推断中都有应用。通过有限马尔可夫嵌入技术，可以找到一大类这样的游程和图案的准确分布。一般来说，我们考虑的是大量试验中模式出现次数的准确分布。然而，在许多情况下，这些马尔可夫链的结果状态空间大得令人望而却步，从时间和空间的角度来看，精确的概率计算都变得困难。在这项研究中，我们建议研究这些概率的新的近似方法。对于这类问题，我们已经发展了极限左尾概率的近似，其表现优于通常的高斯和泊松近似。在这里，我们打算对极右尾概率发展类似的结果。出于许多原因，这些都很重要。在生物序列(例如DNA、RNA和蛋白质序列)中，出现频率比预期高得多(或比怀疑低得多)的模式可能具有一些生物功能，因此识别这些模式很重要。我还将研究多集合的排列和排列中的游程和模式的分布。这里的额外困难在于排列元素之间的依赖结构。在这里，我不仅打算研究具体的情况，而且还打算研究更普遍的方法，这些方法将适用于各种不同的运行和排列模式。排列中的游程和模式有许多与上面列出的相同的应用。例如，RNA中的一些二级结构可以与排列相联系。该方案的最后一个研究领域涉及经典优惠券收集器问题的一些推广，这些问题具有诸如网络安全、捕获/标记/重新捕获实验和可靠性理论等应用。用于多状态试验和排列中的运行和模式的许多技术也适用于这些类型的扩展。

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.