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 independent, but related parts. In the first part we show 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 fixeddimensional subcubes contained in a random subset of the n-dimensional cube. These explicit expressions suggest, but do not prove, that these random variables are always asymptotically normal.

The second part presents a full, human-generated proof, of this asymptotic normality, first proved by Urszula Konieczna.

1. Introduction

1.1. Motivation. Recall that an implicant of a Boolean function in n variables, f(x_{1}, …, x_{n}) is a pure disjunction

x_{i_{1}}^{a_{1}} ∧ x_{i_{2}}^{a_{2}} ∧ ⋯ ∧ x_{i_{r}}^{a_{r}},  (1.1)

that implies it. Here 1 ≤ i_{1} < … i_{r} ≤ n, a_{1}, …, a_{r} ∈ {0, 1}, z^{1} = z, and z^{0} = z̄ (the negation of z).

Fix r and let n vary. We are interested in the statistical distribution of the random variable number of implicants of length n − r in a uniformlyat-random Boolean function of n variables. Clearly, when r = 0 it is nothing but the good old (fair) binomial distribution with 2^{n} fair coin-tosses, B(\frac{1}{2}, 2^{n}).

Equivalently, for a random subset of the n-dimensional cube, we are interested in the statistical distribution of the number of r-dimensional subcubes properly contained in it.

We would like to have explicit expressions, in n, for the k^{th} moment of this random variable, for as many as possible r and k. This turns out to be a challenging symbolic-computational problem that we will address in the first part of this paper.

Date: Feb. 17, 2023.

Accompanied by Maple package SMCboole.txt, available from http://www.math.rutgers.edu/∼zeilberg/mamarim/mamarimhtml/subcubes.html.

In the second part we consider asymptotics as n → ∞. It was proved by Urszula Konieczna [3] that for each fixed r, this distribution is asymptotically normal. We will reprove this by a somewhat different method which leads to a simple proof.

1.2. Our Random Variables. The sample space is the set of subsets of {0, 1}^{n}, that has cardinality 2^{2^{n}}.

Let’s define our random variables formally. For a (uniformly-at-) random subset S, of {0, 1}^{n}, and fixed r, define the random variable

X_{r}(S) := number of r-dimensional subcubes of S.  (1.2)

For example, if n = 3 and

S = {000, 001, 010, 011, 100, 111},  (1.3)

we have

X_{0}(S) = 6, X_{1}(S) = 6, X_{2}(S) = 1, X_{3}(S) = 0.  (1.4)

We would like to get, for as many pairs (k, r) as possible, explicit expressions in n, for the k-th moment of X_{r}, i.e. for

f_{kr}(n) := 𝔼[X_{r}^{k}](n).  (1.5)

2. Explicit Expressions for Moments of the Number of Low-Dimensional Subcubes in a Random Subest of the n-dimensional cube

2.1. The Expectation and Variance. The first moment, aka expectation, aka mean, aka average, is easy, using linearity of expectation.

For any specific subcube C of {0, 1}^{n}, define the atomic random variable, X_{C}, on subsets, S, of {0, 1}^{n} as follows.

X_{C}(S) = \begin{cases}1, & if C ⊂ S; \\ 0, & otherwise. \end{cases}  (2.1)

Let C(n, r) be the set of all \binom{n}{r}2^{n−r} r-dimensional subcubes of \{0, 1\}^{n}. Then, of course,

X_{r}(S) = ∑_{C∈C(n,r)} X_{C}(S).  (2.2)

Applying the expectation functional and using the linearity of expectation, we get that the average, let’s call it μ_{r}(n), is

μ_{r}(n) = 𝔼[X_{r}] = 𝔼 [ ∑_{C∈C(n,r)} X_{C} ] = ∑_{C∈C(n,r)} 𝔼[X_{C}].  (2.3)

STATISTICS OF THE NUMBER OF SUBCUBES IN SUBSETS OF THE N-CUBE 3

