Carleton University
Technical Report TR-96-11
March 1996
A Correlation Inequality and Its Application to a Word Problem
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Michael S.O. Molloy
Abstract
We give upper bounds for the probability that a random word of a given length contains at least one letter from each member of a given collection of sets of letters. We first show a correlation inequality that bounds the probability of the conjunction of a number of pairwise dependent events. The bound takes into account only pairs of events that are positively correlated, yielding significantly tighter bounds in some interesting cases.