The Weather Panel

Part A: 4 mistakes

Call a forecaster unrefuted while they have never been wrong. When the station is wrong, the majority of the unrefuted forecasters was wrong too, so at most half of them stay unrefuted. The never-wrong forecaster always stays, so after $j$ mistakes at least 1 and at most $16/2^j$ remain. That allows at most ${\log }_{2}16=4$ mistakes. The weather can force all four. Each time, it splits the unrefuted forecasters 8 to 8, then 4 to 4, then 2 to 2, then 1 to 1, and makes the rain side wrong. This is the halving algorithm. With $n$ forecasters it makes at most $\lfloor {\log }_{2}n\rfloor$ mistakes.

Part B: two forecasters who always disagree

The run DRDRDRDR works. On day 1 the weights tie, the station says rain, and the day is dry: Ana is halved. On day 2 Ben is heavier, the station says dry, and it rains: now Ben is halved and the weights tie again. The station is wrong every day, 8 mistakes, while Ana and Ben make 4 each.

This is not a weakness of weighted majority. Against any station that commits to one side, the weather can make every day the opposite of the broadcast. With Ana and Ben on the panel, one of them is then right at least half the time. So no deterministic station can promise fewer than twice the best forecaster's mistakes. Weighted majority nearly matches that. Suppose the best forecaster makes $m$ mistakes, and the station makes $M$. The best forecaster's weight ends at $2^{-m}$, which is at most the total weight. Each time the station is wrong, at least half of the total weight was on the wrong side and gets halved, so the total falls to at most $\frac{3}{4}$ of what it was. The total starts at $n$, so $$2^{-m}\le n{\left(\frac{3}{4}\right)}^M⟹M\le \frac{m+{\log }_{2}n}{{\log }_2(4/3)}\approx 2.41(m+{\log }_{2}n).$$

Part C: randomized weighted majority (Hedge)

Keep weight $w_i=e^{-\eta m_i}$, where $m_i$ is forecaster $i$'s mistakes so far, and forecast $p$ = the weighted share saying rain. Then your expected cost on a day is the weighted fraction of the panel that turns out wrong. The standard potential argument gives $$\text{your total}\le \frac{\eta m+\ln n}{1-e^{-\eta }}.$$ A sharper analysis, using Hoeffding's lemma, gives $\eta =\sqrt{8\ln n/T}$ and $$\text{your total}\le m+\sqrt{\frac{T\ln n}{2}},$$ well inside the grader's allowance of $2\sqrt{T\ln n}$. The bound holds for every sequence of days, so it also holds when the weather sees $p$ first. $p$ depends only on the past, and the cost $|p-\text{outcome}|$ is exactly your expected number of mistakes.

What fails the grader:

• Committing to 0 or 1. Deterministic weighted majority and follow-the-leader are both wrong on all 2000 days of the first test, against 1000 for the best.
• Halving the weights, but randomizing. With $\eta =\ln 2$ fixed, the two disagreeing forecasters swap places every day. The station's cost alternates between $\frac{1}{2}$ and $\frac{2}{3}$, an average of $\frac{7}{12}$ per day: about 1167 against 1000, over the allowance of about 74. The rate must shrink like $1/\sqrt{T}$.
• Trusting everyone equally. The panel's average never learns, and pays 0.5 a day against a forecaster who is never wrong.

Going further

• The square root is necessary. Against two forecasters who flip fair coins, any method expects $\Omega (\sqrt{T})$ more mistakes than the luckier one.
• Not knowing $T$. Restart with doubled guesses for $T$ (the doubling trick), or use the time-varying rate ${\eta }_t=\sqrt{8\ln n/t}$.
• Games and boosting. Running Hedge for both players of a zero-sum game converges to its value, a proof of the minimax theorem (Zero-Sum Games). AdaBoost is Hedge run over the training examples.

References

1. N. Littlestone, M. K. Warmuth. The weighted majority algorithm. Information and Computation 108(2), 1994.
2. Y. Freund, R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences 55(1), 1997.
3. M. Herbster, M. K. Warmuth. Tracking the best expert. Machine Learning 32(2), 1998.
4. P. Auer, N. Cesa-Bianchi, Y. Freund, R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing 32(1), 2002.
5. S. Arora, E. Hazan, S. Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing 8, 2012.