Derive expected inversions and mean distribution
Company: Hudson
Role: Data Scientist
Category: Machine Learning
Difficulty: medium
Interview Round: Technical Screen
## Random permutation inversion statistics
Let `π` be a uniformly random permutation of length `N`. Let `X` be the number of inversions in `π`.
1. Compute **the expected value** `E[X]`.
2. Compute **the variance** `Var(X)`.
## Monte Carlo experiment
Now suppose you run the following simulation:
- Fix `N = 200`.
- Repeat `T = 1000` trials:
- sample a fresh uniform random permutation of length `N`
- compute its inversion count `X_t`
- compute the empirical mean `\bar{X} = \frac{1}{T}\sum_{t=1}^T X_t` and empirical variance across trials.
Answer the following:
3. What are the theoretical values of `E[\bar{X}]` and `Var(\bar{X})`?
4. What is the approximate **distribution** of `\bar{X}` for `T=1000` (and why)?
5. If you repeat the entire simulation above **5 independent times** (each time producing a mean `\bar{X}`), what is a reasonable approximation for the **typical range** `max(\bar{X}_1..\bar{X}_5) - min(\bar{X}_1..\bar{X}_5)`?
Quick Answer: This question evaluates understanding of permutation inversion statistics, computation of random-variable moments (expectation and variance), and the use of Monte Carlo simulation for empirical estimation, and sits in the Machine Learning domain with a strong probability and statistics component.