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:

1. What are the theoretical values of E[\bar{X}] and Var(\bar{X})?
2. What is the approximate distribution of \bar{X} for T=1000 (and why)?
3. 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)?