Relevant States and Memory in Markov Chain Bootstrapping and Simulation

Cerqueti, Roy and Falbo, Paolo and Pelizzari, Cristian (2010): Relevant States and Memory in Markov Chain Bootstrapping and Simulation.

Abstract

Markov chain theory is proving to be a powerful approach to bootstrap highly nonlinear time series. In this work we provide a method to estimate the memory of a Markov chain (i.e. its order) and to identify its relevant states. In particular the choice of memory lags and the aggregation of irrelevant states are obtained by looking for regularities in the transition probabilities. Our approach is based on an optimization model. More specifically we consider two competing objectives that a researcher will in general pursue when dealing with bootstrapping: preserving the “structural” similarity between the original and the simulated series and assuring a controlled diversification of the latter. A discussion based on information theory is developed to define the desirable properties for such optimal criteria. Two numerical tests are developed to verify the effectiveness of the method proposed here.

• Item Type: MPRA Paper
• Language: English
• Keywords: Bootstrapping; Information Theory; Markov chains; Optimization; Simulation.
• Subjects: C - Mathematical and Quantitative Methods > C1 - Econometric and Statistical Methods and Methodology: General > C15 - Statistical Simulation Methods: General; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C63 - Computational Techniques ; Simulation Modeling; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C65 - Miscellaneous Mathematical Tools

References

Akaike H (1970) On a decision procedure for system identification. In: Kyoto Symposium on System Engineering Approach to Computer Control (ed) Proceedings of the IFAC Kyoto Symposium on System Engineering Approach to Computer Control. Kyoto Symposium on System Engineering Approach to Computer Control, Kyoto, Japan, pp 485–490.

Anatolyev S, Vasnev A (2002) Markov chain approximation in bootstrapping autoregressions. Economics Bulletin 3:1–8.

Athreya KB, Fuh CD (1992) Bootstrapping Markov chains: Countable case. Journal of Statistical Planning and Inference 33:311–331.

Barron A, Rissanen J, Yu B (1998) The minimum description length principle in coding and modeling. IEEE Transactions on Information Theory 44:2743–2760.

Basawa IV, Green TA, McCormick WP, Taylor RL (1990) Asymptotic bootstrap validity for finite Markov chains. Communications in Statistics - Theory and Methods 19:1493–1510.

Bertail P, Clemencon S (2006) Regenerative block bootstrap for Markov chains. Bernoulli 12:689– 712.

Bertail P, Clemencon S (2007) Second-order properties of regeneration-based bootstrap for atomic Markov chains. Test 16:109–122.

Brock W, Lakonishok J, LeBaron B (1992) Simple technical trading rules and the stochastic properties of stock returns. The Journal of Finance 47:1731–1764.

Buhlmann P (1997) Sieve bootstrap for time series. Bernoulli 3:123–148.

Buhlmann P (2002) Sieve bootstrap with variable-length Markov chains for stationary categorical time series. Journal of the American Statistical Association 97:443–456.

Buhlmann P, Kunsch HR (1999) Block length selection in the bootstrap for time series. Computational Statistics & Data Analysis 31:295–310.

Buhlmann P, Wyner AJ (1999) Variable length Markov chains. The Annals of Statistics 27:480–513.

Carlstein E (1986) The use of subseries values for estimating the variance of a general statistic from a stationary sequence. The Annals of Statistics 14:1171–1179.

Cha S-H (2007) Comprehensive survey on distance/similarity measures between probability density functions. International Journal of Mathematical Models and Methods in Applied Sciences 1:300- 307.

Chambaz A, Garivier A, Gassiat E (2009) A minimum description length approach to hidden Markov models with Poisson and Gaussian emissions. Application to order identification. Journal of Statistical Planning and Inference 139:962–977.

Ching W-K, Ng MK, Fung ES (2008) Higher-order multivariate Markov chains and their applications. Linear Algebra and Its Applications 428:492–507.

Csiszar I (2002) Large-scale typicality of Markov sample paths and consistency of MDL order estimators. IEEE Transactions on Information Theory 48:1616–1628.

Csiszar I, Shields PC (2000) The consistency of the BIC Markov order estimator. The Annals of Statistics 28:1601–1619.

Datta S, McCormick WP (1992) Bootstrap for a finite state Markov chain based on i.i.d. resampling. In: LePage R, Billard L (eds) Exploring the Limits of Bootstrap. John Wiley & Sons, New York, NY, USA, pp 77–97.

Datta S, McCormick WP (1993) Regeneration-based bootstrap for Markov chains. The Canadian Journal of Statistics 21:181–193.

Efron B (1979) Bootstrap methods: Another look at the jackknife. The Annals of Statistics 7:1–26.

Efron B, Tibshirani RJ (1986) Bootstrap methods for standard errors, confidence intervals, and other measures of statistical accuracy. Statistical Science 1:54–75.

Efron B, Tibshirani RJ (1993) An Introduction to the Bootstrap. Chapman & Hall, New York, NY, USA.

Feder M, Merhav N, Gutman M (1992) Universal prediction of individual sequences. IEEE Transactions on Information Theory 38:1258–1270.