Now the probability that a random subset of {0, 1}^{n} contains an r-dimensional subcube C is (\frac{1}{2})^{2^{r}}, since for each of its vertices, the chance of it belonging to S is \frac{1}{2}, and by independence the probability that all its 2^{r} vertices belong to S is indeed \frac{1}{2^{2^{r}}}. The probability that X_{C}(S) = 0 is of course 1 − (\frac{1}{2})^{2^{r}}, hence

𝔼[X_{C}] = 1 · (\frac{1}{2})^{2^{r}} + 0 · (1 − (\frac{1}{2})^{2^{r}}) = (\frac{1}{2})^{2^{r}} .  (2.4)

Going back to equation (2.3) we have

μ_{r}(n) = ∑_{C∈C(n,r)} 𝔼[X_{C}] = ∑_{C∈C(n,r)} \frac{1}{2^{2^{r}}} = |C(n, r)| · \frac{1}{2^{2^{r}}} = \frac{\binom{n}{r}2^{n−r}}{2^{2^{r}}} . (2.5)

In a beautiful paper, Thanatipanonda [5] derived an explicit expression for the general second moment, for every r-dimensional cube.

Thanatipanoda’s General Formula for the Second Moment:

𝔼[X_{r}^{2}] = ∑_{i=0}^{r} \frac{n!2^{n−i}}{i!(r − i)!^{2}(n − 2r + i)!2^{2^{r+1}}} · (2^{2^{i}} − 1) + \frac{[\binom{n}{r}2^{n−r}]^{2}}{2^{2^{r+1}}} , (2.6)

from which immediately follows, using [𝔼(X_{r} − μ_{r}(n))^{2}] = 𝔼[X_{r}^{2}] − μ_{r}(n)^{2}, the following formula.

Thanatipanoda’s General Formula for the Variance:

Var(X_{r}) = ∑_{i=0}^{r} \frac{n!2^{n−i}}{i!(r − i)!^{2}(n − 2r + i)!2^{2^{r+1}}} · (2^{2^{i}} − 1).  (2.7)

Note that the variance is a polynomial in (n, 2^{n}) of degree 2r in n and degree 1 in 2^{n}.

2.2. Higher Moments.

2.2.1. Edges. Thanatipanonda was unable to get such a general formula for higher moments, but did get 𝔼[X_{1}^{3}], from which he immediately deduced that the third central moment (or third-moment-about-the-mean) of X_{1} is

𝔼[(X_{1} − μ_{1}(n))^{3}] = \frac{3n^{3}2^{n}}{64} .  (2.8)

Using the symbolic-computational algorithms to be described in the next section, we managed to derive the following explicit formulas

𝔼[(X_{1} − μ_{1}(n))^{4}] = \frac{n2^{n}}{1024}(12n^{3}2^{n} + 12n^{2}2^{n} + 40n^{3}
+ 3n2^{n} − 48n^{2} + 12n − 16),  (2.9)

𝔼[(X_{1} − μ_{1}(n))^{5}] = \frac{5n^{3}2^{n}}{1024} (6n^{2}2^{n} + 3n2^{n} + 4n^{2} − 24n + 8) ,  (2.10)

𝔼[(X_{1}−μ_{1}(n))^{6}] =
\frac{n2^{n}}{32768} · (120n^{5} (2^{n})^{2} + 180n^{4} (2^{n})^{2} + 1920n^{5}2^{n} + 90n^{3} (2^{n})^{2}
− 840n^{4}2^{n} − 1792n^{5} + 15n^{2} (2^{n})^{2} − 360n^{3}2^{n} − 5280n^{4}
− 300n^{2}2^{n} + 3840n^{3} − 240n2^{n} + 3840n^{2} − 6720n + 4864). (2.11)

