### 37th Putnam 1976

Problem B3

Let 0 < α < 1/4. Define the sequence pn by p0 = 1, p1 = 1 - α, pn+1 = pn - α pn-1. Show that if each of the events A1, A2, ... , An has probability at least 1 - α, and Ai and Aj are independent for | i - j | > 1, then the probability of all Ai occurring is at least pn. You may assume all pn are positive.

Solution

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

Let us assume first that the question was correctly worded. Let En be the event that all of A1, A2, ... , An occur. We write p(E) as the probability that event E occurs. We write ~E as the event (not E). We assume that En-1 and An+1 are independent. We may partition the event En into the disjoint events En+1 and (En & ~An+1). So qn = qn+1 + p(En & ~An+1). But En-1 implies En, so p(En-1 & ~An+1) ≥ p(En & ~An+1). But En-1 and An+1 are assumed to be independent, so p(En-1 & ~An+1) = qn-1 p(~An+1) ≤ α qn-1. Hence p(En & ~An+1) ≤ α qn-1. Hence qn+1 ≥ qn - α qn-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 qn+1 = qn - α qn-1 + βn+1, where βn+1 ≥ 0. A simple induction establishes that qn = pn + pn-2β1 + pn-3β2 + ... + p0βn-1 + βn, so qn ≥ pn 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(A1 & A2 & A3 & A4 & A5) = p(~A1 & A2 & A3 & A4 & A5) = p(A1 & ~A2 & A3 & A4 & A5) = p(A1 & A2 & ~A3 & A4 & A5) = p(A1 & A2 & A3 & ~A4 & A5) = p(A1 & A2 & A3 & A4 & ~A5) = 4/25, p(~A1 & ~A2 & ~A3 & ~A4 & ~A5) = 1/25.

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