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 ?

by Veteran (57.2k points)
retagged by | 311 views

2 Answers

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}$

by Active (1.8k points)
edited by

 is the answer

Can you suggest a way to simply expressions for these individual probabilities? Further, may I know the reference for this question?
I did not do it your way. Rather I used indicative random variable to get the Expected value. Answer came out to be same.
0 votes
ans would be \sum pi,how!!! pi is probability of 1 so if ei is 1,means pi is one. EX = e(1,0,1,0,1,1) p=(1,0,1,1,1) both are similar
by (181 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,369 users