It follows that the scaled moments about the mean for the third, fourth, fifth, and sixth moments, converge, as n → ∞, to 0, 3, 0, 15 respectively, the respective moments of the normal distribution, indicating that the random variable X_{1} (the number of edges contained in S) is probably asymptotically normal. To fully prove asymptotic normality, of course, we need to prove it for all moments, not just for the first six.

2.2.2. Squares. We only managed to get explicit expressions for the third and fourth moments for X_{2}.

𝔼[(X_{2} − μ_{2}(n))^{3}] = \frac{2^{n}n (n − 1)}{32768} (9n^{4} + 6n^{3} + 21n^{2} − 16n − 34) , (2.12)

𝔼[(X_{2} − μ_{2}(n))^{4}] =
\frac{2^{n}n (n − 1)}{4194304} · (12n^{6}2^{n} + 12n^{5}2^{n} + 520n^{6} + 24n^{4}2^{n} − 24n^{5} − 12n^{3}2^{n} + 1272n^{4}
− 9n^{2}2^{n} − 840n^{3} − 27n2^{n} − 5232n^{2} − 2768n + 240). (2.13)

2.2.3. 3-dimensional cubes. We only managed to get an explicit expression for the third moment for X_{3}.

𝔼[(X_{3} − μ_{3}(n))^{3}] =

\frac{2^{n}n (n − 1) (n − 2)}{2415919104}(14n^{6} + 24n^{5} + 479n^{4} + 2046n^{3}
+ 6779n^{2} + 15444n − 23112).  (2.14)

2.3. Our Method. Obviously we did not derive these formulas by hand. We had to teach our computer how to find them. It also uses linearity of expectation, but with higher moments things get very complicated. Recall that

X_{r}(S) = ∑_{C∈C(n,r)} X_{C}(S).  (2.15)

Hence, the k-th moment is

𝔼 [(X_{r})^{k}] = 𝔼 [( ∑_{C∈C(n,r)} X_{C}(S))^{k}]

= ∑_{[C_{1},...,C_{k}]∈C(n,r)^{k}} 𝔼[X_{C_{1}}X_{C_{2}} ⋯ X_{C_{k}}].  (2.16)

So we sum over all (\binom{n}{r}2^{n−r})^{k} members of C(n, r)^{k}. Since the product X_{C_{1}}(S)X_{C_{2}}(S) ⋯ X_{C_{k}}(S) = 1 if each of C_{1}, C_{2}, …, C_{k} is properly included in S (i.e. if each vertex in C_{1} ∪ C_{2} ∪ … C_{k} belongs to S), and 0 otherwise, the contribution, or weight, due to each such term is

Weight([C_{1}, C_{2}, …, C_{k}]) = 𝔼 [X_{C_{1}}X_{C_{2}} ⋯ X_{C_{k}}] = \frac{1}{2^{|C_{1}∪C_{2}∪...C_{k}|}} . (2.17)

2.3.1. Data Structure. Every r-dimensional subcube of {0, 1}^{n} has the form

C = {(x_{1}, …, x_{n}) ∈ {0, 1}^{n} | x_{i_{1}} = α_{i_{1}}, …, x_{i_{n−r}} = α_{i_{n−r}}},  (2.18)

for some 1 ≤ i_{1} < i_{2} < ⋯ < i_{n−r} ≤ n and (α_{i_{1}}, … α_{i_{n−r}}) ∈ {0, 1}^{n−r}. A good way to represent it on a computer is as a row-vector of length n, in the alphabet {0, 1, ∗}, where the entries corresponding to i_{1}, i_{2}, …, i_{n−r} have α_{i_{1}}, ….α_{i_{n−r}} respectively and the remaining r entries are filled with wild cards, denoted by ∗.

For example, if n = 7 and r = 3, the 3-dimensional cube

{(x_{1}, …, x_{7}) ∈ {0, 1}^{7} | x_{2} = 1, x_{4} = 1, x_{5} = 0, x_{7} = 1},  (2.19)

is represented by

