IAE Academy

GATE 2024 CS1 Q.14: solution and answer

GATE 2024 · CS1Q.14 · 1 mark · MCQ

Consider a permutation sampled uniformly at random from the set of all permutations of for some . Let be the event that 1 occurs before 2 in the permutation, and the event that 3 occurs before 4. Which one of the following statements is TRUE?

  1. (A)

    The events and are mutually exclusive

  2. (B)

    The events and are independent

  3. (C)

    Either event or must occur

  4. (D)

    Event is more likely than event

See the question in the paper

Answer and solution

ANSWER

Option (B): the events X and Y are independent, since P(X ∩ Y) = 1/4 = P(X)P(Y).

Official answer: BSource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

  1. Swapping the positions of 1 and 2 in a permutation is a one-to-one map from permutations with 1 before 2 onto those with 2 before 1. So . The same argument with 3 and 4 gives .

  2. Option (D): , so is not more likely than . (D) is false.

  3. Option (A): since , the permutation has 1 before 2 and 3 before 4. Both events occur together, so and the events are not mutually exclusive. (A) is false.

  4. Option (C): the permutation has 2 before 1 and 4 before 3, so neither event occurs. It is therefore false that one of them must occur. (C) is false.

  5. Option (B): only the relative order of the elements matters for and . In a uniformly random permutation, all relative orders of these four elements are equally likely. To get both and , choose which 2 of the 4 positions hold in ways. Then 1 must come before 2 in those two positions and 3 before 4 in the other two, which is 1 way each.

  6. So . This equals . Hence and are independent, and (B) is true.

KEY IDEA

Events that depend on the relative order of disjoint sets of elements, such as {1,2} and {3,4}, are independent in a uniformly random permutation. Each pair has a probability of 1/2 and the joint probability is 1/4.

WATCH OUT FOR

Assuming that "1 before 2" and "3 before 4" must interact because they live in the same permutation. Independence holds here, and it can be checked by counting the 24 orders of the four elements.

From the GATE 2024 CS1 paper. Every question of this paper · Download the full paper · All 60 Probability & statistics questions, with notes

More Probability & statistics questions