Aryeh Kontorovich

Let M(n, k, p) denote the maximum probability of the event X1=X2=⋯=Xn=1 under a k-wise independent distribution whose marginals are Bernoulli random variables with mean p. A long-standing question is to calculate M(n, k, p) for all values of n, k, p. This problem has been partially addressed by several authors, primarily with the goal of answering asymptotic questions. The present paper focuses on obtaining exact expressions for this probability. For a wide range of parameters n, k, and p, we find exact expressions for M(n, k, p). We also present results from several numerical studies, giving rise to eight open conjectures.