Katkat
Back

Derive expected inversions and mean distribution

Hudson River TradingData Scientist · Technical Screen
MediumData ScientistTechnical ScreenMachine Learning

Last updated

This problem tests your understanding of linearity of expectation and variance properties applied to permutation statistics, as well as the ability to design a simulation to verify analytical derivations.

Problem Statement

Consider a random permutation P of the set {1, 2, ..., n}, where each permutation is equally likely. An inversion is a pair of indices (i, j) such that i P[j].

  1. Calculate the expected number of inversions E[I] in a random permutation of length n.
  2. Calculate the variance of the number of inversions Var(I).
  3. Write a function estimate_inversion_stats(n, num_samples) that uses Monte Carlo simulation to estimate the mean and variance of the number of inversions for a given n by generating num_samples random permutations.

Constraints

  • n: Integer, 1 <= n <= 1000
  • num_samples: Integer, 1,000 <= num_samples <= 100,000

Example

For n = 3: Permutations: [1,2,3] (0 inv), [1,3,2] (1), [2,1,3] (1), [2,3,1] (2), [3,1,2] (2), [3,2,1] (3). Mean = (0+1+1+2+2+3) / 6 = 1.5

Interface

def estimate_inversion_stats(n: int, num_samples: int) -> tuple:
    # Returns (empirical_mean, empirical_variance)
    pass

Hints

Hint 1

Define indicator variables X_{i,j} for each pair (i,j) that equals 1 if an inversion exists and 0 otherwise; what is the probability P(X_{i,j} = 1)?

Hint 2

Use the property that the total number of inversions is the sum of these indicator variables and apply the linearity of expectation.

Hint 3

For the variance, note that indicator variables for pairs that share indices are not independent, requiring careful consideration of covariance terms.

Follow-up questions

  • How would the expected number of inversions change if the permutation was not uniformly random but biased such that smaller values were more likely to appear earlier?
  • How does the time complexity of counting inversions in a single array compare to the complexity of your Monte Carlo simulation?
  • Can you derive the distribution of the number of inversions for small n (e.g., n=3) and explain why the distribution becomes approximately normal as n increases?