IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v392y2013i7p1593-1601.html
   My bibliography  Save this article

Markov chain order estimation with conditional mutual information

Author

Listed:
  • Papapetrou, M.
  • Kugiumtzis, D.

Abstract

We introduce the Conditional Mutual Information (CMI) for the estimation of the Markov chain order. For a Markov chain of K symbols, we define CMI of order m, Ic(m), as the mutual information of two variables in the chain being m time steps apart, conditioning on the intermediate variables of the chain. We find approximate analytic significance limits based on the estimation bias of CMI and develop a randomization significance test of Ic(m), where the randomized symbol sequences are formed by random permutation of the components of the original symbol sequence. The significance test is applied for increasing m and the Markov chain order is estimated by the last order for which the null hypothesis is rejected. We present the appropriateness of CMI-testing on Monte Carlo simulations and compare it to the Akaike and Bayesian information criteria, the maximal fluctuation method (Peres–Shields estimator) and a likelihood ratio test for increasing orders using ϕ-divergence. The order criterion of CMI-testing turns out to be superior for orders larger than one, but its effectiveness for large orders depends on data availability. In view of the results from the simulations, we interpret the estimated orders by the CMI-testing and the other criteria on genes and intergenic regions of DNA chains.

Suggested Citation

  • Papapetrou, M. & Kugiumtzis, D., 2013. "Markov chain order estimation with conditional mutual information," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(7), pages 1593-1601.
    • Handle: RePEc:eee:phsmap:v:392:y:2013:i:7:p:1593-1601
    DOI: 10.1016/j.physa.2012.12.017
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437112010837
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2012.12.017?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Kugiumtzis, D. & Provata, A., 2004. "Statistical analysis of gene and intergenic DNA sequences," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 342(3), pages 623-638.
    2. Buldyrev, S.V. & Dokholyan, N.V. & Goldberger, A.L. & Havlin, S. & Peng, C.-K. & Stanley, H.E. & Viswanathan, G.M., 1998. "Analysis of DNA sequences using methods of statistical physics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 249(1), pages 430-438.
    3. M. L. Menéndez & L. Pardo & M. C. Pardo & K. Zografos, 2011. "Testing the Order of Markov Dependence in DNA Sequences," Methodology and Computing in Applied Probability, Springer, vol. 13(1), pages 59-74, March.
    4. L. Zhao & C. Dorea & C. Gonçalves, 2001. "On Determination of the Order of a Markov Chain," Statistical Inference for Stochastic Processes, Springer, vol. 4(3), pages 273-282, October.
    5. Menendez, M.L. & Pardo, J.A. & Pardo, L. & Zografos, K., 2006. "On tests of independence based on minimum [phi]-divergence estimator with constraints: An application to modeling DNA," Computational Statistics & Data Analysis, Elsevier, vol. 51(2), pages 1100-1118, November.
    6. M. Menéndez & J. Pardo & L. Pardo, 2001. "Csiszar’s ϕ-divergences for testing the order in a Markov chain," Statistical Papers, Springer, vol. 42(3), pages 313-328, July.
    7. Dalevi Daniel & Dubhashi Devdatt & Hermansson Malte, 2006. "A New Order Estimator for Fixed and Variable Length Markov Models with Applications to DNA Sequence Similarity," Statistical Applications in Genetics and Molecular Biology, De Gruyter, vol. 5(1), pages 1-26, March.
    8. Kugiumtzis Dimitris, 2008. "Evaluation of Surrogate and Bootstrap Tests for Nonlinearity in Time Series," Studies in Nonlinear Dynamics & Econometrics, De Gruyter, vol. 12(1), pages 1-26, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Abhik Ghosh, 2022. "Robust parametric inference for finite Markov chains," TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 31(1), pages 118-147, March.
    2. Papapetrou, M. & Kugiumtzis, D., 2020. "Tsallis conditional mutual information in investigating long range correlation in symbol sequences," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 540(C).
    3. Fokianos, Konstantinos & Fried, Roland & Kharin, Yuriy & Voloshko, Valeriy, 2022. "Statistical analysis of multivariate discrete-valued time series," Journal of Multivariate Analysis, Elsevier, vol. 188(C).
    4. Andreas C. Georgiou & Alexandra Papadopoulou & Pavlos Kolias & Haris Palikrousis & Evanthia Farmakioti, 2021. "On State Occupancies, First Passage Times and Duration in Non-Homogeneous Semi-Markov Chains," Mathematics, MDPI, vol. 9(15), pages 1-17, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Papapetrou, M. & Kugiumtzis, D., 2020. "Tsallis conditional mutual information in investigating long range correlation in symbol sequences," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 540(C).
    2. Kengne, William, 2021. "Strongly consistent model selection for general causal time series," Statistics & Probability Letters, Elsevier, vol. 171(C).
    3. Resende, Paulo Angelo Alves & Dorea, Chang Chung Yu, 2016. "Model identification using the Efficient Determination Criterion," Journal of Multivariate Analysis, Elsevier, vol. 150(C), pages 229-244.
    4. Lachos, Victor H. & Prates, Marcos O. & Dey, Dipak K., 2021. "Heckman selection-t model: Parameter estimation via the EM-algorithm," Journal of Multivariate Analysis, Elsevier, vol. 184(C).
    5. Sidorov, S.P. & Faizliev, A.R. & Balash, V.A. & Korobov, E.A., 2016. "Long-range correlation analysis of economic news flow intensity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 444(C), pages 205-212.
    6. Andreas C. Georgiou & Alexandra Papadopoulou & Pavlos Kolias & Haris Palikrousis & Evanthia Farmakioti, 2021. "On State Occupancies, First Passage Times and Duration in Non-Homogeneous Semi-Markov Chains," Mathematics, MDPI, vol. 9(15), pages 1-17, July.
    7. John Halley & Dimitris Kugiumtzis, 2011. "Nonparametric testing of variability and trend in some climatic records," Climatic Change, Springer, vol. 109(3), pages 549-568, December.
    8. Kalamaras, N. & Philippopoulos, K. & Deligiorgi, D. & Tzanis, C.G. & Karvounis, G., 2017. "Multifractal scaling properties of daily air temperature time series," Chaos, Solitons & Fractals, Elsevier, vol. 98(C), pages 38-43.
    9. Xie, Rongrong & Deng, Shengfeng & Deng, Weibing & Pato, Mauricio P., 2022. "Generalized Poisson ensemble," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 585(C).
    10. Saha, Debajyoti & Shaw, Pankaj Kumar & Ghosh, Sabuj & Janaki, M.S. & Sekar Iyengar, A.N., 2018. "Quantification of scaling exponent with Crossover type phenomena for different types of forcing in DC glow discharge plasma," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 490(C), pages 300-310.
    11. Abhik Ghosh, 2022. "Robust parametric inference for finite Markov chains," TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 31(1), pages 118-147, March.
    12. M. L. Menéndez & L. Pardo & M. C. Pardo & K. Zografos, 2011. "Testing the Order of Markov Dependence in DNA Sequences," Methodology and Computing in Applied Probability, Springer, vol. 13(1), pages 59-74, March.
    13. Buldyrev, Sergey V. & Dokholyan, Nikolay V. & Havlin, Shlomo & Stanley, H.Eugene & Stanley, Rachel H.R., 1999. "Expansion of tandem repeats and oligomer clustering in coding and noncoding DNA sequences," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 273(1), pages 19-32.
    14. Aylin Alin & Serdar Kurt, 2008. "Ordinary and penalized minimum power-divergence estimators in two-way contingency tables," Computational Statistics, Springer, vol. 23(3), pages 455-468, July.
    15. Zsurkis, Gabriel & Nicolau, João & Rodrigues, Paulo M.M., 2024. "First passage times in portfolio optimization: A novel nonparametric approach," European Journal of Operational Research, Elsevier, vol. 312(3), pages 1074-1085.
    16. Şahin, Gökhan & Erentürk, Murat & Hacinliyan, Avadis, 2009. "Detrended fluctuation analysis in natural languages using non-corpus parametrization," Chaos, Solitons & Fractals, Elsevier, vol. 41(1), pages 198-205.
    17. Jin, Xin & Nie, Rencan & Zhou, Dongming & Yao, Shaowen & Chen, Yanyan & Yu, Jiefu & Wang, Quan, 2016. "A novel DNA sequence similarity calculation based on simplified pulse-coupled neural network and Huffman coding," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 461(C), pages 325-338.
    18. Li Wang & Xing-Lu Gao & Wei-Xing Zhou, 2023. "Testing For Intrinsic Multifractality In The Global Grain Spot Market Indices: A Multifractal Detrended Fluctuation Analysis," FRACTALS (fractals), World Scientific Publishing Co. Pte. Ltd., vol. 31(07), pages 1-24.
    19. Kugiumtzis, D. & Provata, A., 2004. "Statistical analysis of gene and intergenic DNA sequences," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 342(3), pages 623-638.
    20. repec:jss:jstsof:33:i05 is not listed on IDEAS
    21. Dutta, Srimonti & Ghosh, Dipak & Chatterjee, Sucharita, 2016. "Multifractal detrended Cross Correlation Analysis of Foreign Exchange and SENSEX fluctuation in Indian perspective," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 463(C), pages 188-201.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:392:y:2013:i:7:p:1593-1601. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.