Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

As stated in title. I have an existing result (the target) of a binomial experiment of length N trials with P(success)=x. Is there an analytic/closed-form way of getting probability that a new trial of same length and P will have the same outcome(s) (whether success or fail) at the same position(s) for some number of positions z, 1<=z<=N.

z=N is obviously trivial. I can get the value for the z<>N cases by enumerating the length z subsets of the target, taking the members of the target not in each subset and Not-ing the values, putting this all together, and calculating the probability of that sequence, summing these over all subsets, but that obviously explodes combinatorially.

My gut feeling is there is some elegant form, but I'm shooting blanks right now...

Cheers, Rob

Update 20130217: Had the flash, changed it to a counting problem vs the ultimately intractable enumeration problem. Below is snippet in R that does what I needed. I'm still curious if there's some exotic or unexpected solution, à la using Rook polynomials for graph matching.

#Language: R. Input sanity assumed.
#Return proability of matching a binary sequence TVec with a same length
#binomial trial with P = Pr(success->1), matching in precisely MatchLength positions.
#e.g., pVecMatch(c(1,0,1,1),0.5,2) -> 0.375, pVecMatch(c(1,0,1,1),0.5,4) -> 0.0625

pVecMatch<-function(TVec, P, MatchLength){

   Num0<-length(TVec[(TVec==1)])                    #Num zeros in candidate
   Num1<-length(TVec)-Num0                          #Num ones in candidate
   Flippable1<-min(MatchLength,Num1)                #Num of ones flippable
   TP<-0                                            #Probability to return
   Flipped1<-MatchLength-min(MatchLength,Num0)      #Start

   repeat {            


      if ((Flipped1==Flippable1)) {break}  




Update 20130218: I knew there was a reason for the gut feeling that some elegant form existed and that the problem seemed oddly familiar: this is of course just the Poisson binomial distribution in action. See, e.g., here for information, derivation and implementation.

share|cite|improve this question
Is there a question here? It sounds like you have answered your question, but not described it completely. You could write up the answer and accept it so the question doesn't stay unanswered. – Ross Millikan Feb 18 '13 at 23:02
@Ross: No longer, but I could not figure out how to answer my own question in a manner that I could marked it as such...until I saw the giant blue "Answer Your Question". Will do this asap, thanks for comment. – HeyCarNut Feb 18 '13 at 23:36
up vote 0 down vote accepted

This is answered using the Poisson binomial distribution, with the probability of the element(s) of the target for p and the desired match length for k in the PMF of the cited example.

share|cite|improve this answer

Your Answer


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.