Path: news.mathworks.com!not-for-mail
From: "Bruno Luong" <b.luong@fogale.findmycountry>
Newsgroups: comp.soft-sys.matlab
Subject: Re: What is the probability that random integers sum to a given value?
Date: Tue, 30 Jun 2009 21:20:02 +0000 (UTC)
Organization: FOGALE nanotech
Lines: 32
Message-ID: <h2dvi2$sn3$1@fred.mathworks.com>
References: <h2de1d$sgb$1@fred.mathworks.com>
Reply-To: "Bruno Luong" <b.luong@fogale.findmycountry>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1246396802 29411 172.30.248.38 (30 Jun 2009 21:20:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Tue, 30 Jun 2009 21:20:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 390839
Xref: news.mathworks.com comp.soft-sys.matlab:551836


"David Heslop" <david_heslop@xyz.com> wrote in message <h2de1d$sgb$1@fred.mathworks.com>...
> Can anybody suggest an efficient method to approach this problem?
> 
> Choose W unique random integers drawn from 1 to N, what is the probability that their sum will equal a given value? Typically both N and W are large, around 500 and 50 respectively. Currently I'm approaching this problem using a simple Monte Carlo approach to determine probability distributions  for a range of sum values for given N and W, but the accuracy is not good enough. Can anyone suggest an alternative approach which is better than simply performing more Monte-Carlo trials,
> 
> thanks
> 
> Dave 

m=6; % vector length (w)
n=15; % define n such that 0<=w<=n

% engine
% possible sum vector 
s = (0:n*m);
% Compute probabillity
d = zeros(1,m*(n-1)+1);
i1 = n-m+2;
i = cumsum([i1 repmat(n+1,1,m-2)]);
d(i) = arrayfun(@(k) (-1)^(k-1)*nchoosek(m,k-1), 2:m);
c = d;
for k=m:-1:1
    c = cumsum([nchoosek(m-1,k-1) c]);
end
P = c / sum(c);

% Graphic
figure;
plot(s, P, '-o');
xlabel('sum');
ylabel('P(sum)');
title(sprintf('vector length = %d, n = %d', m, n));