The Match Set of a Random Permutation Has the FKG Property
Fishburn, Peter C. ; Doyle, Peter G. ; Shepp, L. A.
Ann. Probab., Tome 16 (1988) no. 4, p. 1194-1214 / Harvested from Project Euclid
We prove a conjecture of Joag-Dev and Goel that if $M = M(\sigma) = \{i: \sigma(i) = i\}$ is the (random) match set, or set of fixed points, of a random permutation $\sigma$ of $1,2,\ldots, n$, then $f(M)$ and $g(M)$ are positively correlated whenever $f$ and $g$ are increasing real-valued set functions on $2^{\{1,\ldots, n\}}$, i.e., $Ef(M)g(M) \geq Ef(M)Eg(M)$. No simple use of the FKG or Ahlswede-Daykin inequality seems to establish this, despite the fact that the FKG hypothesis is "almost" satisfied. Instead we reduce to the case where $f$ and $g$ take values in $\{0, 1\}$, and make a case-by-case argument: Depending on the specific form of $f$ and $g$, we move the probability weights around so as to make them satisfy the FKG or Ahlswede-Daykin hypotheses, without disturbing the expectations $Ef, Eg, Efg$. This approach extends the methodology by which FKG-style correlation inequalities can be proved.
Publié le : 1988-07-14
Classification:  Random permutations,  fixed points,  FKG inequality,  Ahlswede-Daykin inequality,  correlated functions,  60B15,  60E15,  06A10,  06D99
@article{1176991685,
     author = {Fishburn, Peter C. and Doyle, Peter G. and Shepp, L. A.},
     title = {The Match Set of a Random Permutation Has the FKG Property},
     journal = {Ann. Probab.},
     volume = {16},
     number = {4},
     year = {1988},
     pages = { 1194-1214},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1176991685}
}
Fishburn, Peter C.; Doyle, Peter G.; Shepp, L. A. The Match Set of a Random Permutation Has the FKG Property. Ann. Probab., Tome 16 (1988) no. 4, pp.  1194-1214. http://gdmltest.u-ga.fr/item/1176991685/