Tudor Investment's high-frequency research pipeline needs a deterministic filter for unusually large observations in an ordered stream of market values. Implement a robust rolling anomaly detector using the trailing median and median absolute deviation, or MAD.
For each observation after the first window values, use only the previous window observations as the reference distribution. Mark the current observation as anomalous when its absolute deviation from the reference median is strictly greater than threshold * MAD.
If the MAD is zero, any current value different from the median is anomalous. Observations without a complete preceding window cannot be classified and must not be returned.
Implement identify_anomalies(values, window, threshold). values is a list of finite numbers ordered by arrival time. window is an integer, and threshold is a positive number. Return a list of zero-based indices identified as anomalies, in ascending order.
The median of an even-length list is the average of its two middle values. The MAD is the median of the absolute deviations from the median.
def identify_anomalies(values, window, threshold):