∗1 ∗ 10 ∗ 1.  (2.20)

We are trying to find a weighted count of ordered k-tuples of r-dimensional subcubes. The natural data structure for these is the set of k by n matrices in the ‘alphabet’ {0, 1, ∗} where every row has exactly r ‘wildcards’, *.

Let’s call this set of matrices, that correspond to C(n, r)^{k}, C(n, r, k).

For any specific, numeric n, there are ‘only’ (2^{n−r}\binom{n}{r})^{k} of these matrices, and for each and every one of them one can find the cardinality of the union of the corresponding subcubes, let’s call it v, and add to the running sum \frac{1}{2^{v}}. But we want to do it for symbolic n, i.e. for ‘all’ n. We will soon see how, for each specific (numeric) r and k this can be done in principle, but only for relatively small r and k in practice. But let’s try and push it as far we can. An interesting consequence of our algorithm is the precise degree in n and 2^{n} of the expression for 𝔼[X_{r}^{k}](n).

2.3.2. The Kernel. A key object in our approach is the kernel. Given a k × n matrix M in the alphabet {0, 1, ∗} let’s call a column active if it contains at least one ‘∗’. Note that the matrix has exactly k · r ‘∗’s, hence the number of active columns, let’s call it a, is between r and k · r. ^{1} The kernel of M is the submatrix of M consisting of its active columns.

1More generally, if we want to find an expression for the mixed moment 𝔼[X_{r_{1}} ⋯ X_{r_{k}}] the number of active columns is between max(r_{1}, …, r_{k}) and r_{1} + ⋯ + r_{k}.

Let C_{a}(n, r, k) be the subset of C(n, r, k) matrices with exactly a active columns. We will call such a matrix in canonical form if the active columns are occupied by the a leftmost columns (i.e. its kernel is contiguous starting in the first column). Let’s denote by \overline{C}_{a}(n, r, k) the set of such matrices in canonical form. Obviously, there are \binom{n}{a} ways to choose which of the n columns are active and hence

Weight(C(n, r, k)) = ∑_{a=r}^{rk} Weight(C_{a}(n, r, k))

= ∑_{a=r}^{rk} \binom{n}{a} Weight(\overline{C}_{a}(n, r, k)).  (2.21)

For any set, S, Weight(S) is the sum of the weights of its members. Note that this has degree rk in n.

It remains to do a weighted-count, where every matrix gets ‘credit’ 1/2^{v}, where v is the cardinality of the union of the corresponding subcubes represented by the k rows, for the set \overline{C}_{a}(n, r, k), of matrices in canonical form. Note that there are only finitely many choices for the a leftmost columns, i.e. the set of k × a matrices in the alphabet {0, 1, ∗} with the property that every column has at least one ‘∗’, and every row has exactly r ‘∗’s. These can be divided into equivalence classes obtained by permuting rows and columns and transposing 0 and 1 in any given column. Once these are sorted into equivalence classes, one needs only examine one representative, and then multiply the weight by the cardinality of the class.

But what about the n − a rightmost columns? There are 2^{k(n−a)} possible submatrices; the alphabet here is {0, 1}. Almost all of these have distinct rows, more precisely,

\binom{2^{n−a}}{k}k!  (2.22)

of them, and these will produce the smallest possible weight in conjunction with any kernel. The other extreme is that all the rows of the submatrix consisting of the n − a rightmost columns are identical, and then there are only 2^{n−a} choices to fill them in.

In general, every such member of \overline{C}_{a}(n, r, k), determines a set partition of the set of rows {1, …, k}, where two rows are roomates if they have the same last n − a entries. If that set-partition has m members 1 ≤ m ≤ k, then the number of choices of assigning different 0 − 1 vectors of length n − a to each of the parts of the set-partition is

\binom{2^{n−a}}{m}m!.  (2.23)

