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.