Keeping track of and detecting changes in the probability of events is a central problem for animals. We presented mice with an interval timing task: with probability p, mice were reinforced for staying at the first hopper until time t. With complementary probability 1-p they were reinforced for arriving at the second hopper before t+k. Because no animals are perfect timers, this task was difficult due to small k. Depending on p, the optimal switch point changed: if long trials were more likely, switching too late became more costly than switching too early, so the optimal switch time occurred later. Subjects showed highly significant (p<0.005) differences in their mean switch times when p was manipulated. Moreover, subjects were able to update their frequency estimates when the underlying probabilities of trial types changed and their estimates converged on accurate values quickly in comparison to plausible Bayesian optimal models.