Problem #79 MEDIUM
The Circuit Board Test
Apple Meta Probability Optimization
Problem Statement
A factory produces circuit boards in batches of 100. Each batch is either entirely good (all 100 boards work) or entirely defective (all 100 boards fail). Before shipping, a quality controller tests individual boards from the batch. Each test costs 1 unit. If the batch is good, every board passes. If the batch is defective, each board fails its test independently with probability 0.9 (and passes with probability 0.1 — defective boards sometimes appear fine). The prior probability that any given batch is defective is 0.2. How many boards should the controller test to minimise total expected cost (testing cost plus cost of shipping a defective batch, where shipping a defective batch costs 500 units)?
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
Test exactly 3 boards. If all pass, ship the batch. Expected total cost ≈ 3.12 units (test cost 3 + expected defective-shipping cost 0.12). Testing fewer is too risky; testing more costs more than it saves. The Bayesian update makes P(defective) drop by 10× per passing board.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
Use Bayesian updating. Prior: P(D)=0.2, P(G)=0.8. After each passing board, update the posterior. A passing board is more likely from a good batch, so each pass reduces P(D). Stop when remaining expected loss from shipment < 1 (cost of next test).
Step 1: Prior: P(D)=0.2, P(G)=0.8. P(pass | G)=1.0 (good boards always pass). P(pass | D)=0.1 (defective boards pass with only 10% probability).
Step 2: After 1 pass: P(pass) = P(pass|G)×P(G) + P(pass|D)×P(D) = 1×0.8 + 0.1×0.2 = 0.82. P(D|pass) = P(pass|D)×P(D) / P(pass) = 0.02/0.82 ≈ 0.0244.
Step 3: After 2 passes: P(D|2 passes) = P(D|1 pass) × 0.1 / [P(D|1 pass)×0.1 + P(G|1 pass)×1] ≈ 0.00244/0.97806 ≈ 0.00249.
Step 4: After k passes: P(D | k passes) = 0.2×0.1^k / (0.8 + 0.2×0.1^k). This drops by factor ~10 with each test.
Step 5: Expected cost if stopping after k tests (all pass): k (test cost) + P(D|k passes)×500. After 0 tests: 0.2×500 = 100. After 1 test: 1 + 0.0244×500 ≈ 13.2. After 2 tests: 2 + 0.00249×500 ≈ 3.25. After 3 tests: 3 + 0.000249×500 ≈ 3.12. After 4 tests: 4 + 0.0000249×500 ≈ 4.01.
Step 6: Minimum expected cost at k=3: approximately 3.12 units. Testing 3 boards and shipping if all pass is the optimal policy.
Key Insight:
The optimal stopping point balances the information value of one more test against its cost. Here, P(D) drops by a factor of 10 per test (since defective boards fail 90% of the time), so the expected defective-shipping cost plummets rapidly. The sweet spot is where the marginal test cost (1) just exceeds the marginal expected-loss reduction — at k=3.