Now for each a and for each set-partition, we let the computer generate the finite set of k × a matrices in the alphabet {0, 1, ∗}. Each of the members of the set partition has its own submatrix, and we ask our computer to kindly find the number of vertices in the corresponding union of subcubes corresponding to each member of the examined set partition. Since they are disjoint, we add them up, getting v for that particular pair (matrix, set-partition), giving credit 1/2^{v}.

2.3.3. Implementation. All this is implemented in the Maple package SMCboole.txt, available from:

https://sites.math.rutgers.edu/~zeilberg/tokhniot/SMCboole.txt

In particular ‘Moms(A,n);’, for any list of non-negative integers A = [r_{1}, … r_{k}] gives you the mixed moment 𝔼[X_{r_{1}} ⋯ X_{r_{k}}]. For example, to get the third moment of the number of edges (i.e. 1-dimensional subcubes) type Moms([1,1,1],n); , which very quickly returns:

\frac{2^{n}n^{2} ((2^{n})^{2} n + 12 2^{n}n + 6 2^{n} + 24n)}{512}.  (2.24)

To get the third moment of the number of squares (i.e. 2-dimensional subcubes), type Moms([2,2,2],n); , getting

\frac{2^{n}n (n − 1)}{2097152} · ( (2^{n})^{2} n^{4} − 2 (2^{n})^{2} n^{3} + 48 2^{n}n^{4} + (2^{n})^{2} n^{2}
+ 576n^{4} + 24 2^{n}n^{2} + 384n^{3} − 72 2^{n}n
+ 1344n^{2} − 1024n − 2176).  (2.25)

The third moment of the number of 3-dimensional cubes takes a bit longer, and we were unable to compute the fourth moment of the number of 3dimensional cubes; it took too much time and too much space.

More informative for statistical purposes are the central moments, 𝔼[(X_{r}− μ_{r}(n))^{k}], that Maple easily derives, using linearity of expectation from the pure moments. The function call for this is MOMrk(r,k,n); where r and k are numeric but n is a symbol denoting the dimension of the ambient cube.

To get the explicit expression given above for the third through sixth moments for the number of edges, the third and fourth moments for the number of squares, and the third moment for the number of 3-dimensional subcube (all about the mean) we typed:

  MOMrk(1,3,n); , MOMrk(1,4,n); , MOMrk(1,5,n); , MOMrk(1,6,n); ,
  MOMrk(2,3,n); , MOMrk(2,4,n); ,
  MOMrk(3,3,n);

respectively. To our chagrin, ‘MOMrk(3,4,n);’ took too long.

2.3.4. Consequence of the algorithm. : The k-th moment of X_{r} is a bivariate polynomial in (n, 2^{n}) of degree k r in n and degree k in 2^{n} .

This raises the theoretical possibility (in God’s computer) of finding these expressions by pure brute force. The generic polynomial in (n, 2^{n}) of degree kr in n and degree k in 2^{n} has (1 + kr)(1 + k) ‘degrees of freedom’. So using undetermined coefficients we need to generate a table of 𝔼[X_{r}^{k}](n) for 1 ≤ n ≤ (1+kr)·(1+k). After gathering the data, we use linear algebra to solve a system of (1 + kr) · (1 + k) equations with that many unknowns. For each specific n = n_{1} there are ‘only’ 2^{2^{n_{1}}} subsets, and for each of them we can ask how many r-dimensional subcubes do they contain, raise it to the k-th power and take the average. Alas, 2^{2^{5}} is already big enough, so only God’s computer, with practically infinite time and space, can carry this brute force approach.

3. Asymptotic Normality

As said in the introduction, asymptotic normality of X_{r} was proved by Urszula Konieczna [3]. The random variable X_{r} depends on n, and for emphasis, we denote it in the sequel by X_{n,r}. We may then state the result as follows, where N(0, 1) denotes the standard normal distribution.

Theorem 3.1 ([3]). For every fixed r ≥ 0, we have as n → ∞

