GATE CS 2024 Set 1 — Question 14

MCQ+1 / -0.33MediumSample Space & EventsProbability & StatisticsEngineering Mathematics

Engineering Mathematics → Probability & Statistics → Sample Space & Events

Last updated 20 August 2026

Question

Consider a permutation sampled uniformly at random from the set of all permutations of

\{1, 2, 3, \dots, n\}

for some

n \geq 4

. Let

X

be the event that 1 occurs before 2 in the permutation, and

Y

the event that 3 occurs before 4. Which one of the following statements is TRUE?

The events

X

and

Y

are mutually exclusive

The events

X

and

Y

are independent

Either event

X

Y

must occur

Event

X

is more likely than event

Y

Correct answer

(B) The events X and Y are independent

Solution

Let

S

be the set of all

n!

permutations of the set

\{1, 2, 3, \dots, n\}

1.Event $X$ : 1 occurs before 2. In any random permutation, the relative order of 1 and 2 can only be (1, 2) or (2, 1). By symmetry, both are equally likely. Thus,

P(X) = \frac{1}{2}

2.Event $Y$ : 3 occurs before 4. Similarly, the relative order of 3 and 4 can only be (3, 4) or (4, 3), and both are equally likely. Thus,

P(Y) = \frac{1}{2}

3.Independence: To determine if

X

and

Y

are independent, we check if

P(X \cap Y) = P(X)P(Y)

Consider the relative ordering of the subset

\{1, 2, 3, 4\}

. There are

4! = 24

possible relative orderings of these four elements, all of which are equally likely in a random permutation of

n

elements.

The event $X \cap Y$ occurs when 1 is before 2 AND 3 is before 4.
Out of the 24 permutations of $\{1, 2, 3, 4\}$ , we can count the number of ways where both conditions are met:
Choose 2 positions out of 4 for the pair $\{1, 2\}$ in $\binom{4}{2} = 6$ ways. In each choice, there is exactly 1 way to place them such that 1 is before 2.
The remaining 2 positions must be filled by $\{3, 4\}$ . There is exactly 1 way to place them such that 3 is before 4.
Total favorable outcomes = $6 \times 1 \times 1 = 6$ .
$P(X \cap Y) = \frac{6}{24} = \frac{1}{4}$ .

Since

P(X \cap Y) = \frac{1}{4} = \frac{1}{2} \times \frac{1}{2} = P(X)P(Y)

, the events

X

and

Y

are independent.

Analysis of other options:

(A) False: $P(X \cap Y) = 1/4 \neq 0$ , so they are not mutually exclusive.
(C) False: $P(X \cup Y) = P(X) + P(Y) - P(X \cap Y) = 1/2 + 1/2 - 1/4 = 3/4$ . Since the probability is not 1, it is not guaranteed that either $X$ or $Y$ must occur.
(D) False: $P(X) = P(Y) = 1/2$ , so they are equally likely.

GATE CS 2024 Set 1 — Question 14

Question

Correct answer

Solution

More questions on Probability & Statistics