Measure concentration and the weak Pinsker property

Austin, Tim

doi:10.1007/s10240-018-0098-3

Austin, Tim

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

Résumé

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.

Reçu le : 2017-10-16
Accepté le : 2018-02-03
Première publication : 2018-02-15
Publié le : 2018-11-09

DOI : 10.1007/s10240-018-0098-3

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

TY  - JOUR
AU  - Austin, Tim
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  - http://archive.numdam.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 Austin, Tim
%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 http://archive.numdam.org/articles/10.1007/s10240-018-0098-3/
%R 10.1007/s10240-018-0098-3
%G en
%F PMIHES_2018__128__1_0

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

Bibliographie
Cité par

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

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

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

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

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

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

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

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

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

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

[11.] Cover, T. M.; Thomas, J. A. 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.] Csiszár, I. Information-type measures of difference of probability distributions and indirect observations, Studia Sci. Math. Hung., Volume 2 (1967), pp. 299-318 | MR | Zbl

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

[15.] Danilenko, A. I.; Park, K. K. 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.] Dembo, A. Information inequalities and concentration of measure, Ann. Probab., Volume 25 (1997), pp. 927-939 | MR | Zbl

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

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

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

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

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

[22.] Furstenberg, H. 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.] Gangbo, W.; McCann, R. J. The geometry of optimal transportation, Acta Math., Volume 177 (1996), pp. 113-161 | MR | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[43.] Kieffer, J. C. 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.] Kieffer, J. C. A simple development of the Thouvenot relative isomorphism theory, Ann. Probab., Volume 12 (1984), pp. 204-211 | MR | Zbl

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

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

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

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

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

[51.] Ledoux, M. 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.] Ledoux, M. On Talagrand’s deviation inequalities for product measures, ESAIM Probab. Stat., Volume 1 (1995), pp. 63-87 | MR | Zbl

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

[54.] Levin, V. L. 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.] Lindenstrauss, E.; Peres, Y.; Schlag, W. 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.] Linial, N.; Samorodnitsky, A.; Wigderson, A. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, Combinatorica, Volume 20 (2000), pp. 545-568 | MR | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[81.] Radhakrishnan, J. Entropy and counting (Mishra, J., 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.] Rahe, M. Relatively finitely determined implies relatively very weak bernoulli, Can. J. Math., Volume 30 (1978), pp. 531-548 | MR | Zbl

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

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

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

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

[88.] Sanov, I. N. 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.] Shields, P. The Theory of Bernoulli Shifts, Univ. of Chicago Press, Chicago, 1973 | Zbl

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

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

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

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

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

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

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

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

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

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

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

[102.] Tao, T. 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.] Tao, T.; Vu, V. Additive Combinatorics, Cambridge Univ. Press, Cambridge, 2006 | Zbl

[104.] Thouvenot, J.-P. 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.] Thouvenot, J.-P. 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.] Thouvenot, J.-P. On the stability of the weak Pinsker property, Isr. J. Math., Volume 27 (1977), pp. 150-162 | MR | Zbl

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

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

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

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

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

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

[113.] Vershik, A. M. 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.] Watanabe, S. Information theoretical analysis of multivariate correlation, IBM J. Res. Dev., Volume 4 (1960), pp. 66-82 | MR | Zbl

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

Cité par Sources :