The Library
Small sets and Markov transition densities
Tools
Kendall, Wilfrid S. and Montana, Giovanni. (2002) Small sets and Markov transition densities. Stochastic Processes and their Applications, Vol.99 (No.2). pp. 177194. ISSN 03044149

PDF
WRAP_Kendall_Small_sets_371.pdf  Submitted Version  Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (220Kb) 
Official URL: http://dx.doi.org/10.1016/S03044149(02)00090X
Abstract
The theory of general statespace Markov chains can be strongly related to the case of discrete statespace by use of the notion of small sets and associated minorization conditions. The general theory shows that small sets exist for all Markov chains on statespaces with countably generated sigmaalgebras, though the minorization provided by the theory concerns small sets of order n and nstep transition kernels for some unspecified n. Partly motivated by the growing importance of small sets for Markov chain Monte Carlo and Coupling from the Past, we show that in general there need be no small sets of order n = 1 even if the kernel is assumed to have a density function (though of course one can take n = 1 if the kernel density is continuous). However, n = 2 will suffice for kernels with densities (integral kernels), and in fact small sets of order 2 abound in the technical sense that the 2step kernel density can be expressed as a countable sum of nonnegative separable summands based on small sets, This can be exploited to produce a representation using a latent discrete Markov chain; indeed one might say, inside every Markov chain with measurable transition density there is a discrete statespace Markov chain struggling to escape. We conclude by discussing complements to these results, including their relevance to Harrisrecurrent Markov chains and we relate the counterexample to Turan problems for bipartite graphs.
Item Type:  Journal Article 

Subjects:  Q Science > QA Mathematics 
Divisions:  Faculty of Science > Statistics 
Library of Congress Subject Headings (LCSH):  Markov processes, Statespace methods 
Journal or Publication Title:  Stochastic Processes and their Applications 
Publisher:  Elsevier Science BV 
ISSN:  03044149 
Date:  June 2002 
Volume:  Vol.99 
Number:  No.2 
Number of Pages:  18 
Page Range:  pp. 177194 
Identification Number:  10.1016/S03044149(02)00090X 
Status:  Peer Reviewed 
Publication Status:  Published 
Access rights to Published version:  Restricted or Subscription Access 
Funder:  Engineering and Physical Sciences Research Council (EPSRC), European Union (EU) 
Grant number:  GR/L5683 (EPSRC), ERBFMRXCT960095 (EU) 
References:  [1] K.B. Athreya and P. Ney. A new approach to the limit theory of recurrent Markov chains. Transactions of the American Mathematical Society, 245:493–501, 1978. [2] N.H. Bingham, C.M. Goldie, and J.L. Teugels. Regular Variation. Cambridge University Press, Cambridge, 1987. [3] B. Bollob´as. Modern Graph Theory. SpringerVerlag, New York, 1998. [4] L.A. Breyer and G.O. Roberts. Some multistep coupling constructions for Markov chains. Research report, University of Lancaster, 2000. [5] L.A. Breyer and G.O. Roberts. Catalytic perfect simulation. Methodology and computing in applied probability, To appear, 2001. [6] W. Doeblin. Sur les propri´et´es asymptotiques de mouvement r´egis par certains types de chaˆınes simples. Bull. Math. Soc. Roum. Sci., 1,2(57115,361), 1937. [7] J.L. Doob. Stochastic Processes. John Wiley & Sons, New York, 1953. [8] J.H. Friedman and N.I. Fisher. Bump hunting in highdimensional data. Statistics and Computing, 9:123–143, 1999. [9] Z. F¨uredi. New asymptotics for bipartite Tur´an numbers. Journal of Combinatorial Theory. Series A, 75:141–144, 1996. [10] A.P. Godbole, B. Lamorte, and E.J. Sandquist. Threshold functions for the bipartite Tur´an property. Electronic Journal of Combinatorics, 4.1(R18), 1997. [11] P.J. Green and D.J. Murdoch. Exact sampling for Bayesian inference: towards general purpose algorithms (with discussion). In J.M. Bernardo, J.O. Berger, A.P. Dawid, and A.F.M. Smith, editors, Bayesian Statistics 6, pages 301–321. The Clarendon Press Oxford University Press, 1999. Presented as an invited paper at the 6th Valencia International Meeting on Bayesian Statistics, Alcossebre, Spain, June 1998. [12] P.R. Halmos. Measure Theory. SpringerVerlag, New York, 1974. (First edition, 1950, Litton, New York). [13] A.H. Hoekstra and F.W. Steutel. Limit theorems for Markov chains of finite rank. Linear Algebra and Applications, 60:65–77, 1984. [14] S.P. Meyn and R.L. Tweedie. Markov Chains and Stochastic Stability. Springer Verlag, New York, 1993. [15] D.J Murdoch and P.J. Green. Exact sampling from a continuous state space. Scand. J. Stat., 25:483–502, 1998. [16] E. Nummelin. A splitting technique for Harrisrecurrent chains. Zeitschrift f¨ur Wahrscheinlichkeitstheorie und Verve Gebiete, 43:309–318, 1978. [17] E. Nummelin. General Irreducible Markov Chains and Nonnegative Operators. Cambridge University Press, Cambridge, 1984. [18] S. Orey. Lecture Notes on Limit Theorems for Markov Chain Transition Probabilities. Van Nostrand Rienhold, London, 1971. [19] C.P. Robert. Discretization and MCMC Convergence Assessment. Lecture Notes 135. SpringerVerlag, New York, 1998. [20] G.O. Roberts and J.S. Rosenthal. Quantitative bounds for convergence rates of continuous time Markov processes. Electronic Journal of Probability, 1:1–21, 1996. Paper 1. [21] G.O. Roberts and J.S. Rosenthal. Small and pseudosmall sets for Markov chains. Stochastic Models, 17(2):to appear, 2000. Available at URL ftp://markov. utstat.toronto.edu/jeff/psmall.ps.Z. [22] J.S. Rosenthal. Convergence of pseudofinite Markov chains. Unpublished manuscript available at http://markov.utstat.toronto.edu/jeff/ research.html, 1992. [23] J.S. Rosenthal. Minorization conditions and convergence rates for Markov chain Monte Carlo. Journal of American Statistical Association, 90:558–566, 1995. [24] W. Rudin. Real and Complex Analysis. McGrawHill, New York, 1966. [25] J.Th. Runnenburg and F.W. Steutel. On Markov chains the transition function of which is a finite sum of products of one variable. Annals of Mathematical Statistics, 33:1483–1484, 1962. 
URI:  http://wrap.warwick.ac.uk/id/eprint/10903 
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
View Item 