Moments of the Count of a Regular Expression in a Heterogeneous Random Sequence

作     者：Nuel, G. 

作者机构：Sorbonne Univ Natl Inst Math Sci INSMI Probabil & Stat LPSM CNRS 8001LPMACNRS 7599 F-75005 Paris France 

出 版 物：《METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY》 (应用概率论的方法与计算)

年 卷 期：2019年第21卷第3期

页      面：875-887页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0714[理学-统计学（可授理学、经济学学位）] 0701[理学-数学] 

主　　题：Probability generating function Moment generating function Probabilistic graphical model Bayesian network Sum-product algorithm Forward backward algorithms 

摘      要：We focus here on the distribution of the random count N of a regular expression in a multi-state random sequence generated by a heterogenous Markov source. We first briefly recall how classical Markov chain embedding techniques allow reducing the problem to the count of specific transitions in a (heterogenous) order 1 Markov chain over a deterministic finite automaton state space. From this result we derive the expression of both the mgf/pgf of N as well as the factorial and non-factorial moments of N. We then introduce the notion of evidence-based constraints in this context. Following the classical forward/backward algorithm in hidden Markov models, we provide explicit recursions allowing to compute the mgf/pgf of N under the evidence constraint. All the results presented are illustrated with a toy example.