\frac{X_{n,r} − μ_{r}(n)}{\sqrt{Var(X_{n,r})}} ⟶^{d} N(0, 1)  (3.1)

with convergence in distribution and of all moments.

As already noted at the very beginning of this paper, the case r = 0 is well known, since then the variables X_{C} are independent and this becomes an instance of the central limit theorem for binomial variables, known since a pamphlet by de Moivre in 1733. (This case can be used as a sanity check in the arguments below.)

The proof in [3] is based on the method of moments. We will in this section survey how a variation of this method, based on cumulants and dependency graphs leads to a quick proof with almost no calculations.

Remark 3.2. Urszula Konieczna [3] considered a more general case where each subcube appears with probability p ∈ (0, 1), where p = p(n) may depend on n, and showed asymptotic normality for a large range of p(n). A special case, not including the case p = \frac{1}{2} treated here, was earlier shown by Karl Weber [6]. This extension can also be treated by the method below, but for simplicity we continue to consider only the case p = \frac{1}{2} discussed in Section 2.

The aim is thus to show that the leading terms in the expressions for the central moments 𝔼[(X_{n,r} −μ_{r}(n))^{k}] are what we would expect from a normal distribution, or, more formally, that the scaled central moments

𝔼 [(\frac{X_{n,r} − μ_{r}(n)}{\sqrt{Var(X_{n,r})}})^{k}]  (3.2)

converge as n → ∞ to the corresponding moment 𝔼[Z^{k}] of a standard normal random variable Z, for every fixed r ≥ 0 and k ≥ 1. Then, the random variables X_{n,r} are asymptotically normal by the method of moments.

We thus want to find the leading term of the moment (3.2). In Section 2, we computed the central moments from the pure moments. This involves massive cancellation of high-order terms, and is less suitable for a (human) proof for general k.

As a first step, we may modify (2.16) and instead expand the central moment as

𝔼[(X_{n,r} − μ_{r}(n))^{k}] = ∑_{[C_{1},...,C_{k}]∈C(n,r)^{k}} 𝔼[(X_{C_{1}} − μ) ⋯ (X_{C_{k}} − μ)], (3.3)

where μ = 𝔼[X_{C}] is given by (2.4). Note that two variables X_{C_{1}} and X_{C_{2}} are independent if C_{1} ∩ C_{2} = ∅. In particular, for k = 2, all such terms in the sum in (3.3) vanish; this leaves only Θ(n^{2r}2^{n}) terms of the Θ(n^{2r}2^{2n}) terms in the full sum, or in (2.16), which is reflected in the leading terms in (2.6) and (2.7).

For higher moments, we can obtain a further reduction by considering cumulants (also called semiinvariants) instead of moments. We describe this briefly, referring to e.g. [4] or [2, pp. 145–149] for details. In general, if Y is a random variable with moments m_{k} := 𝔼[Y^{k}] and moment generating function ∑_{k=0}^{∞} m_{k}t^{k}/k!, then the cumulants κ_{k} = κ_{k}(Y) are the coefficients of the generating function

∑_{k=1}^{∞} κ_{k} \frac{t^{k}}{k!} := log (∑_{k=0}^{∞} m_{k} \frac{t^{k}}{k!}) .  (3.4)

(The generating functions can be regarded as formal power series.) Moreover, this generalizes to mixed cumulants κ_{k}(Y_{1}, …, Y_{k}) of several random variables. This means that there are algebraic relations: each cumulant κ_{k} is a polynomial in the moments m_{ℓ} of order ℓ ≤ k, and conversely, and this generalizes to mixed cumulants and moments. For example, κ_{1} = m_{1} = 𝔼 Y, and κ_{2} = m_{2} − m_{1}^{2} = Var(Y), and the mixed cumulant κ(Y_{1}, Y_{2}) = 𝔼[Y_{1}Y_{2}] − 𝔼[Y_{1}] 𝔼[Y_{2}], the covariance of Y_{1} and Y_{2}.

