Let \(A[1..n]\) be an array of \(n\) distinct numbers. If \(i < j\) and \(A[i] > A[j]\), then the pair \((i, j)\) is called an inversion of \(A\). (See Problem 2-4 for more on inversions.) Suppose that the elements of \(A\) form a uniform random permutation of \(\{1, 2, \ldots, n\}\). Use indicator random variables to compute the expected number of inversions.
An inversion is a pair of elements that are “out of order” with respect to their positions. For example, in the array \([3, 1, 4, 2]\), the pairs \((1,2)\), \((1,4)\), and \((3,4)\) are inversions because \(A[1] > A[2]\), \(A[1] > A[4]\), and \(A[3] > A[4]\) respectively.
Setting Up Indicator Random Variables
For each pair of indices \((i, j)\) where \(1 \leq i < j \leq n\), we define an indicator random variable:
Since the array contains a uniform random permutation of \(\{1, 2, \ldots, n\}\), for any two positions \(i\) and \(j\), the values \(A[i]\) and \(A[j]\) are two distinct random values from this set. These two values are equally likely to appear in either order. Therefore:
Experiment with the simulation below to see how inversions behave in practice. Compare sorted arrays (0 inversions), reversed arrays (maximum inversions), and random permutations (expected \(n(n-1)/4\) inversions):
import random
def count_inversions(arr):
"""
Count the number of inversions in an array.
An inversion is a pair (i, j) where i < j but arr[i] > arr[j].
"""
n = len(arr)
inversions = 0
for i in range(n):
for j in range(i + 1, n):
if arr[i] > arr[j]:
inversions += 1
return inversions
def simulate_expected_inversions(n, num_trials=500):
"""
Generate random permutations and compute average inversions.
Args:
n: Size of the permutation
num_trials: Number of random permutations to test
Returns:
The empirical average number of inversions
"""
total_inversions = 0
for _ in range(num_trials):
# Create a random permutation of 1 to n
arr = list(range(1, n + 1))
random.shuffle(arr)
total_inversions += count_inversions(arr)
return total_inversions / num_trials
# Test with small array sizes
print("Expected number of inversions in random permutations")
print("=" * 60)
for size in [5, 10]:
empirical_average = simulate_expected_inversions(size)
theoretical_expected = size * (size - 1) / 4
print(f"n = {size:2d} elements")
print(f" Theoretical: {theoretical_expected:.2f}")
print(f" Empirical: {empirical_average:.2f}")
print(f" Difference: {abs(empirical_average - theoretical_expected):.2f}")
print()
# Examples with specific arrays
print("=" * 60)
print("Specific examples with n = 5:")
print()
# Sorted array (no inversions)
sorted_arr = [1, 2, 3, 4, 5]
print(f"Sorted: {sorted_arr} -> {count_inversions(sorted_arr)} inversions")
# Reverse sorted (maximum inversions)
reverse_arr = [5, 4, 3, 2, 1]
max_inv = 5 * 4 // 2
print(f"Reverse: {reverse_arr} -> {count_inversions(reverse_arr)} inversions (max = {max_inv})")
print()
# Random examples
print("Three random permutations:")
for i in range(3):
random_arr = list(range(1, 6))
random.shuffle(random_arr)
inv_count = count_inversions(random_arr)
print(f" {random_arr}: {inv_count} inversions")
print(f"\nExpected for n=5: {5 * 4 / 4:.1f} inversions")