Finite Markov Chain Imbedding and Its Applications in Stochastic Processes, biological Sequences, and Discrete Mathematics

有限马尔可夫链嵌入（FMCI）技术是一种非传统的，简单，灵活和计算效率高的概率工具，以评估的概率和分布的运行和感兴趣的模式。它已成功应用于解决各种领域的复杂和未解决的问题，如健康科学，基因组分析，可靠性，质量控制，物理学，统计学，应用概率，计算机科学和离散数学。本文将FMCI技术推广到四个非常重要的应用领域：（i）高维布朗运动的边界穿越概率（BCP），（ii）最多允许d个突变的两个DNA序列的匹配概率，（iii）在[S]-指定的随机排列中要避免的模式的分布和（iv）基因组-广泛的关联研究，用于比较正常和疾病染色体之间的基因表达。预期成果如下： A.短期预期成果（未来五年） （一） 第一部分的建议将建立一个分析和有效的数值方法近似的边界交叉概率的非线性凸边界的d维布朗运动。这将表明收敛速度是O（1/n1/2），并且与维数d无关。所得结果将推广到相关的随机过程，如Ornstein-Uhlenbeck过程和布朗桥。 (ii)本文提出了一种相似性度量的统计量Ln（d），即两个DNA序列在最多允许d个突变/插入的情况下的最长匹配长度。将导出Ln（d）的精确分布，并表明Ln（d）的分布可以用扫描统计量的分布来表示。 (iii)得到了[S]-指定随机排列中需要避免的模式的精确分布。为了达到这个目的，从一个带有[s]-指定符号的瓮中逐个采样，而不替换，以形成随机排列。结果将涵盖许多经典的结果，例如条件运行测试和条件扫描统计。 (iv)“碰撞狩猎”在正常和疾病染色体之间的全基因组关联研究中至关重要。在建议的最后一部分中，凸块是由它的两个组成部分，凸块的长度和大小的联合和边缘分布的凸块的数量和长度将被导出。 B。长期目标 (i)长期目标是使用FMCI技术来解决尽可能多的复杂和未解决的问题，图形和新出现的实际问题，与应用概率和统计中的运行和模式的分布，特别是连续的情况下。例如，跳跃过程、扩散过程和马尔可夫过程的边界交叉概率，以及允许最多d个突变/缺失的一组DNA序列之间的匹配概率。

The finite Markov chain imbedding (FMCI) technique is an unconventional, simple, flexible and computation efficient probabilistic tool to evaluate probabilities and distributions of runs and patterns of interest. It has been successfully applied for solving complex and unsolved problems in various areas such as health science, genomic analysis, reliability, quality control, physics, statistics, applied probability, computer science, and discrete mathematics. In this proposal, the FMCI technique is going to be extended into four very important applied areas, (i) boundary crossing probability (BCP) for high dimensional Brownian motion, (ii) matching probability of two DNA sequences with allowing at most d mutations, (iii) distributions of patterns to avoid in [S]-specified random permutation and (iv) distributions of bumps of genome-wide association studies for comparing gene expressions between normal and disease chromosomes. The following are expected results:  A. Short term expected results (next five years) (i)   The first part of the proposal will establish an analytical and efficient numerical method for approximating the boundary crossing probabilities for non-linear convex boundaries of d-dimensional Brownian motion. It will show the rate of convergence is O(1/n1/2) and independent of the dimensionality d. The results will be extended to related stochastic processes such as Ornstein-Uhlenbeck process and Brownian Bridge. (ii)  The statistic Ln(d), the length of the longest matching of two DNA sequences with allowing at most d mutations/insertions, is proposed as a measure for similarity. The exact distributions of Ln(d) will be derived and show that the distribution of Ln(d) can be expressed in terms of the distribution of scan statistics. (iii)  The exact distribution of patterns to avoid in [S]-specified random permutation will be obtained. To achieve the goal, sampling one-by-one from an urn with [s]-specified symbols without replacement to forming random permutation. The results will cover many classical results for example the conditional runs tests and conditional scan statistics. (iv) "Bump hunting" is vital important in genome-wide association studies between normal and disease chromosomes. In the last part of the proposal, the bump is modeled by its two components, the length and size of the bump and the joint and marginal distributions for the number and length of bumps will be derived. B. Long term goal (i)  The long term goal is to use FMCI technique to solve as many complex and unsolved problems, conjectures and newly arise practical problems associated with distributions of runs and patterns in applied probability and statistics, especially the continuous case. For example boundary crossing probabilities for jump processes, diffusion processes and Markov processes and matching probabilities among a set of DNA sequences allowing at most d mutations/deletions.