A convenient property of cumulants is that a normal distribution N(μ, σ^{2}) has moment generating function exp(μt+ \frac{σ^{2}}{2} t^{2}), and thus by (3.4) cumulants κ_{k} = 0 for k ≥ 3. Consequently, to show that a normalized sequence of random variables is asymptotically normal, it suffice to show that each cumulant κ_{k} with k ≥ 3 converges to 0.

The mixed cumulants are multilinear, and thus we have an analog of (2.16) and (3.3):

κ_{k}(X_{n,r}) = κ(X_{n,r}, …, X_{n,r}) = ∑_{[C_{1},...,C_{k}]∈C(n,r)^{k}} κ(X_{C_{1}}, …, X_{C_{k}}). (3.5)

We can here reduce the number of terms in the sum by a general property of cumulants: If there is a partition {1, …, k} = I ∪ J into two non-empty sets I and J such the two families of random variables (Y_{i} | i ∈ I) and (Y_{j} | j ∈ J) are independent of each other, then the mixed cumulant κ(Y_{1}, …, Y_{k}) = 0. (Informally, this means that the kth cumulant κ_{k}(X_{n,r}) can be seen as some kind of measure of kth order dependencies in the sum (2.2), with lower order dependencies removed.)

As noticed above, each of our variables X_{C} is independent of most of the others. We need to keep track of not just pairwise independence, but also independence between families of such variables; it is then convenient to use the notion of dependency graphs.

Definition. Let (Y_{α})_{α∈A} be a family of random variables, with some arbitrary index set A. A dependency graph for this family is a graph Γ with vertex set A, such that if I and J are two disjoint subsets of A such that there is no edge in Γ with one endpoint in I and the other in J, then the two families (Y_{α} | α ∈ I) and (Y_{β} | β ∈ J) are independent of each other.

Lemma 3.3. Let Γ(n, r) be the graph with vertex set C(n, r) and an edge between two distinct cubes C, C′ ∈ C(n, r) iff C ∩ C′ ≠ ∅. Then Γ(n, r) is a dependency graph for the family (X_{C} | C ∈ C(n, r)).

Proof. Let I and J be disjoint subsets of C(n, r) with no edge between I and J. Then V_{I} := ⋃_{C∈I} C and V_{J} := ⋃_{C∈J} C are two disjoint subsets of {0, 1}^{n}. Thus the two random sets S ∩V_{I} and S ∩V_{J} are independent. Since the random variables (X_{C} | C ∈ I) only depend on S ∩ V_{I}, and similarly for J, it follows that the families (X_{C} | C ∈ I) and (X_{C} | C ∈ J) are independent. □

We can now use the dependency graphs Γ(n, r) and the machinery above to estimate cumulants of X_{n,r} and show that κ_{k}(X_{n,r}) = o((Var X_{n,r})^{k/2}) as n → ∞ for every fixed r ≥ 0 and k ≥ 3. However, we do not have to do these calculations, since they already have been done under general hypotheses, leading to convergence theorems that are easy to apply in situations like ours where there is a rather sparse dependency graph. We use here the following theorem, taken (with minor changes in notation) from [1, Theorem 2, with moment convergence by its proof and Theorem 1]. See e.g. [2, Theorems 6.18 and 6.20] for some related theorems (proved by the same cumulant method) that also can be used to show Theorem 3.1, and [2, Theorem 6.33] for another related theorem (proved by a different method) that also yields the asymptotic normality in Theorem 3.1 (but not immediately moment convergence).

Theorem 3.4 ([1]). Suppose that, for each n, (Y_{n,α} | α ∈ A_{n}) is a family of bounded random variables: |Y_{n,α}| ≤ A_{n}. Let N_{n} := |A_{n}|. Suppose further that Γ_{n} is a dependency graph for this family, and let M_{n} be the maximal degree of Γ_{n} (assuming this is not 0, in which case we let M_{n} := 1). Let W_{n} = ∑_{i∈A_{i}} Y_{n,i} and σ_{n}^{2} := Var(W_{n}). If there exists a positive integer m such that

