Exercise 187. [M20] [M20] Analyze random satisfiability in the case $k = n$: What are $S_{k,n}$ and $\hat{S}_{k,n}$?

Verified: yes
Solve time: 7m01s

For $k=n$, every clause contains every variable exactly once. Therefore the possible clauses are

$$ N=2^n\binom{n}{n}=2^n $$

in number. Each clause is falsified by exactly one Boolean assignment of the $n$ variables, and every Boolean assignment falsifies exactly one of these $2^n$ clauses.

A formula consisting of $m$ distinct random $n$-clauses is satisfiable exactly when at least one Boolean assignment has not yet been excluded. Thus it becomes unsatisfiable precisely when all $2^n$ possible clauses have appeared.

For the distinct-clause model, the clauses are revealed in a uniformly random order without repetition. The first $2^n-1$ clauses always leave one Boolean assignment satisfying all of them, because exactly one falsifying clause is still absent. The $2^n$-th clause eliminates the last remaining assignment. Hence the stopping time is always

$$ P_{n,n}=2^n. $$

Since $S_{k,n}$ is the expected stopping time,

$$ \boxed{S_{n,n}=2^n}. $$

For the model with replacement, each new clause is chosen independently from the $2^n$ possible clauses. The formula becomes unsatisfiable exactly when every one of the $2^n$ clauses has appeared at least once. This is the coupon collector problem with

$$ N=2^n $$

coupons.

Let $T_i$ be the number of additional draws needed when exactly $i$ distinct clauses have already appeared. When $i$ clauses have appeared, the probability that the next draw gives a new clause is

$$ \frac{N-i}{N}, $$

$$ E(T_i)=\frac{N}{N-i}. $$

Therefore the expected time to collect all $N$ clauses is

$$ \hat S_{n,n}

\sum_{i=0}^{N-1}\frac{N}{N-i}

N\sum_{j=1}^{N}\frac1j. $$

Substituting $N=2^n$ gives

$$ \boxed{\hat S_{n,n}=2^n H_{2^n}}, $$

where

$$ H_m=\sum_{j=1}^{m}\frac1j $$

is the $m$-th harmonic number.

Thus the two random satisfiability stopping times in the case $k=n$ are

$$ \boxed{S_{n,n}=2^n,\qquad \hat S_{n,n}=2^n H_{2^n}}. $$

TAOCP 7.2.2.2 Exercise 187

$$ \hat S_{n,n}

\sum_{i=0}^{N-1}\frac{N}{N-i}