ZHANG Yan wrote: > Hi, I need to find the following probability problem: > > if the distributions of n indepednet random variables Y1,Y2,...Yn are > given, ie. > P(Yi=yi) is known for i=1..n; > > I need to find the following probability: > P(Y1+Y2+...+Yn = M)=? > > First I use n cycles, but the time comsumptio is too high. could you > plz give me some tips on any fast algorithm to compute the > probability? > > thx in advance.
>From a mathematical point of view, a general way of doing this would be to use moment generating functions. Taking this over to computations, you would need a general way of inverting the transformation from probabilities to mgf's. There may be an explicit formula for this, there certainly is if you were to use characteristic functions instead ... this would seem to lead to your needing to use an FFT routine somewhere. David Jones . . ================================================================= Instructions for joining and leaving this list, remarks about the problem of INAPPROPRIATE MESSAGES, and archives are available at: . http://jse.stat.ncsu.edu/ . =================================================================
