  A classical result in online learning characterizes the optimal mistake bound
achievable by deterministic learners using the Littlestone dimension
(Littlestone '88). We prove an analogous result for randomized learners: we
show that the optimal expected mistake bound in learning a class $\mathcal{H}$
equals its randomized Littlestone dimension, which is the largest $d$ for which
there exists a tree shattered by $\mathcal{H}$ whose average depth is $2d$. We
further study optimal mistake bounds in the agnostic case, as a function of the
number of mistakes made by the best function in $\mathcal{H}$, denoted by $k$.
We show that the optimal randomized mistake bound for learning a class with
Littlestone dimension $d$ is $k + \Theta (\sqrt{k d} + d )$. This also implies
an optimal deterministic mistake bound of $2k + \Theta(d) + O(\sqrt{k d})$,
thus resolving an open question which was studied by Auer and Long ['99].
  As an application of our theory, we revisit the classical problem of
prediction using expert advice: about 30 years ago Cesa-Bianchi, Freund,
Haussler, Helmbold, Schapire and Warmuth studied prediction using expert
advice, provided that the best among the $n$ experts makes at most $k$
mistakes, and asked what are the optimal mistake bounds. Cesa-Bianchi, Freund,
Helmbold, and Warmuth ['93, '96] provided a nearly optimal bound for
deterministic learners, and left the randomized case as an open problem. We
resolve this question by providing an optimal learning rule in the randomized
case, and showing that its expected mistake bound equals half of the
deterministic bound of Cesa-Bianchi et al. ['93,'96], up to negligible additive
terms. In contrast with previous works by Abernethy, Langford, and Warmuth
['06], and by Br\^anzei and Peres ['19], our result applies to all pairs $n,k$.
