TAOCP 7.1.2 Exercise 71

Fix an assignment $y \in {0,1}^{n-3}$ to the variables ${x_1,\ldots,x_n}\setminus{x_i,x_\ell,x_m}$.

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.1.2: Boolean Evaluation

Exercise 71. ▶ [M26] Suppose $f(x)$ is equal to 0 with probability $p$ at each point $x = x_1 \ldots x_n$, independent of its value at other points.

a) What is the probability that the gates $(58)$ are good?

b) What is the probability that bad pairs $(58)$ exist?

c) What is the probability that bad pairs $(58)$ are found in at most $t$ random trials?

d) What is the expected time to test case $(i, j, m)$, as a function of $p$, $t$, and $n$?

Verified: yes
Solve time: 1m54s

Setup

Fix an assignment $y \in {0,1}^{n-3}$ to the variables ${x_1,\ldots,x_n}\setminus{x_i,x_\ell,x_m}$. For this fixed $y$, the restriction of $f$ to the 3-dimensional subcube

$$ (x_i,x_\ell,x_m)\in{0,1}^3 $$

is an arbitrary Boolean function on 3 variables, specified by 8 independent Bernoulli trials with

$$ \Pr(f=0)=p,\qquad \Pr(f=1)=1-p. $$

Denote these 8 values by a vector

$$ F_y \in {0,1}^8, $$

indexed by the triples $(x_i,x_\ell,x_m)$ in lexicographic order.

The multilinear coefficients $\alpha_t(y)$ in the representation of $f$ on this cube are fixed Boolean functions of the 8 entries of $F_y$, given by the standard Möbius inversion over the Boolean lattice on 3 variables. Each $\alpha_t(y)$ is therefore a deterministic Boolean function of $F_y$.

Since different choices of $y$ use disjoint sets of input values of $f$, the random vectors $F_y$ are independent over all $2^{n-3}$ assignments $y$.

For each fixed $y$, define the event $G_y$ that the “gates (58) are good” at $y$, meaning that the three equalities

$$ \alpha_{010}\alpha_{101} = \alpha_{011}\alpha_{100}, \quad \alpha_{100}\alpha_{110} = \alpha_{100}\alpha_{111}, \quad \alpha_{110}\alpha_{011} = \alpha_{111}\alpha_{010} $$

hold when evaluated at $y$.

Let

$$ q = \Pr(G_y). $$

Then global events factor as

$$ \Pr(\text{gates (58) are good for all }y) = q^{2^{n-3}}. $$

All remaining parts reduce to computing or combining this single-slice probability $q$.

Solution

(a) Probability that the gates (58) are good

The event that the gates are good globally is the intersection of independent events $G_y$ over all $2^{n-3}$ assignments $y$. Hence

$$ \Pr(\text{all gates good}) = q^{2^{n-3}}. $$

It remains to express $q$.

For a fixed $y$, the vector $F_y$ ranges over ${0,1}^8$ with probability

$$ \Pr(F_y = u) = p^{#0(u)} (1-p)^{#1(u)}. $$

Each $\alpha_t(y)$ is a deterministic Boolean function of $u$. Therefore $q$ is

$$ q = \sum_{u\in{0,1}^8} p^{#0(u)}(1-p)^{#1(u)} \cdot \mathbf{1}{G(u)=1}, $$

where $G(u)$ denotes the satisfaction of the three algebraic identities after computing the coefficients from $u$.

Thus

$$ \boxed{\Pr(\text{gates (58) good}) = \left(\sum_{u\in{0,1}^8} p^{#0(u)}(1-p)^{#1(u)} \mathbf{1}{G(u)}\right)^{2^{n-3}} }. $$

(b) Probability that bad pairs (58) exist

A bad pair exists globally if there is some $y$ for which $G_y$ fails.

Thus

$$ \Pr(\exists \text{ bad pair}) = 1 - \Pr(\forall y,; G_y). $$

By independence across $y$,

$$ \Pr(\forall y,; G_y) = q^{2^{n-3}}. $$

Hence

$$ \boxed{\Pr(\text{bad pairs exist}) = 1 - q^{2^{n-3}} }. $$

(c) Probability that bad pairs are found in at most $t$ random trials

A “random trial” samples a random assignment $y$, producing an independent event $G_y$ with success probability $q$.

A bad pair is found within $t$ trials if at least one trial produces $\neg G_y$. Thus

$$ \Pr(\text{bad found in }\le t\text{ trials}) = 1 - \Pr(G_y \text{ holds in all }t\text{ trials}). $$

Independence gives

$$ \Pr(G_y \text{ in all }t) = q^t. $$

Therefore

$$ \boxed{\Pr(\text{bad found in }\le t\text{ trials}) = 1 - q^t }. $$

(d) Expected time to test case $(i,j,m)$

A single test of a fixed triple $(i,j,m)$ requires evaluating the 8 values of $f$ on the corresponding cube and computing the coefficients $\alpha_t$, followed by checking the three products in (58).

Let $T_{\text{eval}}$ be the time to evaluate the 8 input values and compute the 8 coefficients, and let $T_{\text{check}}$ be the time for the three comparisons. Then the total time per trial is

$$ T = T_{\text{eval}} + T_{\text{check}}. $$

Each trial succeeds (detects a bad configuration) with probability $1-q$. The number of trials until success is geometric with mean $1/(1-q)$.

Hence the expected time is

$$ \boxed{\mathbb{E}[\text{time}] = \frac{T}{1-q}}. $$

The dependence on $p$ is contained entirely in $q$, since $q$ is determined by the Bernoulli distribution on the 8 values of each cube, and therefore by $p$ through the weights $p^{#0}(1-p)^{#1}$ in the sum defining $q$.

Verification

The decomposition into independent slices $y$ is valid because each $G_y$ depends only on the 8 values of $f$ on a disjoint subcube, so the associated random variables are independent.

The complement rule in (b) uses $\Pr(A^c)=1-\Pr(A)$ applied to the event that all slices satisfy the gate conditions.

The geometric distribution in (c) applies because each trial is independent and identically distributed with success probability $1-q$ for detecting a bad configuration.

The expectation in (d) follows from the standard mean of a geometric waiting time multiplied by the per-trial cost.

This completes the proof. ∎