Path: news.mathworks.com!not-for-mail
From: "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
Newsgroups: comp.soft-sys.matlab
Subject: Re: compute (multimonial type) expression
Date: Thu, 24 Jan 2008 05:12:02 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 35
Message-ID: <fn96n2$n9i$1@fred.mathworks.com>
References: <22123f1d-a0b3-42f4-b685-cb52d0793a5b@x69g2000hsx.googlegroups.com>
Reply-To: "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1201151522 23858 172.30.248.37 (24 Jan 2008 05:12:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 24 Jan 2008 05:12:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:447350


tenida@gmail.com wrote in message <22123f1d-a0b3-42f4-b685-
cb52d0793a5b@x69g2000hsx.googlegroups.com>...
> I need to compute what is the probability of selecting k balls from N
> balls where ball j can be picked with prob p_j.
> 
> Prob (k balls are picked) = \sum_{i_1}^N \sum_{i_2, i_2 not equal to
> i_1}^N......\sum_{i_k=1, i_k not equal to any of i_1,i_2,..,i_{k-1}}^N
> p_{i_1} p_{i_2}...p_{i_k} \Prod_{j not equal to i_1, i_2, ..,i_k} (1-
> p_j)
> 
> how can I compute Prob (k) efficiently, it seems there are N choose K
> terms inside and for me N = 350 and K=10 ?
--------
  I would do this problem by using an iteration in N.  Set up vector t with k+2 
elements in which after n steps in the iteration, the elements of t = [t(1),t(2),t
(3),t(4),...,t(k+2)] are the probabilities of having selected -1,0,1,2,...,k balls 
from the first n balls, respectively.  Of course t(1) will always be zero since -1 
is impossible, but the iteration is simplified if this zero is present.  In the 
beginning when n = 0 we must have t(2) = 1 and all other elements zero, 
since it is certain no balls have yet been selected.  Let p be the vector where p
(j) is the probability of picking the j-th ball.

 t = zeros(1,k+2); t(2) = 1;
 for j = 1:N
  t(2:k+2) = p(j)*t(1:k+1)+(1-p(j))*t(2:k+2);
 end
 
Then t(end) emerges as the desired probability of having picked k balls out of 
all N balls.  Moreover, the elements t(end-1),t(end-2), ...,t(2) will be the 
probabilities of having picked k-1, k-2, ..., 0 balls, respectively.  If you set k 
= N, then t(2:end) will give the probabilities of having chosen any desired 
number of balls from 0 to N.

Roger Stafford