Before the hats are distributed, the wizards partition themselves into an
infinite number of finite committees S_1, S_2, S_3, etc. Each of these
committees, upon receiving their hats, will independently execute a
sub-strategy that only looks at the hats within their committee. Committee
S_i is said to succeed if it produces at least one correct guess and zero
wrong guesses.
If committee S_i succeeds with probability p_i, then the collective
probability of success is at least p_1 * p_2 * p_3 * ...
If we set each p_i to be greater than exp(-C*2^(-i)), then the infinite
product is greater than exp(-C). By choosing C appropriately, this product
can be made greater than 0.99.
It suffices to show that for any p<1, some finite committee can succeed
with probability > p.
Let us start with the better-known version of this problem: a size-3
committee. The maximum probability of success attainable is 3/4. You do
this by abstaining if you see two opposite colored hats, and guessing the
opposite color if you see two identically colored hats. The committee
succeeds in 6 of the 2^3=8 possible hat distributions (failing on BBB and
WWW).
It turns out that we can generalize this solution: a size-n committee can
succeed with probability n/(n+1), as long as n is of the form 2^k-1. Those
well-versed in information theory may already be familiar with the result.
For others, I've provided a proof in the appendix. In any case, since
n/(n+1) tends to 1 as n approaches infinity, this completes the solution.
QED
*Appendix: The Generalized Finite Solution (n=2^k-1): *
Consider a size n=2^k-1 committee, consisting of wizards numbered 1, 2,
..., n. Some subset of these wizards will receive black hats; let x be the
XOR of the wizards of this subset. Because n is of the form 2^k-1, x will
be an integer in the range {0, 1, ..., n}.
The committee does not know what x will be, but they can collectively
guess. Guessing the exact value is too hard, so they just guess a value
that x is *not*. To be precise, before the hats are even distributed, they
randomly choose some y in the range {0, 1, ..., n} and simply guess that x
!= y. Their guess will be correct with probability n/(n+1). And if they are
indeed correct, they can individually guess/abstain in a way to ensure that
they will succeed. The strategy is the natural one: each wizard assumes the
collective guess is correct, looks at the other (n-1) hats, and asks
whether he can rule out either black or white for his own hat by doing an
XOR computation. If he can rule out one of the two colors, he guesses the
other.
All that remains to be shown is that at least one wizard will make a guess
when x != y. To see this, define x_i to be what the total XOR would be *if
wizard i's hat color were flipped*. Clearly, x_i != x_j whenever i != j,
implying that {x_1, x_2, ..., x_n} is a permutation of {0, 1, ..., n} -
{x}. So as long as x!=y, there exists some i such that x_i = y, meaning
that wizard i can rule out one of two colors, as desired.