Let \(\beta \in (0,1)\), let \(W : \mathbb {N} \to \mathbb {R}\) be a sequence of positive reals, and suppose \(W(k+1) \le W(k) \cdot \tfrac {1+\beta }{2}\) for every \(k \lt M\). Then

Under the same shrinkage hypothesis as wm_weight_shrinkage, if additionally \(n \ge 1\) and the initial total weight satisfies \(W(0) = n\), then

Let \(\beta \in (0,1)\), \(n \ge 1\), and suppose \(\beta ^{M^*} \le n \cdot \bigl(\tfrac {1+\beta }{2}\bigr)^{M_{\mathrm{WM}}}\). Then

This packages the potential inequality into logarithmic form by monotonicity of \(\log \).

Let \(n \ge 2\), \(\beta \in (0,1)\), and suppose \(\beta ^{M^*} \le n \cdot \bigl(\tfrac {1+\beta }{2}\bigr)^{M_{\mathrm{WM}}}\). Then

Equivalently, \(M_{\mathrm{WM}} \le \dfrac {\log n + M^* \cdot \log (1/\beta )}{\log (2/(1+\beta ))}\), giving the standard Weighted Majority mistake bound.

For any \(T \in \mathbb {N}\), there exist \(M_{\mathrm{alg}}, M^* \in \mathbb {N}\) with \(M_{\mathrm{alg}} = T\) and \(2 M^* \le T\). This witnesses that a deterministic learner facing two constant experts can be forced by an adversary to make \(T\) mistakes while the best expert makes at most \(T/2\), showing the factor of \(2\) in the Weighted Majority bound is unavoidable.