is the answer

The Gateway to Computer Science Excellence

0 votes

We have a **set(A)** of **N elements**. Let's assume elements are `e1,e2,e3..`

etc. Value of each element can be **0** or **1**. Another set of N elements(set B) are given, `p1,p2,p3..`

etc. Where `p (i) =probability of e (i) to be 1`

. If we pick a random permutation **P** of **N** elements from **set(A)**. What is the expected sum of elements in **P** ?

Example : if set(A) contains 5 elements `e1,e2,e3,e4,e5`

and we picked a 5 element sequence `1,0,0,1,1`

. In this case ** sum** = 3.

`Expected_Value`

of `sum`

0 votes

Thanks for pointing out my ignorance of the associated probabilities,

The solution I get now *appears* complex to me...and I would like to take your views on simplifying it in case it is correct,

Probability of selecting permutation with sum 1:

$P_{1} = n! * \sum_{i = 1}^{n} p_{i} \prod_{j = 1, j \ne i}^{n} (1-p_{j})$

Here we have $n!$ because we choose random permutation of elements in A.

Similarly for sum 2:

$P_{2} = n! * \sum_{i_{1} = 1}^{n}\sum_{i_{2} = 1, i_{1} \ne i_{2}}^{n} p_{i_{1}} p_{i_{2}}\prod_{j = 1, j \ne i_{1}, j \ne i_{2}}^{n} (1-p_{j})$

Generalizing it for sum n we get:

$P_{n} = n! * p_{i_{1}}* p_{i_{2}}...*p_{i_{n}}$, since there is only one string on n 1s, although it still can be arranged in $n!$ ways because all elements are distinct.

So the expected sum = $\sum_{i = 1}^{n} i * P_{i}$

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,292 answers

198,237 comments

104,919 users