(N_{n}/M_{n})^{1/m}M_{n}A_{n}/σ_{n} → 0  as n → ∞,  (3.6)

then

(W_{n} − 𝔼 W_{n})/σ_{n} ⟶^{d} N(0, 1)  as n → ∞,  (3.7)

with convergence in distribution and with all moments.

Proof of Theorem 3.1. Fix r ≥ 0. We let c_{1}, c_{2}, c_{3} denote unimportant positive constants that may depend on r, but not on n.

We use Theorem 3.4, with Y_{n,C} := X_{C} for C ∈ A_{n} := C(n, r), so W_{n} = X_{n,r}. We use Lemma 3.3 and take the dependency graph Γ_{n} = Γ(n, r). Then

N_{n} = |C(n, r)| = \binom{n}{r}2^{n−r} ≤ n^{r}2^{n},  (3.8)

and, by (2.7) (where i = 0 yields the leading term),

σ_{n}^{2} := Var(X_{n,r}) ≥ c_{1}n^{2r}2^{n}.  (3.9)

Furthermore, we may take

A_{n} := 1.  (3.10)

Moreover, from the definition of the graph Γ(n, r) follows that it is regular, with degree

M_{n} ≤ 2^{r}\binom{n}{r} ≤ c_{2}n^{r}.  (3.11)

We choose m = 3 in Theorem 3.4. (This is the standard case, which corresponds to the method of moment without extra arguments, see the proof in [1].) Then (3.8)–(3.11) yield

(N_{n}/M_{n})^{1/m}M_{n}A_{n}/σ_{n} = N_{n}^{1/3}M_{n}^{2/3}A_{n}/σ_{n} ≤ c_{3} \frac{n^{r}2^{n/3}}{n^{r}2^{n/2}} → 0  (3.12)

as n → ∞, so (3.6) holds. Consequently, Theorem 3.4 applies and shows Theorem 3.1. □

4. Conclusion

In the first part, we demonstrated the power of computers to automatically derive complicated explicit expressions, all polynomials in n and 2^{n}, for low moments of the random variable number of fixed-size implicants of a Boolean function of n variable, or equivalently, the number of fixed-dimensional subcubes of a random subset of the n-dimensional unit cube. These implied that the scaled first few moments for low-dimensional subcubes tend, as n goes to infinity, to those of the Normal Distribution, suggesting, but by no means proving, that for each fixed dimension, this random variable is asymptotically normal.

In the second part, we demonstrated the power of human ingenuity, and the traditional lore of probability and statistics, by presenting a simple proof of asymptotic normality, first proved in [3].

References

[1] Svante Janson, Normal convergence by higher semiinvariants with applications to sums of dependent random variables and random graphs. Annals of Probability 16 (1988), 305–312.

[2] Svante Janson, Tomasz Łuczak and Andrzej Ruciński, Random Graphs. Wiley, New York, 2000.

[3] Urszula Konieczna, Asymptotic normality of subcubes in random subgraphs of the n-cube. Discrete Mathematics 121 (1993), 117–122.

[4] V. P. Leonov and Albert Nikolaevich Shiryaev, On a method of semiinvariants. Teor. Veroyatnost. i Primenen 4 (1959), 342–355. (Russian.) English transl: Theor. Probability Appl. 4 (1959), 319–329.

[5] Thotsaporn Aek Thanatipanonda, Reviews of Symbolic Moment Calcu-

lus, arXiv:2003.11749. https://arxiv.org/abs/2003.11749

[6] . Karl Weber, Poisson convergence in the n-cube. Math. Nachr. 131 (1987), 49–57.

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/

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

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

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

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