On the Statistics of the Number of Fixed-Dimensional Subcubes in a Random Subset of the n-Dimensional Discrete Unit Cube

Svante JANSON, Blair SEIDLER, and Doron ZEILBERGER

Abstract: This paper consists of two indpendent, but related parts. In the first part we show how how to use symbolic computation to derive explicit expressions for the first few moments of the number of implicants that a random Boolean function has, or equivalently the number of fixed-dimensional subcubes contained in a random subset of the ndeimensional cube. These explicit expressions suggest, but do not prove, that these random variables are always asymptotically normal. The second part is a full, human-generated proof, of this asymptotic normality.

Preface

References

Svante Janson, Department of Mathematics, Uppsala University, PO Box 480, SE-751 06 Uppsala,

Sweden. svante.janson@math.uu.se

Blair Seidler and Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: blair.seidler@math.rutgers.edu , DoronZeil@gmail.com .

Written: Feb. 10, 2023.