Trevor is a fan of the TV show Seinfeld. Trevor enjoys watching the episodes in random order. In the show, there are n ≥ 2 episodes, which we will label with a distinct number from the set S = {1, 2, · · · , n}. While Trevor was trying to figure out which order to watch the episodes in, he decided to practice his expectation skills. Let s₁s₂ · · · sₙ be a permutation of S.
For i = 2, 3, . . . , n we say that position i in the permutation is a step if sᵢ₋₁< si. We also go ahead and just consider position 1 a step. What is the expected number of steps in a random permutation of S?