ROC curves have historically been used to evaluate the accuracy of Intrusion Detection Systems (IDSs). In this paper, we argue that a real-time IDS' input changes considerably over time and ROC curves generated using fixed, time-invariant classification thresholds do not characterize the best accuracy that an IDS can achieve. To address this problem, we propose a simple, generic and adaptive technique to achieve good ROC operating points for any given IDS. The proposed technique stochastically predicts the next anomaly score of an IDS and the anomaly classification threshold is then set as a function of the predicted score. We first perform statistical and information-theoretic analyses of network- and host-based IDSs' anomaly scores to reveal a consistent time correlation structure during benign activity periods. We model the observed correlation structure using Markov chains and then use this model to predict and adapt an IDS' classification threshold. The proposed adaptive thresholding module is incorporated into six prominent network- and host-based Anomaly Detection Systems (ADSs). These adaptive ADSs are evaluated on public and labeled attack datasets. We show that, while reducing the need for manual threshold configuration and having very low-complexity, adaptive thresholding enables the ADSs to achieve considerably higher accuracies on the ROC plane.