2
$\begingroup$

I have an intuition that re-casting the Poisson binomial distribution probability mass function in the following way might lead to a more elegant closed form than the DFT approach:

Sum the $\log_2$'s of the probabilities of each independent trial. The negation of that sum is equivalent to a new number of trials each of which has a $p=1/2$. Of course, if all the $p$'s start as $1/2$ the number of trials will be unchanged and one can degenerate the existing formulas accordingly to yield an $O(n)$ solution. But if the $p$'s differ, something else must be done (for example, because not every $p=1/2$ trial is independent).

My conjecture (or perhaps "wishful thinking" is more appropriate) is that there is an $O(n)$ closed form which will tell how one must re-number the desired number of successful trials ($k$) so it can be applied to the new number of trials where each has a $p$ of $1/2$, but not all are independent, yielding the same result as one would get from the ordinary PBD pmf.

$\endgroup$
1
  • $\begingroup$ How is the new space going to have the same support as the original PBD $\{0, \dotsc, n\}$ if there are fewer trials? $\endgroup$ – Neil G Feb 29 '12 at 19:39
1
$\begingroup$

At a glance, if you have n trials, then the parameter space of n independent trials is dimension n (each p_n is a separate parameter). But for the not-independent trials, you have an effective dimension of (2^n)-n-1. Each combination of pass/fail is a separate nonnegative parameter. The probability of all such states much add to 1 and the conditional probabilities of the states where the ith trial passes is set equal to 1/2. That gives n+1 constraints on 2^n parameters.

So my view is that there are enough parameters to do something like what you want for n>2. The key remaining problem is coming up with a transformation of the system of independent trials into the latter. I don't have any ideas there.

$\endgroup$
1
  • $\begingroup$ As an aside, you might want to consider the n=3 or n=4 case. If there are interesting transformations at these sizes, then maybe they can be generalized to arbitrary n. $\endgroup$ – Karl Hallowell Oct 2 '11 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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