Ramsey Theory and Sequences of Random Variables

Abstract

We consider probability spaces which contain a family {E_A[ratio ]A⊆{1, 2, …, n}, [mid ]A[mid ]=k} of events indexed by the k-element subsets of {1, 2, …, n}. A pair (A, B) of k-element subsets of {1, 2, …, n} is called a shift pair if the largest k−1 elements of A coincide with the smallest k−1 elements of B. For a shift pair (A, B), Pr[AB¯] is the probability that event E_A is true and E_B is false. We investigate how large the minimum value of Pr[AB¯], taken over all shift pairs, can be. As n→∞, this value converges to a number λ_k, with ½−1/2k+2[les ]λ_k[les ] ½−1/4k+2. We show that λ_k is a strictly increasing function of k, with λ₁=¼ and λ₂=1/3.

For k=1, our results have the following natural interpretation. If a fair coin is tossed repeatedly, and event E_i is true when the ith toss is heads, then for all i and j with i<j, Pr[E_iĒ_j]=¼. Furthermore, as we show in this paper, for any ε>0, there is an n such that for any sequence E₁, E₂, …, E_n of events in an arbitrary probability space, there are indices i<j with Pr[E_iĒ_j]<¼+ε. The results and techniques we develop in this research, together with further applications of Ramsey theory, are then used to show that the supremum of fractional dimensions of interval orders is exactly 4, answering a question of Brightwell and Scheinerman.

Generalizing the ¼+ε result to random variables X₁, X₂, …, X_n with values in an m-element set, we obtain a finite version of de Finetti's theorem without the exchangeability hypothesis: for any fixed m, k and ε, every sufficiently long sequence of such random variables has a length-k subsequence at variation distance less than ε from an i.i.d. mix.