Cerqueti, Roy and Falbo, Paolo and Pelizzari, Cristian (2010): Relevant States and Memory in Markov Chain Bootstrapping and Simulation.
This is the latest version of this item.

PDF
MPRA_paper_46250.pdf Download (432kB)  Preview 
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 

Original Title:  Relevant States and Memory in Markov Chain Bootstrapping and Simulation 
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 
Item ID:  46254 
Depositing User:  Roy Cerqueti 
Date Deposited:  16 Apr 2013 20:06 
Last Modified:  26 Sep 2019 16:36 
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) Secondorder properties of regenerationbased 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 variablelength 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 SH (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 WK, Ng MK, Fung ES (2008) Higherorder multivariate Markov chains and their applications. Linear Algebra and Its Applications 428:492–507. Csiszar I (2002) Largescale 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) Regenerationbased 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 MTNS91. Mita Press, Tokyo, Japan, pp 643–645. Freedman DA (1984) On bootstrapping twostage leastsquares 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 BY (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 codebased identification and order estimation for constrained finitestate 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. SpringerVerlag, New York, NY, USA. Lahiri SN, Furukawa K, Lee YD (2007) A nonparametric plugin rule for selecting optimal block lengths for block bootstrap methods. Statistical Methodology 4:292–321. Liu CC, 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 blocklength selection for the dependent bootstrap. Econometric Reviews 23:53–70. Rajarshi MB (1990) Bootstrap in Markovsequences 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 IT29:656–664. Rissanen J (1986) Complexity of strings in the class of Markov sources. IEEE Transactions on Information Theory IT32:526–532. Rissanen J, Langdon Jr. GG (1981) Universal modeling and coding. IEEE Transactions on Information Theory IT27: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) Datasnooping, 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:137162. 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 finitestate source. IEEE Transactions on Information Theory 38:61–65. 
URI:  https://mpra.ub.unimuenchen.de/id/eprint/46254 
Available Versions of this Item

Relevant States and Memory in Markov Chain Bootstrapping and Simulation. (deposited 16 Apr 2013 12:33)
 Relevant States and Memory in Markov Chain Bootstrapping and Simulation. (deposited 16 Apr 2013 20:06) [Currently Displayed]