In article <[EMAIL PROTECTED]>, David Jones <[EMAIL PROTECTED]> wrote:
>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.
If the distributions are discrete on the integers, I
suggest using generating functions methods instead. If the
ranges are finite, discrete convolutions work well, and
may, if the situation warrants it, be handled by the FFT.
If the distributions are on {0, 1, ..., k}, direct
convolutions can get the results in O(nk^2) computations.
The FFT can reduce this somewhat, but with considerable
danger of large roundoff error.
If the problem alllows for analytic methods, they should
be used. If the mgf can be computed easily, complex
inversion should be used. One can calculate numerically
the distribution of the sum of 100 absolute normal
random variables, and even get a good approximation in
the tails, but if the cdf is of interest, use the direct
formula for the cdf, not integrating the numerically
calculated density, or even using first-order asymptotics
on it.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Deptartment of Statistics, Purdue University
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
.
.
=================================================================
Instructions for joining and leaving this list, remarks about the
problem of INAPPROPRIATE MESSAGES, and archives are available at:
. http://jse.stat.ncsu.edu/ .
=================================================================
