Bounding \(\bar d\)-distance by informational divergence: A method to prove measure concentration. (English) Zbl 0865.60017

Summary: There is a simple inequality by Pinsker between variational distance and informational divergence of probability measures defined on arbitrary probability spaces. We shall consider probability measures on sequences taken from countable alphabets, and derive, from Pinsker’s inequality, bounds on \(\overline d\)-distance by informational divergence. Such bounds can be used to prove the “concentration of measure” phenomenon for some nonproduct distributions.


60F10 Large deviations
60G70 Extreme value theory; extremal stochastic processes
60G05 Foundations of stochastic processes
Full Text: DOI


[1] AHLSWEDE, R., GACS, P. and KORNER, J. 1976. Bounds on conditional probabilities with applica\' ẗions in multi-user communication. Z. Wahrsch. Verw. Gebiete 34 157 177. Z. · Zbl 0349.94038
[2] CSISZAR, I. and KORNER, J. 1981. Information Theory: Coding Theorems for Discrete Memory\' \" less Sy stems. Academic Press, New York. Z.
[3] MARTON, K. 1986. A simple proof of the blowing-up lemma. IEEE Trans. Inform. Theory IT-32 445 446. Z. · Zbl 0594.94003
[4] MARTON, K. 1995a. A concentration-of-measure inequality for contracting Markov chains. Geometric and Functional Analy sis. To appear. Z.
[5] MARTON, K. 1995b. Processes having the blowing-up property. Unpublished manuscript. Z.
[6] MARTON, K. and SHIELDS, P. C. 1994. The positive divergence and blowing-up properties. Israeli J. Math. 86 331 348. Z. · Zbl 0797.60044
[7] MCDIARMID, C. 1989. On the method of bounded differences. In Survey s in Combinatorics. Z. London Mathematical Society Lecture Notes J. Simons, ed. 141 148 188. Cambridge Univ. Press, London. Z. · Zbl 0712.05012
[8] PAPAMARCOU, A. and SHALABY, H. 1993. Error exponent for distributed detection of Markov sources. IEEE Trans. Inform. Theory 40 397 408. Z. · Zbl 0802.62002
[9] PINSKER, M. S. 1964. Information and Information Stability of Random Variables and Processes. Holden-Day, San Francisco. Z. · Zbl 0125.09202
[10] TALAGRAND, M. 1995. Concentration of measure and isoperimetric inequalities in product spaces. Publ. IHES. 81 73 205. · Zbl 0864.60013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.