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. 177-194. ISSN 0304-4149

Preview

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/S0304-4149(02)00090-X

Abstract

The theory of general state-space Markov chains can be strongly related to the case of discrete state-space 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 state-spaces with countably generated sigma-algebras, though the minorization provided by the theory concerns small sets of order n and n-step 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 2-step kernel density can be expressed as a countable sum of non-negative 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 state-space Markov chain struggling to escape. We conclude by discussing complements to these results, including their relevance to Harris-recurrent 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, State-space methods
Journal or Publication Title:	Stochastic Processes and their Applications
Publisher:	Elsevier Science BV
ISSN:	0304-4149
Date:	June 2002
Volume:	Vol.99
Number:	No.2
Number of Pages:	18
Page Range:	pp. 177-194
Identification Number:	10.1016/S0304-4149(02)00090-X
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), ERB-FMRX-CT96-0095 (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. Springer-Verlag, New York, 1998. [4] L.A. Breyer and G.O. Roberts. Some multi-step 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(57-115,3-61), 1937. [7] J.L. Doob. Stochastic Processes. John Wiley & Sons, New York, 1953. [8] J.H. Friedman and N.I. Fisher. Bump hunting in high-dimensional 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. Springer-Verlag, 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 Harris-recurrent chains. Zeitschrift f¨ur Wahrscheinlichkeitstheorie und Verve Gebiete, 43:309–318, 1978. [17] E. Nummelin. General Irreducible Markov Chains and Non-negative 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. Springer-Verlag, 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 pseudo-small 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 pseudo-finite 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. McGraw-Hill, 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