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

G. Nuel ()
Additional contact information
G. Nuel: Sorbonne University

Methodology and Computing in Applied Probability, 2019, vol. 21, issue 3, 875-887

Abstract: Abstract 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.

Keywords: Probability generating function; Moment generating function; Probabilistic graphical model; Bayesian network; Sum-product algorithm; Forward/backward algorithms; 60J10; 60J22 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s11009-019-09700-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:21:y:2019:i:3:d:10.1007_s11009-019-09700-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-019-09700-0

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().