Detecting outliers in binary data using Mahalanobis distance

Question

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.

Answer 1

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.

Answer 2

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.