Finesso L (1992) Estimation of the order of a finite Markov chain. In: Kimura H, Kodama S (eds) Recent Advances in Mathematical Theory of Systems, Control, Networks, and Signal Processing: Proceedings of the International Symposium MTNS-91. Mita Press, Tokyo, Japan, pp 643–645.

Freedman DA (1984) On bootstrapping two-stage least-squares estimates in stationary linear models. The Annals of Statistics 12:827–842.

Freedman DA, Peters SC (1984) Bootstrapping a regression equation: Some empirical results. Journal of the American Statistical Association 79:97–106.

Hall P (1985) Resampling a coverage pattern. Stochastic Processes and their Applications 20:231– 246.

Hall P, Horowitz JL, Jing B-Y (1995) On blocking rules for the bootstrap with dependent data. Biometrika 82:561–574.

Horowitz JL (2003) Bootstrap methods for Markov processes. Econometrica 71:1049–1082.

Kieffer JC (1993) Strongly consistent code-based identification and order estimation for constrained finite-state model classes. IEEE Transactions on Information Theory 39:893–902.

Kolmogorov AN (1965) Three approaches to the quantitative definition of information. Problemy Peredachi Informatsii 1:3–11.

Kulperger RJ, Prakasa Rao BLS (1989) Bootstrapping a finite state Markov chain. Sankhya, The Indian Journal of Statistics 51:178–191.

Kunsch HR (1989) The jackknife and the bootstrap for general stationary observations. The Annals of Statistics 17:1217–1241.

Lahiri SN (2003) Resampling Methods for Dependent Data. Springer-Verlag, New York, NY, USA.

Lahiri SN, Furukawa K, Lee Y-D (2007) A nonparametric plug-in rule for selecting optimal block lengths for block bootstrap methods. Statistical Methodology 4:292–321.

Liu C-C, Narayan P (1994) Order estimation and sequential universal data compression of a hidden Markov source by the method of mixtures. IEEE Transactions on Information Theory 40:1167–1180.

Liu RY, Singh K (1992) Moving blocks jackknife and bootstrap capture weak dependence. In: LePage R, Billard L (eds) Exploring the Limits of Bootstrap. John Wiley & Sons, New York, NY, USA, pp 225–248.

Merhav N, Gutman M, Ziv J (1989) On the estimation of the order of a Markov chain and universal data compression. IEEE Transactions on Information Theory 35:1014–1019.

Morvai G, Weiss B (2005) Order estimation of Markov chains. IEEE Transactions on Information Theory 51:1496–1497.

Paparoditis E, Politis DN (2001a) Tapered block bootstrap. Biometrika 88:1105–1119.

Paparoditis E, Politis DN (2001b) A Markovian local resampling scheme for nonparametric estimators in time series analysis. Econometric Theory 17:540–566.

Paparoditis E, Politis DN (2002a) The tapered block bootstrap for general statistics from stationary sequences. The Econometrics Journal 5:131–148.

Paparoditis E, Politis DN (2002b) The local bootstrap for Markov processes. Journal of Statistical Planning and Inference 108:301–328.

Peres Y, Shields PC (2008) Two new Markov order estimators. http://arxiv.org/PS_cache/math/pdf/0506/0506080v1.pdf. Retrieved on 9 February 2013.

Politis DN, Romano JP (1992) A general resampling scheme for triangular arrays of mixing random variables with application to the problem of spectral density estimation. The Annals of Statistics 20:1985–2007.

Politis DN, Romano JP (1994) The stationary bootstrap. Journal of the American Statistical Association 89:1303–1313.

Politis DN, White H (2004) Automatic block-length selection for the dependent bootstrap. Econometric Reviews 23:53–70.

Rajarshi MB (1990) Bootstrap in Markov-sequences based on estimates of transition density. Annals of the Institute of Statistical Mathematics 42:253–268.

Rissanen J (1978) Modeling by shortest data description. Automatica 14:465–471.

Rissanen J (1983) A universal data compression system. IEEE Transactions on Information Theory IT-29:656–664.

Rissanen J (1986) Complexity of strings in the class of Markov sources. IEEE Transactions on Information Theory IT-32:526–532.

Rissanen J, Langdon Jr. GG (1981) Universal modeling and coding. IEEE Transactions on Information Theory IT-27:12–23.

Schwarz G (1978) Estimating the dimension of a model. The Annals of Statistics 6:461–464.

Sullivan R, Timmermann A, White H (1999) Data-snooping, technical trading rule performance, and the bootstrap. The Journal of Finance 54:1647–1691.

Ullah A (1996) Entropy, divergence and distance measures with econometric applications. Journal of Statistical Planning and Inference 49:137-162.

Weinberger MJ, Lempel A, Ziv J (1992) A sequential algorithm for the universal coding of finite memory sources. IEEE Transactions on Information Theory 38:1002–1014.

Weinberger MJ, Rissanen JJ, Feder M (1995) A universal finite memory source. IEEE Transactions on Information Theory 41:643–652.

Ziv J, Merhav N (1992) Estimating the number of states of a finite-state source. IEEE Transactions on Information Theory 38:61–65.