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.