Timer
00:00
Your Answer
A
B
C
D
E
Global Stats
Don't know if this forum is the right place to submit such question. If it is not, sorry, delete it, Thanks
There is a set of m elements and I have a subset of n (0<n<m) elements built according to the following procedure:
A simple example with m=3 and n=1. Elements E1 E2 and E3 and probabilities p1=0.5 p2=0.4 p3=0.2
Which is the probability to get the subset E1 ?
Favourable cases: element Ei, probability to get it, probability to keep (if E1) or to NOT keep (if not E1) ...
E1 1/3 0.5
E2 1/3 (1-0.4) E1 1/2 0.5
............................. E3 1/2 (1-0.2) E1
E3 1/3 (1-0.2) E1 1/2 0.5
............................. E2 1/2 (1-0.4) E1
So, the probability to get the subset E1 is
p(E1) = 1/3 * 0.5 + 1/3 * 0.6 * (1/2 * 0.5 + 1/2 * 0.8) + 1/3 * 0.8 * (1/2 * 0.5 + 1/2 * 0.6) = 0.4433
and
p(E2) = 1/3 * 0.4 + 1/3 * 0.5 * (1/2 * 0.4 + 1/2 * 0.8) + 1/3 * 0.8 * (1/2 * 0.4 + 1/2 * 0.5) = 0.3533
p(E3) = 1/3 * 0.2 + 1/3 * 0.5 * (1/2 * 0.2 + 1/2 * 0.6) + 1/3 * 0.6 *(1/2 * 0.2 + 1/2 * 0.5) = 0.2033
I have been able to generalize this method and get a generic algorithm when n=1, but unable to obtain a generic one for any n.
============================================
Probability to get the subset Ek with m elements and probabilities pi
$$p(Ek)=\sum_{j=1}^m pk''\ \cdot\ Combi^{j-1}\ \cdot\frac{1}{j\ \cdot\ C\left(_j^m\right)}$$
Where pk'' = 1 when j=m
.............. pk'' = pk when j<>m
and \(Combi^j\) means all different products of j elements (1-pi) with i<>k
Unsure is the explanation is clear, so let’s see an example of \(Combi^j\) whith m=4, k=2
There is a set of m elements and I have a subset of n (0<n<m) elements built according to the following procedure:
- 1. Pick up a random element
2. Look up the probability to keep this specific element on a table specifying its fixed probability
3. Repeat the process until either- a. n elements are kept, or
b. the number of elements kept + the number of elements remaining = n. In this case all remaining elements are kept regardless of its probability
- a. n elements are kept, or
A simple example with m=3 and n=1. Elements E1 E2 and E3 and probabilities p1=0.5 p2=0.4 p3=0.2
Which is the probability to get the subset E1 ?
Favourable cases: element Ei, probability to get it, probability to keep (if E1) or to NOT keep (if not E1) ...
E1 1/3 0.5
E2 1/3 (1-0.4) E1 1/2 0.5
............................. E3 1/2 (1-0.2) E1
E3 1/3 (1-0.2) E1 1/2 0.5
............................. E2 1/2 (1-0.4) E1
So, the probability to get the subset E1 is
p(E1) = 1/3 * 0.5 + 1/3 * 0.6 * (1/2 * 0.5 + 1/2 * 0.8) + 1/3 * 0.8 * (1/2 * 0.5 + 1/2 * 0.6) = 0.4433
and
p(E2) = 1/3 * 0.4 + 1/3 * 0.5 * (1/2 * 0.4 + 1/2 * 0.8) + 1/3 * 0.8 * (1/2 * 0.4 + 1/2 * 0.5) = 0.3533
p(E3) = 1/3 * 0.2 + 1/3 * 0.5 * (1/2 * 0.2 + 1/2 * 0.6) + 1/3 * 0.6 *(1/2 * 0.2 + 1/2 * 0.5) = 0.2033
I have been able to generalize this method and get a generic algorithm when n=1, but unable to obtain a generic one for any n.
============================================
Probability to get the subset Ek with m elements and probabilities pi
$$p(Ek)=\sum_{j=1}^m pk''\ \cdot\ Combi^{j-1}\ \cdot\frac{1}{j\ \cdot\ C\left(_j^m\right)}$$
Where pk'' = 1 when j=m
.............. pk'' = pk when j<>m
and \(Combi^j\) means all different products of j elements (1-pi) with i<>k
Unsure is the explanation is clear, so let’s see an example of \(Combi^j\) whith m=4, k=2
Code: Select all
j=1 p2 / 4 + (*no elements*)
j=2 p2 [(1-p1) + (1-p3) + (1-p4)] / 12 + (*all single elements*)
j=3 p2 [(1-p1) (1-p3) + (1-p1) (1-p4) + (1-p3) (1-p4)] / 12 + (*all possible duplets*)
j=4 (1-p1) (1-p3) (1-p4) / 4 (*all possible triplets*)
