Measure concentration and the weak Pinsker property

Tim Austin

doi:10.1007/s10240-018-0098-3

Tim Austin

Publications Mathématiques de l'IHÉS, Volume 128 (2018), pp. 1-119

Abstract

Let $(X, μ)$ be a standard probability space. An automorphism $T$ of $(X, μ)$ has the weak Pinsker property if for every $ε > 0$ it has a splitting into a direct product of a Bernoulli shift and an automorphism of entropy less than $ε$ . This property was introduced by Thouvenot, who asked whether it holds for all ergodic automorphisms.

This paper proves that it does. The proof actually gives a more general result. Firstly, it gives a relative version: any factor map from one ergodic automorphism to another can be enlarged by arbitrarily little entropy to become relatively Bernoulli. Secondly, using some facts about relative orbit equivalence, the analogous result holds for all free and ergodic measure-preserving actions of a countable amenable group.

The key to this work is a new result about measure concentration. Suppose now that $μ$ is a probability measure on a finite product space $A^{n}$ , and endow this space with its Hamming metric. We prove that $μ$ may be represented as a mixture of other measures in which (i) most of the weight in the mixture is on measures that exhibit a strong kind of concentration, and (ii) the number of summands is bounded in terms of the difference between the Shannon entropy of $μ$ and the combined Shannon entropies of its marginals.

Received: 2017-10-16
Accepted: 2018-02-03
Online First: 2018-02-15
Published online: 2018-11-09

DOI: 10.1007/s10240-018-0098-3

