THE MAHONIAN PROBABILITY DISTRIBUTION ON WORDS IS ASYMPTOTICALLY NORMAL

BLAIR SEIDLER, SVANTE JANSON, 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.

1. Introduction

2. Explicit Expressions for Moments of the Number of

Low-Dimensional Subcubes in a Random Subest of the n-dimensional cube

COMING UP

3. Asymptotic Normality

References

[1] W. Feller, An Introduction to Probability Theory and Its Application, volume I, third edition, Wiley, New York, 1968.

Department of Mathematics, Rutgers University, NJ 08854, USA

E-mail address: blair [Dot] seidler [At] math [Dot] rutgers [Dot] edu

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

E-mail address: svante.janson [At] math [Dot] uu [Dot] se
URL: http://www.math.uu.se/∼svante/

Mathematics Department, Rutgers University (New Brunswick), Piscataway, NJ 08854, USA

E-mail address: zeilberg [At] math [Dot] rutgers [Dot] edu

Date: Feb. 10, 2023. Accompanied by Maple package MahonianStat available from

http://www.math.rutgers.edu/∼zeilberg/mamarim/mamarimhtml/mahon.html.

The work of D. Zeilberger was supported in part by the United States of America National Science Foundation. The work of E. R. Canfield was supported in part by the NSA Mathematical Sciences Program.