Exact expressions for the maximal probability that all $k$-wise independent bits are 1

Daniel Berend, Philip Ernst, Aryeh Kontorovich, Rishi KumararXiv 2024 · DOI · arXiv

Abstract

In the study of $k$-wise independent distributions, a fundamental challenge is determining the maximum possible probability that all $n$ Bernoulli random variables in a set are simultaneously equal to 1. This value, denoted as $M(n, k, p)$, where $p$ is the marginal probability of each bit, has significant implications for the derandomization of algorithms. While previous research has focused on asymptotic bounds, this paper provides the first exact, closed-form formulas for $M(n, k, p)$ in the regimes where $p$ is near 0 or near 1. By leveraging Linear Programming (LP) duality and Bonferroni polynomials, the authors identify the piecewise polynomial nature of this probability and provide a roadmap for solving the problem across the entire interval of $p$.

Introduction

In theoretical computer science and probability theory, "weak" independence is a powerful tool. While fully independent random bits are mathematically simple, they are computationally expensive to generate. Consequently, researchers often utilize $k$-wise independent distributions, where any subset of $k$ bits behaves as if they were independent, even if the group as a whole does not.

A critical question for the efficiency of derandomized algorithms is: what is the worst-case scenario for these distributions? Specifically, if we have $n$ bits that are $k$-wise independent, each with a probability $p$ of being 1, what is the maximum possible probability $M(n, k, p)$ that all $n$ bits are 1? Historically, this question has been addressed through upper bounds and asymptotic estimates. This paper shifts the focus toward obtaining exact, closed-form expressions.

Methodology

Linear Programming Formulation

The authors frame the search for $M(n, k, p)$ as a Linear Programming (LP) problem. They define $v_i$ as the probability that exactly $i$ bits are set to 1. The objective is to maximize $v_n$ subject to constraints that enforce $k$-wise independence. These constraints are expressed as moments of the distribution, ensuring that for any subset of size $j \le k$, the probability that all bits in that subset are 1 is exactly $p^j$.

Dual Feasibility and Bonferroni Polynomials

To solve the LP, the researchers analyze the dual problem, utilizing the framework established by Boros and Prékopa regarding dual feasible bases. A central component of their analysis involves Bonferroni inequalities and their associated polynomials. These mathematical tools provide alternating sums that bound the probability of a union of events, allowing the authors to construct tight upper bounds and identify optimal solutions.

Symmetry and Realizability

The study exploits a fundamental mathematical symmetry: the behavior of the distribution for $p$ near 1 is a mirrored version of the behavior for $p$ near 0. Furthermore, the authors distinguish between "dual feasible" bases and "realizable" bases—those that correspond to actual, valid probability distributions. They found that realizable bases are highly concentrated and follow a specific lexicographic order.

Numerical Investigations

While the paper is primarily theoretical, the authors conducted extensive numerical studies to validate their formulas and generate conjectures. They calculated exact values for various configurations, including:

  • $k=4$ for $n$ up to 500
  • $k=6$ for $n$ up to 200
  • $k=8$ for $n$ up to 100
  • $k=10$ for $n$ up to 50

These computations revealed that $M(n, k, p)$ is not a single smooth curve but a "spline-like" sequence of different polynomials connected at specific "exceptional points."

Key Insights and Results

The $p^k$ Threshold

A significant result of this work is Theorem 2.2, which proves that if $p$ is sufficiently small ($p \le 1/(n-k+1)$), the maximum probability $M(n, k, p)$ is exactly $p^k$. This result generalizes earlier findings for $k=2$ and $k=3$ to all values of $k$.

Exact Formulas for Boundary Regimes

The paper provides the first exact polynomials for the following intervals:

  • Near Zero: The exact expressions for the first and second intervals of $p$ starting from $p=0$.
  • Near One: The closed-form expressions for the last and second-to-last intervals as $p$ approaches 1.

Improved Bounds

Through Theorem 2.1, the authors establish new, tighter upper bounds for $M(n, k, p)$ across the entire range of $p \in [0, 1]$ using Bonferroni polynomials, surpassing previous estimates in precision.

Conclusion and Future Work

This research provides a definitive solution for $M(n, k, p)$ at the boundaries of $p$. However, a universal "master formula" for all $n, k, p$ remains elusive due to the increasing complexity and number of polynomial pieces as $n$ and $k$ grow.

The authors conclude with eight open conjectures based on their numerical data. These conjectures regarding the rational nature of exceptional points and the transition of realizable bases provide a clear trajectory for future research to complete the mathematical map of $k$-wise independence.

Summary updated

Abstract

Let $M(n, k, p)$ denote the maximum probability of the event $X_1 = X_2 = \cdots = X_n=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 question 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. To this end, we provide closed-form formulas of $M(n,k,p)$ for $p$ near 0 as well as $p$ near 1.
BibTeX
@misc{berend2024exact,
  author = {Daniel Berend and Philip Ernst and Aryeh Kontorovich and Rishi Kumar},
  title = {{Exact expressions for the maximal probability that all $k$-wise independent bits are 1}},
  year = {2024},
  eprint = {2407.18688},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.18688},
}
Figure