How much are increasing sets positively correlated?
type: Item
instance of: scholarly article
title: How much are increasing sets positively correlated?
zbMATH Open document ID: 0861.05008
DOI: 10.1007/BF01844850
author: Michel Talagrand
published in: Combinatorica
publication date: 1997-05-04T00:00:00Z
review text: The author studies sets \(A\) of sequences consisting of 0 and 1 of length \(n\) (\(n\) a positive integer). Such a set \(A\) is called increasing (or upward directed) if for each sequence \(x\) in \(A\) every sequence \(y\) that is componentwise greater or equal to \(x\) is also in the set \(A\). He introduces the normalized counting measure \(\mu(A)=2^{-n}\text{card}(A)\), where \(\text{card}(A)\) is the cardinality of \(A\). If \(x\) is a sequence, the sequence \(T_i(x)\) is obtained from \(x\) by changing the \(i\)th coordinate. For a set \(A\) the set \(A_i\) is defined as \(A_i= \{x\) in \(A\mid T_i(x)\) not in \(A\}\). The main theorem states the following: If \(\varphi(x)\) is defined for \(0\leq x\leq 1\) as \(\varphi(x)=x/\log(e/x)\), then for some universal constant \(K\) and for all \(n\) and all increasing sets \(A\), \(B\) of sequences of 0 and 1 of length \(n\) we have that \[ \mu(A\cap B)- \mu(A)\mu(B)\geq 1/K^*\varphi\Biggl(\sum_{i\leq n}\mu(A_i)\mu(B_i)\Biggr). \] The author shows that this lower bound is more or less tight by giving an example from which it is clear that it is of the right order. The proof of the theorem is given starting from some relatively easy formulas followed by elaborate manipulations on them using Fubini's theorem and the Cauchy-Schwarz inequality several times finally reaching the aimed result.
Mathematics Subject Classification ID: 05A20
Mathematics Subject Classification ID: 28A35
zbMATH DE Number: 936875
zbMATH Keywords: correlation
zbMATH Keywords: sequences
zbMATH Keywords: normalized counting measure
zbMATH Keywords: increasing sets
reviewed by: Herman J. Tiersma
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 936875