The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 votes

We are given a set $X = \{X_1,\ldots,X_n\}$ where $X_i=2^i$.  A sample  $S\subseteq X$ is drawn by  selecting each $X_i$  independently with probability $P_i = \frac{1}{2}$ . The expected value of the smallest number in sample $S$ is:

  1. $\left(\frac{1}{n}\right)$
  2. $2$
  3. $\sqrt n$
  4. $n$
asked in Probability by Active (3.3k points)
edited by | 1.9k views

4 Answers

+47 votes
Best answer
The answer is option $D.$

The smallest element in sample $S$ would be $X_i$  for which $i$ is smallest.

The given probability is for selection of each item of $X$. Independent selection means each item is selected with probability $\frac{1}{2}$.

Probability for $X_1$ to be smallest in $S = \frac{1}{2} $.
Value of $X_1=2$.
Probability for $X_2$ to be smallest in $S$ = Probability of $X_1$ not being in $S$ $\times$ Probability of $X_2$ being in $S$ $= \frac{1}{2} . \frac{1}{2} $.
Value of $X_2=2^2=4$.
Similarly, Probability for $X_i$ to be smallest in $S = (1/2)^i$.

Value of $X_i=2^i$ .

Now Required Expectation=  $\sum_{i=1}^{n}2^{^{i}} \times \left ( \frac{1}{2} \right )^{i} = \sum_{i=1}^n 1 = n $.
answered by Active (2k points)
edited by

What if S is ∅ ?

Well explained !
nice explanation thump up (y)

Superb .Thanks:)

@Mari Ganesh-

Why the probability for $X_1$ to be smallest is $\frac{1}{2}$ and why not it is like

$X_1$ is smallest if we surely have $X_1$ in our set S, and remaining elements from the set X from $X_2$ to $X_n$ may or may not be present each with probability 1/2


So it should be like proability of $X_1$ to be smallest in S=Probability of $X_1$ in S * 2(Probability of Each of $X_i$ in S or not in S for i=$2\,to\,n$

= Probability of $X_1$ in S*2*($\frac{1}{2}$)=Probability of $X_1$ in S
probability of $x1$ being selected is $\frac{1}{2}$  along with it's weightage $2$. But when $x1$  is getting selected, then we are not choosing all the other elements ($x2,x3,....,xn$). So why it is not computed like this

$E(x)$=probability of choosing $x1$ * not choosing $(x2,x3,....xn)$* weight-age of $x1 = \frac{1}{2} *(\frac{1}{2})^{n-1} *2$

Kindly explain?
@Abhijit Sen4-That's exactly What i also want to know

 @Ayush Upadhyaya

After selection of $x_{i}$ , we should not care about presence or absence of $x_{i+1}$ to $x_{n}$

they may present or may they sum up to prob 1

ex $x_{1}$,$x_{2}$,$x_{3}$

$x_{1}$(present) $x_{2}$(present) $x_{3}$(present)

$x_{1}$(present) $x_{2}$(present) $x_{3}$( not present)

$x_{1}$(present) $x_{2}$(not present) $x_{3}$(present)

$x_{1}$(present) $x_{2}$(not present) $x_{3}$(present)

total for P(X = $x_{1}$) = 1/2 [ (1/4) * 4 ] = 1/2

correct me if something wrong 

I think for subset S=∅ i.e. { } since there is nothing present so smallest value= no value which can be taken as 0. Probability of S=∅ is $\frac{1}{2^n}$. So, $0 *\frac{1}{2^n}=0$ Doesn't affect anything..
+5 votes

Ans : D] n

Here, = {2,4,8,...,2n} and S is subset of X.

E[Z] = $\sum$ Z*P[Z] Here, random variable Z is value of smallest number in S, so Z can take value from {2,4,⋯,2n}.

E[smallest number] = $\sum_{i=1}^{n}$ xi * P[xi is smallest]

Now, P[xi is smallest] = $\frac{1}{2^{i}}$ as for xi to be smallest x1, x2,..., xi-1 should not be selected (this has probability of $\frac{1}{2^{i-1}}$ ) and xi should be selected (probability $\frac{1}{2}$ ).

$\therefore$ E[smallest number] = $\sum_{i=1}^{n}$ 2i * $\frac{1}{2^{i}}$ =  $\sum_{i=1}^{n}$ 1 = n

answered by Active (4.5k points)
+1 vote

Events are:

2 is smallest or 4 is smallest or ... or 'n' is smallest number.

Lets consider the probablity that 1 is smallest no. in set S

I choose 2 with probablity 1/2.

Now, I can choose 0 more elements in (n-1)C* $(\frac{1}{2})^{n-1}$

$(\frac{1}{2})^{n-1}$ because all elements were deselected each with probablity 1/2.


I can choose 1 more elements in (n-1)C1 * $(\frac{1}{2})^{n-1}$

(n-1)C1 * $(\frac{1}{2})^{n-1}$ because I selected 1 element with prob. 1/2 and deselected others each with prob. 1/2





I can choose n-1 more elements in (n-1)C1 * $(\frac{1}{2})^{n-1}$

(n-1)C(n-1) * $(\frac{1}{2})^{n-1}$ because I selected (n-1) elements each with prob. 1/2 

Thus, total probablity that 2 is least number

= $\frac{1}{2} * (\frac{1}{2})^{n-1} * (\binom{n-1}{0} + \binom{n-1}{1}+...+\binom{n-1}{n-1})$


Similarly, probablity of 4 being least number = 1/4




Similarly, probablity of 2n being least number = $\frac{1}{2^{n}}$

Now, mean

= $\sum x.P(x)$

= 2 * (1/2)  + 4 * (1/4)  + ... + 2n * $\frac{1}{2^{n}}$

= 1 + 1 + 1 + ... + (n times)

= n

answered by Boss (18.3k points)
–2 votes
Most probably 2 option b not sure.
answered by Active (3.3k points)
D is correct !

Related questions

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
49,814 questions
54,518 answers
75,287 users