MATLAB Central Newsreader - compute (multimonial type) expression

compute (multimonial type) expression

tenida@gmail.com — Thu, 24 Jan 2008 01:10:41 -0500

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 ?

Re: compute (multimonial type) expression

Roger Stafford — Thu, 24 Jan 2008 05:12:02 -0500

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

Re: compute (multimonial type) expression

Roger Stafford — Thu, 24 Jan 2008 06:10:03 -0500

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in
message <fn96n2$n9i$1@fred.mathworks.com>...
> 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
-----
In case it will give you more confidence in the reasoning here, I should point
out that the above procedure is a simple generalization of the algorithm
involved in generating Pascal triangles for values nCk.

Roger Stafford