2
$\begingroup$

I have a binary vector $X_i$, $i=1...N$ of independent Bernoulli variables with parameters $p_i, \mu_i = p_i, \sigma_i^2 = p_i(1-p_i)$ (which is known) and I'm looking for some sort of tail bound to detect outliers. I'm considering using the Mahalanobis distance, i.e., comparing,

$$\Delta^2 = \sum_i \frac{(X_i - \mu_i)^2}{\sigma_i^2} \quad \quad \quad \text{to} \quad \quad \quad \mathbb{E}\left[\sum_i\frac{(X_i - \mu_i)^2}{\sigma_i^2} \right] = N.$$

I can use Hoeffding's inequality to show that

$$\mathbb{P}\left[\Delta^2 - N > \epsilon N\right] \propto \exp \Bigg( {-\frac{\epsilon N^2}{\sum_i 1/\sigma_i^4}} \Bigg) \propto e^{-k\epsilon N},$$

so for sufficiently large $N$ I can quantify the unlikelihood of a particular vector, but this only works so long as $p_i \neq 0, 1$ (Euclidean distance obviously doesn't have this problem). I have also heard whispers that the Mahalanobis distance is inappropriate for discrete data. Is this a valid criteria for classifying outliers in data of this sort? I can probably live with restricting to $p_i \neq 0, 1$ if I have to.

$\endgroup$

2 Answers 2

1
$\begingroup$

The appropriate measure for detecting outliers turns out to be the entropy rate, because of the Asymptotic Equipartition Property, which briefly states that the entropy rate of a random sequence tends to the Shannon entropy rate as the sequence gets longer. Detecting outliers is therefore asking if a sequence is not a member of the typical set.

$\endgroup$
0
$\begingroup$

According to this source, an extension of Mahalanobis distance can be used for discrete variables. I have no experience on neither tail bounds nor Hoeffding's inequality, but as far as I understand there is no restriction $p_i \neq 0,1$ for the distance definition in the paper.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer. The most appropriate measure for my application turner out to be looking at the Shannon entropy rate, and appealing to the Asymptotic Equipartition Property. $\endgroup$ Aug 21, 2021 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.