Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

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_1(1-p_1)$ (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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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