Linear time Outlier Scoring via Random Walks

I use a markov chain rejection sampling method to score outliers in linear time.

Input a matrix where the rows are points and the columns are features, you get back the matrix with an extra last column being the outlier scores.

The scoring is done by an original method (to my knowledge) inspired by MCMC and rejection sampling. It's linear in scoring where you can change the constant multiplier. A larger sampling constant is slower.