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.