Putnam 1976/B3 solution

37th Putnam 1976

Problem B3

Let 0 < α < 1/4. Define the sequence p_n by p₀ = 1, p₁ = 1 - α, p_n+1 = p_n - α p_n-1. Show that if each of the events A₁, A₂, ... , A_n has probability at least 1 - α, and A_i and A_j are independent for | i - j | > 1, then the probability of all A_i occurring is at least p_n. You may assume all p_n are positive.

Solution

This was a rare Putnam disaster - the question is wrong. Let q_n be the probability that all of A₁, ... , A_n occur. The idea was that one can more or less write down that q_n+1 ≥ q_n - α q_n-1 (*). The problem is then to show that it follows that q_n ≥ p_n (despite the awkward minus sign in (*) ). Unfortunately, (*) requires that A_n+1 is independent of the event (all of A₁, ... , A_n-1 occur) and that does not follow from the fact that A_n+1 is independent of each of A₁, ... , A_n-1.

Let us assume first that the question was correctly worded. Let E_n be the event that all of A₁, A₂, ... , A_n occur. We write p(E) as the probability that event E occurs. We write ~E as the event (not E). We assume that E_n-1 and A_n+1 are independent. We may partition the event E_n into the disjoint events E_n+1 and (E_n & ~A_n+1). So q_n = q_n+1 + p(E_n & ~A_n+1). But E_n-1 implies E_n, so p(E_n-1 & ~A_n+1) ≥ p(E_n & ~A_n+1). But E_n-1 and A_n+1 are assumed to be independent, so p(E_n-1 & ~A_n+1) = q_n-1 p(~A_n+1) ≤ α q_n-1. Hence p(E_n & ~A_n+1) ≤ α q_n-1. Hence q_n+1 ≥ q_n - α q_n-1. I have spelt that out at somewhat tedious length, but one should in fact be able to write the conclusion straight down.

Now let us assume that q_n+1 = q_n - α q_n-1 + β_n+1, where β_n+1 ≥ 0. A simple induction establishes that q_n = p_n + p_n-2β₁ + p_n-3β₂ + ... + p₀β_n-1 + β_n, so q_n ≥ p_n as required.

Finally, we need to show that the conclusion can be false if we assume no more than stated in the question. Take: p(A₁ & A₂ & A₃ & A₄ & A₅) = p(~A₁ & A₂ & A₃ & A₄ & A₅) = p(A₁ & ~A₂ & A₃ & A₄ & A₅) = p(A₁ & A₂ & ~A₃ & A₄ & A₅) = p(A₁ & A₂ & A₃ & ~A₄ & A₅) = p(A₁ & A₂ & A₃ & A₄ & ~A₅) = 4/25, p(~A₁ & ~A₂ & ~A₃ & ~A₄ & ~A₅) = 1/25.

We can easily check that p(A₁) = p(A₂) = p(A₃) = p(A₄) = 20/25, so we may take α = 1/5. We can also check that the prob of any pair, such as p(A₁ & A₂) = 16/25, so an independence assumption stronger than that in the question is satisfied. But p(A₁ & A₂ & A₃ & A₄) = 4/25 ≤ p₅ (= 6/25 - 1/125).

37th Putnam 1976