Algorithms
October 20, 2024GATE-2024-CS1(Forenoon)
October 20, 2024GATE 2006
|
Question 18
|
We are given a set X = {x1, …. xn} where xi = 2i. A sample S ⊆ X is drawn by selecting each xi independently with probability pi = 1/2. The expected value of the smallest number in sample S is:
|
1/n
|
|
|
2
|
|
|
√n
|
|
|
n
|
Question 18 Explanation:
The smallest element in sample S would be xi for which i is the smallest.
The given probability Pi is for selection of each item independently with probability 1/2.
Now, Probability for x1 to be smallest in S = 1/2
Now, Probability for x2 to be smallest in S = Probability of x1 not being in S × Probability of x2 being in S
= 1/2 × 1/2
Similarly, Probability xi to be smallest = (1/2)i
Now the Expected value is
The given probability Pi is for selection of each item independently with probability 1/2.
Now, Probability for x1 to be smallest in S = 1/2
Now, Probability for x2 to be smallest in S = Probability of x1 not being in S × Probability of x2 being in S
= 1/2 × 1/2
Similarly, Probability xi to be smallest = (1/2)i
Now the Expected value is
Correct Answer: D
Question 18 Explanation:
The smallest element in sample S would be xi for which i is the smallest.
The given probability Pi is for selection of each item independently with probability 1/2.
Now, Probability for x1 to be smallest in S = 1/2
Now, Probability for x2 to be smallest in S = Probability of x1 not being in S × Probability of x2 being in S
= 1/2 × 1/2
Similarly, Probability xi to be smallest = (1/2)i
Now the Expected value is
The given probability Pi is for selection of each item independently with probability 1/2.
Now, Probability for x1 to be smallest in S = 1/2
Now, Probability for x2 to be smallest in S = Probability of x1 not being in S × Probability of x2 being in S
= 1/2 × 1/2
Similarly, Probability xi to be smallest = (1/2)i
Now the Expected value is