Hamming distance distribution induced by binary hypercube

Question

The following problem arises in a particular machine learning problem:

Assume that we have $n$ independent Bernoulli random variables with parameters $p_i$, e.g. $n=5$ and the $p$ vector is $(0.2, 0.3, 0.7, 0.6, 0.3)$. All possible realizations of the random variables form the corners of the $\lbrace 0,1\rbrace^n$-hypercube. There is one corner with highest probability (let's call it $c_\text{max}$), for $p=(0.2, 0.3, 0.7, 0.6, 0.3)$ we have $c_\text{max} = (0, 0, 1, 1, 0)$. Every corner of the hypercube is thus associated with a probability, let's call it $P^*$.

I am interested in the random variable $Z: \lbrace0,1\rbrace^n\rightarrow\lbrace0,\dots,n\rbrace$ with $Z(c) = $ Hamming distance from $c$ to $c_\text{max}$. Thus, I want to know the probability mass of $P^*$ at distance $1, 2, \dots n$ from $c_\text{max}$.

Brute-force traversal of the hypercube corners is out of the question for the problem sizes I'm considering ($n > 100$). However, I was thinking that there might by a clever (recursive?) way of exploiting the fact that the probabilities of neighboring corners differ by only one multiplicative factor of $p_i$ or $(1-p_i)$.

Although I don't think that I'm the first to contemplate this problem, a standard literature search has not revealed anything usable. Any algorithm ideas or pointers to the literature are much appreciated.

Thanks, Stephan

Answer 1

You can certainly phrase this question more simply. Without loss of generality you can take $p_i\leq 1/2$, so that the most likely corner is at 0. Then you are looking for the distribution of $\sum_{i=1}^n X_i$ where $X_i$ are independent Bernoulli$(p_i)$.

A simple way to calculate the probabilities you're after is recursively in $n$. Let $a_{r,m}$ be the probability that $\sum_{i=1}^m X_i=r$. Then $a_{0,0}=1$, and for $m\geq 1$

$a_{0,m}=(1-p_m)a_{0,m-1}$

$a_{r,m}=p_m a_{r-1,m-1} + (1-p_m) a_{r,m-1}$ for $1\leq r\leq m.$

This calculates the probabilities with order $n^2$ operations.

Other things that might be relevant if you want to approximate rather than calculate the probabilites: approximation by a normal distribution of mean $\sum p_i$ and variance $\sum p_i(1-p_i)$ (if the mean is reasonably large) or by a Poisson distribution of mean $\sum p_i$ (if the mean is small and each of the $p_i$ is very small). Simulation could also give you a pretty decent answer.