@article{PMIHES_2018__128__1_0,
     author = {Tim Austin},
     title = {Measure concentration and the weak {Pinsker} property},
     journal = {Publications Math\'ematiques de l'IH\'ES},
     pages = {1--119},
     year = {2018},
     publisher = {Springer Berlin Heidelberg},
     address = {Berlin/Heidelberg},
     volume = {128},
     doi = {10.1007/s10240-018-0098-3},
     language = {en},
     url = {https://pmihes.centre-mersenne.org/articles/10.1007/s10240-018-0098-3/}
}

TY  - JOUR
AU  - Tim Austin
TI  - Measure concentration and the weak Pinsker property
JO  - Publications Mathématiques de l'IHÉS
PY  - 2018
SP  - 1
EP  - 119
VL  - 128
PB  - Springer Berlin Heidelberg
PP  - Berlin/Heidelberg
UR  - https://pmihes.centre-mersenne.org/articles/10.1007/s10240-018-0098-3/
DO  - 10.1007/s10240-018-0098-3
LA  - en
ID  - PMIHES_2018__128__1_0
ER  -

%0 Journal Article
%A Tim Austin
%T Measure concentration and the weak Pinsker property
%J Publications Mathématiques de l'IHÉS
%D 2018
%P 1-119
%V 128
%I Springer Berlin Heidelberg
%C Berlin/Heidelberg
%U https://pmihes.centre-mersenne.org/articles/10.1007/s10240-018-0098-3/
%R 10.1007/s10240-018-0098-3
%G en
%F PMIHES_2018__128__1_0

Tim Austin. Measure concentration and the weak Pinsker property. Publications Mathématiques de l'IHÉS, Volume 128 (2018), pp. 1-119. doi: 10.1007/s10240-018-0098-3

References
Cited by

[1.] L. M. Abramov The entropy of a derived automorphism, Dokl. Akad. Nauk SSSR, Volume 128 (1959), pp. 647-650 | MR | Zbl

[2.] R. Ahlswede; P. Gács; J. Körner Bounds on conditional probabilities with applications in multi-user communication, Z. Wahrscheinlichkeitstheor. Verw. Geb., Volume 34 (1976), pp. 157-177 | MR | Zbl

[3.] S. Aida; T. Masuda; I. Shigekawa Logarithmic Sobolev inequalities and exponential integrability, J. Funct. Anal., Volume 126 (1994), pp. 83-101 | MR | Zbl

[4.] N. Avni Entropy theory for cross-sections, Geom. Funct. Anal., Volume 19 (2010), pp. 1515-1538 | MR | Zbl

[5.] P. Billingsley Ergodic Theory and Information, Wiley, New York, 1965 | Zbl

[6.] S. G. Bobkov; F. Götze Exponential integrability and transportation cost related to logarithmic Sobolev inequalities, J. Funct. Anal., Volume 163 (1999), pp. 1-28 | MR | Zbl

[7.] B. Bollobás Modern Graph Theory, Springer, Berlin, 1998 | Zbl

[8.] L. Bowen Measure conjugacy invariants for actions of countable sofic groups, J. Am. Math. Soc., Volume 23 (2010), pp. 217-245 | MR | Zbl

[9.] F. R. K. Chung; R. L. Graham; P. Frankl; J. B. Shearer Some intersection theorems for ordered sets and graphs, J. Comb. Theory, Ser. A, Volume 43 (1986), pp. 23-37 | MR | Zbl

[10.] A. Connes; J. Feldman; B. Weiss An amenable equivalence relation is generated by a single transformation, Ergod. Theory Dyn. Syst., Volume 1 (1982), pp. 431-450 (1981) | MR | Zbl

[11.] T. M. Cover; J. A. Thomas Elements of Information Theory, Wiley–Interscience, Hoboken, 2006 | Zbl

[12.] G. Crooks, On measures of entropy and information. Technical note, available online at threeplusone.com/on_information.pdf.

[13.] I. Csiszár Information-type measures of difference of probability distributions and indirect observations, Studia Sci. Math. Hung., Volume 2 (1967), pp. 299-318 | MR | Zbl

[14.] I. Csiszár Sanov property, generalized $I$ -projection and a conditional limit theorem, Ann. Probab., Volume 12 (1984), pp. 768-793 | MR | Zbl

[15.] A. I. Danilenko; K. K. Park Generators and Bernoullian factors for amenable actions and cocycles on their orbits, Ergod. Theory Dyn. Syst., Volume 22 (2002), pp. 1715-1745 | MR | Zbl

[16.] A. Dembo Information inequalities and concentration of measure, Ann. Probab., Volume 25 (1997), pp. 927-939 | MR | Zbl

[17.] R. M. Dudley Real Analysis and Probability, 74, Cambridge Univ. Press, Cambridge, 2002 (revised reprint of the 1989 original) | Zbl

[18.] D. Ellis; E. Friedgut; G. Kindler; A. Yehudayoff Geometric stability via information theory, Discrete Anal., Volume 10 (2016), p. 28 | MR | Zbl

[19.] W. Feller An Introduction to Probability Theory and Its Applications, vol. I, Wiley, New York, 1968 | Zbl

[20.] W. Feller An Introduction to Probability Theory and Its Applications, vol. II, Wiley, New York, 1971 | Zbl

[21.] A. Fieldsteel Stability of the weak Pinsker property for flows, Ergod. Theory Dyn. Syst., Volume 4 (1984), pp. 381-390 | MR | Zbl

[22.] H. Furstenberg Ergodic behaviour of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Anal. Math., Volume 31 (1977), pp. 204-256 | Zbl

[23.] W. Gangbo; R. J. McCann The geometry of optimal transportation, Acta Math., Volume 177 (1996), pp. 113-161 | MR | Zbl

[24.] W. T. Gowers Lower bounds of tower type for Szemerédi’s uniformity lemma, Geom. Funct. Anal., Volume 7 (1997), pp. 322-337 | MR | Zbl

[25.] W. T. Gowers Rough structure and classification, Geom. Funct. Anal., Special Volume, Part I (2000), pp. 79-117

[26.] N. Gozlan; C. Léonard Transport inequalities. A survey, Markov Process. Relat. Fields, Volume 16 (2010), pp. 635-736 | MR | Zbl

[27.] M. Gromov Endomorphisms of symbolic algebraic varieties, J. Eur. Math. Soc., Volume 1 (1999), pp. 109-197 | MR | Zbl

[28.] M. Gromov Metric Structures for Riemannian and Non-Riemannian Spaces, Birkhäuser, Boston, 2001

[29.] Y. Gutman; M. Hochman On processes which cannot be distinguished by finite observation, Isr. J. Math., Volume 164 (2008), pp. 265-284 | MR | Zbl

[30.] P. R. Halmos Lectures on Ergodic Theory, Chelsea, New York, 1960 | Zbl

[31.] T. S. Han Linear dependence structure of the entropy space, Inf. Control, Volume 29 (1975), pp. 337-368 | MR | Zbl

[32.] T. S. Han Nonnegative entropy measures of multivariate symmetric correlations, Inf. Control, Volume 36 (1978), pp. 133-156 | MR | Zbl

[33.] W. Hoeffding Probability inequalities for sums of bounded random variables, J. Am. Stat. Assoc., Volume 58 (1963), pp. 13-30 | MR | Zbl

[34.] C. Hoffman The behavior of Bernoulli shifts relative to their factors, Ergod. Theory Dyn. Syst., Volume 19 (1999), pp. 1255-1280 | MR | Zbl

[35.] S. Kalikow Non-intersecting splitting $σ$ -algebras in a non-Bernoulli transformation, Ergod. Theory Dyn. Syst., Volume 32 (2012), pp. 691-705 | MR | Zbl

[36.] S. Kalikow; R. McCutcheon An Outline of Ergodic Theory, 122, Cambridge Univ. Press, Cambridge, 2010 | Zbl

[37.] S. A. Kalikow $T, T^{- 1}$ transformation is not loosely Bernoulli, Ann. Math. (2), Volume 115 (1982), pp. 393-409 | MR | Zbl

[38.] L. V. Kantorovich On a problem of Monge, Zap. Nauč. Semin. POMI, Volume 312 (2004), pp. 15-16 | MR

[39.] L. V. Kantorovich; G. v. Rubinshtein On a functional space and certain extremum problems, Dokl. Akad. Nauk SSSR, Volume 115 (1957), pp. 1058-1061 | MR | Zbl

[40.] L. V. Kantorovitch On the translocation of masses, C. R. (Dokl.) Acad. Sci. URSS, Volume 37 (1942), pp. 199-201 | MR | Zbl

[41.] A. Katok Fifty years of entropy in dynamics: 1958–2007, J. Mod. Dyn., Volume 1 (2007), pp. 545-596 | MR | Zbl

[42.] J. H. B. Kemperman On the optimum rate of transmitting information, Proc. Int. Sympos. on Probability and Information Theory (1969), pp. 126-169

[43.] J. C. Kieffer A direct proof that VWB processes are closed in the $\bar{d}$ -metric, Isr. J. Math., Volume 41 (1982), pp. 154-160 | MR | Zbl

[44.] J. C. Kieffer A simple development of the Thouvenot relative isomorphism theory, Ann. Probab., Volume 12 (1984), pp. 204-211 | MR | Zbl

[45.] A. N. Kolmogorov A new metric invariant of transient dynamical systems and automorphisms in Lebesgue spaces, Dokl. Akad. Nauk SSSR, Volume 119 (1958), pp. 861-864 | MR | Zbl

[46.] A. N. Kolmogorov Entropy per unit time as a metric invariant of automorphisms, Dokl. Akad. Nauk SSSR, Volume 124 (1959), pp. 754-755 | MR | Zbl

[47.] W. Krieger On entropy and generators of measure-preserving transformations, Trans. Am. Math. Soc., Volume 149 (1970), pp. 453-464 | MR | Zbl

[48.] S. Kullback Certain inequalities in information theory and the Cramér–Rao inequality, Ann. Math. Stat., Volume 25 (1954), pp. 745-751 | MR | Zbl

[49.] S. Kullback A lower bound for discrimination information in terms of variation, IEEE Trans. Inf. Theory, Volume T–13 (1967), p. 126

[50.] S. Kullback; R. A. Leibler On information and sufficiency, Ann. Math. Stat., Volume 22 (1951), pp. 79-86 | MR | Zbl

[51.] M. Ledoux Remarks on logarithmic Sobolev constants, exponential integrability and bounds on the diameter, J. Math. Kyoto Univ., Volume 35 (1995), pp. 211-220 | MR | Zbl

[52.] M. Ledoux On Talagrand’s deviation inequalities for product measures, ESAIM Probab. Stat., Volume 1 (1995), pp. 63-87 | MR | Zbl

[53.] M. Ledoux The Concentration of Measure Phenomenon, 89, Am. Math. Soc., Providence, 2001 | Zbl

[54.] V. L. Levin General Monge–Kantorovich problem and its applications in measure theory and mathematical economics, Functional Analysis, Optimization, and Mathematical Economics, Oxford Univ. Press, New York, 1990, pp. 141-176

[55.] E. Lindenstrauss; Y. Peres; W. Schlag Bernoulli convolutions and an intermediate value theorem for entropies of $K$ -partitions, J. Anal. Math., Volume 87 (2002), pp. 337-367 (dedicated to the memory of Thomas H. Wolff) | MR | Zbl

[56.] N. Linial; A. Samorodnitsky; A. Wigderson A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, Combinatorica, Volume 20 (2000), pp. 545-568 | MR | Zbl

[57.] K. Marton A simple proof of the blowing-up lemma, IEEE Trans. Inf. Theory, Volume 32 (1986), pp. 445-446 | MR | Zbl

[58.] K. Marton Bounding $\bar{d}$ -distance by informational divergence: a method to prove measure concentration, Ann. Probab., Volume 24 (1996), pp. 857-866 | MR | Zbl

[59.] K. Marton A measure concentration inequality for contracting Markov chains, Geom. Funct. Anal., Volume 6 (1996), pp. 556-571 | MR | Zbl

[60.] K. Marton Measure concentration for a class of random processes, Probab. Theory Relat. Fields, Volume 110 (1998), pp. 427-439 | MR | Zbl

[61.] K. Marton; P. C. Shields The positive-divergence and blowing-up properties, Isr. J. Math., Volume 86 (1994), pp. 331-348 | MR | Zbl

[62.] K. Marton; P. C. Shields How many future measures can there be?, Ergod. Theory Dyn. Syst., Volume 22 (2002), pp. 257-280 | MR | Zbl

[63.] C. McDiarmid On the method of bounded differences, Surveys in Combinatorics, Volume 141 (1989), pp. 148-188

[64.] W. J. McGill Multivariate information transmission, Trans. IRE Profess. Group Inf. Theory, Volume 4 (1954), pp. 93-111 | MR

[65.] V. D. Milman The heritage of P. Lévy in geometrical functional analysis, Astérisque, Volume 157–158 (1988), pp. 273-301 | Zbl

[66.] V. D. Milman; G. Schechtman Asymptotic Theory of Finite-Dimensional Normed Spaces, 1200, Springer, Berlin, 1986 (with an appendix by M. Gromov) | Zbl

[67.] D. Ornstein Bernoulli shifts with the same entropy are isomorphic, Adv. Math., Volume 4 (1970), pp. 337-352 (1970) | MR | Zbl

[68.] D. Ornstein Two Bernoulli shifts with infinite entropy are isomorphic, Adv. Math., Volume 5 (1970), pp. 339-348 (1970) | MR | Zbl

[69.] D. Ornstein Newton’s laws and coin tossing, Not. Am. Math. Soc., Volume 60 (2013), pp. 450-459 | MR | Zbl

[70.] D. S. Ornstein An example of a Kolmogorov automorphism that is not a Bernoulli shift, Adv. Math., Volume 10 (1973), pp. 49-62 | MR | Zbl

[71.] D. S. Ornstein A $K$ automorphism with no square root and Pinsker’s conjecture, Adv. Math., Volume 10 (1973), pp. 89-102 | MR | Zbl

[72.] D. S. Ornstein A mixing transformation for which Pinsker’s conjecture fails, Adv. Math., Volume 10 (1973), pp. 103-123 | MR | Zbl

[73.] D. S. Ornstein Ergodic Theory, Randomness, and Dynamical Systems, 5, Yale Univ. Press, New Haven, 1974 | Zbl

[74.] D. S. Ornstein Factors of Bernoulli shifts, Isr. J. Math., Volume 21 (1975), pp. 145-153 (1974) | MR | Zbl

[75.] D. S. Ornstein; P. C. Shields An uncountable family of $K$ -automorphisms, Adv. Math., Volume 10 (1973), pp. 63-88 | MR | Zbl

[76.] D. S. Ornstein; B. Weiss Every transformation is bilaterally deterministic, Isr. J. Math., Volume 21 (1975), pp. 154-158 (1974) | MR | Zbl

[77.] D. S. Ornstein; B. Weiss Entropy and isomorphism theorems for actions of amenable groups, J. Anal. Math., Volume 48 (1987), pp. 1-141 | MR | Zbl

[78.] K. Petersen; J.-P. Thouvenot Tail fields generated by symbol counts in measure-preserving systems, Colloq. Math., Volume 101 (2004), pp. 9-23 | MR | Zbl

[79.] M. S. Pinsker Dynamical systems with completely positive or zero entropy, Sov. Math. Dokl., Volume 1 (1960), pp. 937-938 | MR | Zbl

[80.] M. S. Pinsker Information and Information Stability of Random Variables and Processes, Holden-Day, San Francisco, 1964 | Zbl

[81.] J. Radhakrishnan Entropy and counting (J. Mishra, ed.), Computational Mathematics, Modelling and Applications, IIT Kharagpur, Golden Jubilee Volume, Narosa, New York, 2003, pp. 146-168 (available online via www.tcs.tifr.res.in/~jaikumar/Papers)

[82.] M. Rahe Relatively finitely determined implies relatively very weak bernoulli, Can. J. Math., Volume 30 (1978), pp. 531-548 | MR | Zbl

[83.] V. A. Rohlin Lectures on the entropy theory of transformations with invariant measure, Usp. Mat. Nauk, Volume 22 (1967), pp. 3-56 | MR

[84.] D. J. Rudolph If a two-point extension of a Bernoulli shift has an ergodic square, then it is Bernoulli, Isr. J. Math., Volume 30 (1978), pp. 159-180 | MR | Zbl

[85.] D. J. Rudolph The second centralizer of a Bernoulli shift is just its powers, Isr. J. Math., Volume 29 (1978), pp. 167-178 | MR | Zbl

[86.] D. J. Rudolph; B. Weiss Entropy and mixing for amenable group actions, Ann. Math. (2), Volume 151 (2000), pp. 1119-1150 | MR | Zbl

[87.] P.-M. Samson Concentration of measure inequalities for Markov chains and $Φ$ -mixing processes, Ann. Probab., Volume 28 (2000), pp. 416-461 | MR | Zbl

[88.] I. N. Sanov On the probability of large deviations of random variables, Select. Transl. Math. Statist. and Probability, Vol. 1, Inst. Math. Statist. and Amer. Math. Soc., Providence, R.I., 1961, pp. 213-244

[89.] B. Seward, Krieger’s finite generator theorem for actions of countable groups I. | arXiv

[90.] P. Shields The Theory of Bernoulli Shifts, Univ. of Chicago Press, Chicago, 1973 | Zbl

[91.] P. Shields The Ergodic Theory of Discrete Sample Paths, 13, Am. Math. Soc., Providence, 1996 | Zbl

[92.] J. Sinaĭ On the concept of entropy for a dynamic system, Dokl. Akad. Nauk SSSR, Volume 124 (1959), pp. 768-771 | MR | Zbl

[93.] J. G. Sinaĭ On a weak isomorphism of transformations with invariant measure, Mat. Sb. (N.S.), Volume 63 (1964), pp. 23-42 | MR

[94.] M. Smorodinsky; J.-P. Thouvenot Bernoulli factors that span a transformation, Isr. J. Math., Volume 32 (1979), pp. 39-43 | MR | Zbl

[95.] E. Szemerédi On sets of integers containing no $k$ elements in arithmetic progression, Acta Arith., Volume 27 (1975), pp. 199-245 | MR | Zbl

[96.] E. Szemerédi Regular partitions of graphs, Problèmes combinatoires et théorie des graphes, Volume 260 (1978), pp. 399-401

[97.] M. Talagrand On Russo’s approximate zero-one law, Ann. Probab., Volume 22 (1994), pp. 1576-1587 | MR | Zbl

[98.] M. Talagrand Concentration of measure and isoperimetric inequalities in product spaces, Inst. Hautes Études Sci. Publ. Math., Volume 81 (1995), pp. 73-205 | MR | Zbl

[99.] M. Talagrand A new look at independence, Ann. Probab., Volume 24 (1996), pp. 1-34 | MR | Zbl

[100.] M. Talagrand Transportation cost for Gaussian and other product measures, Geom. Funct. Anal., Volume 6 (1996), pp. 587-600 | MR | Zbl

[101.] T. Tao Szemerédi’s regularity lemma revisited, Contrib. Discrete Math., Volume 1 (2006), pp. 8-28 | MR | Zbl

[102.] T. Tao The dichotomy between structure and randomness, arithmetic progressions, and the primes, International Congress of Mathematicians, vol. I, Eur. Math. Soc., Zürich, 2007, pp. 581-608

[103.] T. Tao; V. Vu Additive Combinatorics, Cambridge Univ. Press, Cambridge, 2006 | Zbl

[104.] J.-P. Thouvenot Quelques propriétés des systèmes dynamiques qui se décomposent en un produit de deux systèmes dont l’un est un schéma de Bernoulli, Isr. J. Math., Volume 21 (1975), pp. 177-207 | MR | Zbl

[105.] J.-P. Thouvenot Une classe de systèmes pour lesquels la conjecture de Pinsker est vraie, Isr. J. Math., Volume 21 (1975), pp. 208-214 (1974) | MR | Zbl

[106.] J.-P. Thouvenot On the stability of the weak Pinsker property, Isr. J. Math., Volume 27 (1977), pp. 150-162 | MR | Zbl

[107.] J.-P. Thouvenot Entropy, isomorphism and equivalence in ergodic theory, Handbook of Dynamical Systems, vol. 1A, North-Holland, Amsterdam, 2002, pp. 205-238

[108.] J.-P. Thouvenot Two facts concerning the transformations which satisfy the weak Pinsker property, Ergod. Theory Dyn. Syst., Volume 28 (2008), pp. 689-695 | MR | Zbl

[109.] J.-P. Thouvenot Relative spectral theory and measure-theoretic entropy of Gaussian extensions, Fundam. Math., Volume 206 (2009), pp. 287-298 | MR | Zbl

[110.] S. Verdú; T. Weissman The information lost in erasures, IEEE Trans. Inf. Theory, Volume 54 (2008), pp. 5030-5058 | MR | Zbl

[111.] A. M. Vershik Dynamic theory of growth in groups: entropy, boundaries, examples, Usp. Mat. Nauk, Volume 55 (2000), pp. 59-128 | MR | Zbl

[112.] A. M. Vershik The Kantorovich metric: the initial history and little-known applications, Zap. Nauč. Semin. POMI, Volume 312 (2004), pp. 69-85

[113.] A. M. Vershik Dynamics of metrics in measure spaces and their asymptotic invariants, Markov Process. Relat. Fields, Volume 16 (2010), pp. 169-184 | MR | Zbl

[114.] R. Vershynin, High-Dimensional Probability: An Introduction with Applications in Data Science, Cambridge Univ. Press (in press), draft available online at https://www.math.uci.edu/~rvershyn/papers/HDP-book/HDP-book.html.

[115.] S. Watanabe Information theoretical analysis of multivariate correlation, IBM J. Res. Dev., Volume 4 (1960), pp. 66-82 | MR | Zbl

[116.] D. Welsh Codes and Cryptography, Clarendon/Oxford Univ. Press, New York, 1988 | Zbl

Cited by Sources: