7m/8 is a closed form, and a closed form has hypotheses. Write a clause with only two distinct variables and it is satisfied by 3 of its 4 local assignments rather than 7 of 8, so the mean drops to 27/8 while 7m/8 still reads 7/2. Linearity of expectation has not failed; the arithmetic that collapsed m shares into one formula has. The lab computes each clause's share separately so the failure has an address.
Core ideas
The hard idea is which part of the argument broke. The other two are how the lab localises it and what a closed form owes its reader.
The expectation is always Σⱼ P(clause j satisfied), and that sum is correct for every formula. 7m/8 is what the sum collapses to when every term is 7/8. A clause on two distinct variables has 4 local assignments, one of which falsifies it, so its term is 3/4. The lab prints one row per clause with its own variable count and its own share, and the sum of the shares is checked against the mean over every assignment.
On the edited formula the four shares are 7/8, 7/8, 3/4 and 7/8, adding to 27/8, and the enumeration over all eight assignments gives 27/8 as well. Linearity is exactly as true as it was. What failed is a substitution: replacing each term by 7/8 was justified by a hypothesis, and the hypothesis stopped holding while the formula kept being applied.
7m/8 is printed on the panel with the word agrees or the words DOES NOT agree beside it, and the clause table marks any clause whose distinct-variable count is not three. So the page cannot show a wrong closed form without saying so, and the reader is told which clause did it rather than that something did.
The material
One edited clause, three quantities that disagree, and the one of them that is still right.
Start from the formula of “The Probabilistic Method” and change one clause. x₁ ∨ ¬x₂ ∨ x₃ becomes x₁ ∨ x₁ ∨ x₂. It is still a disjunction of three literals, it is still a legal clause, and it still looks like every other clause on the page. What it is not is a clause on three distinct variables, and that was a hypothesis of the theorem.
A clause has a width — how many literals it contains — and a count of distinct variables — how many different variables those literals mention. For most clauses the two are equal. x₁ ∨ x₁ ∨ x₂ has width 3 and two distinct variables, and it is the second number that decides the clause's satisfying fraction.
Let a clause mention d distinct variables and contain no pair of complementary literals on the same variable. Under a uniformly random assignment it is satisfied with probability (2ᵈ − 1)/2ᵈ. For d = 3 that is 7/8 and for d = 2 it is 3/4.
The clause is falsified exactly when every literal in it is false. A literal on variable v is false for exactly one of the two values of v, and since no variable appears with both signs, the requirement is consistent: it pins each of the d variables to one value.
So exactly one of the 2ᵈ assignments to those d variables falsifies the clause, and the variables outside the clause are irrelevant. The satisfying probability is (2ᵈ − 1)/2ᵈ.
□
If a clause does contain a variable and its negation — x₁ ∨ ¬x₁ ∨ x₂ — it is satisfied by every assignment and its share is 1. The lab handles that correctly too, by computing each clause's models over its own variables rather than applying a formula, which is what makes the clause table an enumeration rather than a second closed form waiting to be wrong.
x₁ ∨ x₂ ∨ ¬x₃ has three distinct variables and a share of 7/8. ¬x₁ ∨ x₂ ∨ x₃: three, 7/8. x₁ ∨ x₁ ∨ x₂: two, and 3 of its 4 local assignments satisfy it, so 3/4. ¬x₂ ∨ ¬x₃ ∨ ¬x₁: three, 7/8. The shares add to 7/8 + 7/8 + 3/4 + 7/8 = 27/8, and enumerating all eight assignments gives a mean of 27/8 as well. 7m/8 reads 7/2, and 27/8 ≠ 7/2.
27/8 is 3.375 and 7/2 is 3.5, a difference of 1/8 — exactly the amount the third clause's share fell short, which is what an additive argument predicts. Nothing subtle happened. One term in a sum of four was smaller than assumed, and the sum was smaller by precisely that much.
The existence argument survives in its general form: Z cannot always be below E[Z], so some assignment satisfies at least ⌈27/8⌉ = 4 clauses. The panel confirms it — the optimum is 4, which is all four clauses, so this formula is satisfiable. What does not survive is the number 7m/8, and any sentence that used it as the guarantee rather than as the value of the sum in a special case.
The distribution has changed shape as well. On the original formula every assignment satisfied 3 or 4 clauses; here one assignment satisfies only 2, three satisfy 3, and four satisfy 4. The measured mean over 120 seeded coin flips came out 33/10 = 3.3 with a range of 2 to 4, against an exact mean of 27/8 = 3.375. Same three kinds of number as everywhere else on this course, and the middle one has moved because the formula moved.
The optimum is still 4, so the ratio the random assignment earns is (27/8)/4 = 27/32 ≈ 0.844, down from 7/8 = 0.875. The algorithm has not changed and the instance has, which is the ordinary situation for an approximation ratio: the 7/8 guarantee is a claim about a class of instances, and this instance is outside the class. Either restate the guarantee for general clause widths or preprocess the formula so the hypothesis holds.
Preprocessing is the honest fix and it is cheap: x₁ ∨ x₁ ∨ x₂ is logically x₁ ∨ x₂, and a formula of clauses with fewer than three distinct variables has a general bound of Σ (2^dⱼ − 1)/2^dⱼ, which the lab already computes as the sum of the shares. The bound is weaker per clause with a smaller d — 3/4 against 7/8 — and it is correct, which 7m/8 is not.
This is the path's hazard in its sharpest form. A count on one input is not a bound; here, a closed form derived under a hypothesis is not a bound on instances that fail it, and the failure is silent. Every quantity on the panel was computed correctly and the page would have printed 7m/8 as the answer if nobody had asked the clause table what its terms were.
So the habit worth taking away is smaller than the theorem: keep the sum before you collapse it. Σⱼ P(clause j satisfied) is right for every formula, costs one row per clause to evaluate, and degrades into 7m/8 by itself when the hypothesis happens to hold. The collapsed version is shorter and it is the one that can be quietly wrong.
Interactive
The mean over every assignment is a fraction, the best assignment is found by enumeration, and the ratio between them is what the algorithm earns
Method
Find the term that changed before deciding what the theorem says.
Width three and three variables are different claims, and only the second decides the share. The lab prints both columns side by side and colours the second when they disagree, because this is the whole of the defect.
A clause with d distinct variables contributes (2ᵈ − 1)/2ᵈ. Put the real value in the sum and the answer is right again. Adjusting 7m/8 by a fudge factor is the move to avoid, since the fudge depends on the instance.
The panel adds the per-clause shares and compares them with the mean over every assignment. Two routes, one number; if they ever disagreed, the clause table would be the thing to distrust, not linearity.
7/8 of the optimum is a claim about formulas whose clauses have three distinct variables. On this formula the ratio is 27/32. Either say which class your instance is in, or quote the general sum, which is always available and always correct.
x₁ ∨ x₂ ∨ ¬x₃, ¬x₁ ∨ x₂ ∨ x₃, x₁ ∨ x₁ ∨ x₂, ¬x₂ ∨ ¬x₃ ∨ ¬x₁. Only the third clause differs from the formula of the previous lesson, and only one variable in it.
Two numbers agree and one does not, and the two that agree were computed by completely different routes: adding four per-clause fractions, and averaging eight integers. When a closed form disagrees with two independent computations, the closed form is the thing to doubt, and here the reason is visible in the third row of the first table.
The second row of the assignment table is new. F F T satisfies only 2 clauses, which the original formula had no assignment doing. Editing a clause changed the shape of the distribution as well as its mean, and neither change is visible from 7m/8, which did not move at all.
For a faded rehearsal, edit the third clause again, to x₁ ∨ ¬x₁ ∨ x₂, and predict the new mean first. The supplied first move is this: that clause contains a variable and its negation, so no assignment falsifies it and its share is 1. Work out the new sum of shares, say whether 7m/8 is now too high or too low, and then check both against the enumeration.
You should be able to compute a clause's share from its distinct variables, keep the per-clause sum rather than the collapsed form, say which of the argument's steps survives an edited clause, and recompute an approximation ratio against an optimum that has actually been found.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.