Let 0 < α < 1/4. Define the sequence p_{n} by p_{0} = 1, p_{1} = 1 - α, p_{n+1} = p_{n} - α p_{n-1}. Show that if each of the events A_{1}, A_{2}, ... , 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_{1}, ... , 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_{1}, ... , A_{n-1} occur) and that does not follow from the fact that A_{n+1} is independent of each of A_{1}, ... , A_{n-1}.

Let us assume first that the question was correctly worded. Let E_{n} be the event that all of A_{1}, A_{2}, ... , 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}β_{1} + p_{n-3}β_{2} + ... + p_{0}β_{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_{1} & A_{2} & A_{3} & A_{4} & A_{5}) = p(~A_{1} & A_{2} & A_{3} & A_{4} & A_{5}) = p(A_{1} & ~A_{2} & A_{3} & A_{4} & A_{5}) = p(A_{1} & A_{2} & ~A_{3} & A_{4} & A_{5}) = p(A_{1} & A_{2} & A_{3} & ~A_{4} & A_{5}) = p(A_{1} & A_{2} & A_{3} & A_{4} & ~A_{5}) = 4/25, p(~A_{1} & ~A_{2} & ~A_{3} & ~A_{4} & ~A_{5}) = 1/25.

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

© John Scholes

jscholes@kalva.demon.co.uk

23 Jan 2001