We have been given a random permutation on $n$ letters. The random variable $X$ is equal to the number of times that the position of an element after permutation is larger than its value. Find $\mathbb{E}(X)$.
What I have attempted so far:
I have attempted to make the statement of the problem rigorous. Assume that the permutation is given by $\sigma: \{1,\cdots,n\} \to \{1,\cdots,n\}$ such that $i \mapsto \sigma(i)$. We can rewrite $X(\sigma) = \#\{i: \sigma(i)>i\}$. Hence $X : S_n \to \{0,\cdots,n-1\}\subset\mathbb{R}$ is a random variable. I am assuming that all elements in $S_n$ are equally likely, even though it hasn't been mentioned in the wording of the problem.
So, intuitively, I expected the expectation to be some number like $\frac{n-1}{2}$ because the possible outcomes for $X$ range from $0$ to $n-1$ and $S_n$ is so symmetric and nice. Then I wrote a python code to gain some intuition about the problem. It turns out that checking up to $n=10$, $\mathbb{E}(X)=\frac{n-1}{2}$ works. Here are some values of $X$ for different values of $n$:
$$n=1: X=[1]$$ $$n=2: X=[1,1]$$ $$n=3: X=[1,4,1]$$ $$n=4: X=[1,11,11,1]$$ $$n=5: X=[1,26,66,26,1]$$ $$n=6: X=[1,57,302,302,57,1]$$
I don't see how to find the outcome of $X$ in general. I'm still thinking about it and have some ideas about working with transitions, but I haven't reached any conclusion yet. Any help (hints) is appreciated.
Let $X_i$ take value $1$ if $\sigma(i)>i$ and value $0$ otherwise.
Then $X=X_1+\cdots+X_n$.
Applying linearity of expectation we find:$$\mathbb EX=\sum_{i=1}^n\mathbb EX_i=\sum_{i=1}^n\mathsf P(\sigma(i)>i)=\sum_{i=1}^n\frac{n-i}n=\frac12(n-1)$$