Let $\pi$ be a random permutation of $n$ objects and let $ T := \text{the number of transpositions in } \pi $. Use Chebychev's Inequality to find an upper bound for $T\geqslant k$.
Okay the problem I'm having here is with $\mathbb{Var}(T)$, I'm not sure how to find it. I know the expectation is $\frac{1}{2}$, so my formula so far is $$\mathbb{P}\left(T-\frac{1}{2}\geqslant k\right) \leqslant \frac{\mathbb{Var}(T)}{k^2}$$
Best Answer
I'll assume that you mean inversions, not transpositions, as bgins suggested. I'll also assume that the question does refer to the number and not the proportion of inversions, since $k$ looks like an integer variable, and that you just confused the two when you said that the expectation value is $1/2$. Also, note that the right-hand side of your inequality is the one for the two-sided Chebyshev inequality, whereas you want the one-sided one.
Finding the variance works similarly to finding the expectation value; it's just a bit more involved. Both use linearity of expectation.
Since every pair of elements has probability $1/2$ of being inverted, the expectation value for the number of inversions is half the number of unordered pairs, $n(n-1)/4$.
For the variance, we need to consider all possible ordered pairs of unordered pairs of distinct elements. There are four kinds of these: $n(n-1)/2$ pairs of identical pairs, $n(n-1)(n-2)/3$ pairs with an inner element in common, $2n(n-1)(n-2)/3$ pairs with an outer element in common, and $n(n-1)(n-2)(n-3)/4$ pairs with no elements in common, for a total of $n(n-1)(1/2+(n-2)/3+2(n-2)/3+(n-2)(n-3)/4)=(n(n-1)/2)^2$ pairs. We need to find the expectation value of the product of the inversion indicator variables for each type of pair.
For the pairs of identical pairs, the product is a square, and the square of an indicator variable is just the variable itself, so this expectation value is also $1/2$.
For the pairs with an inner element in common, all $6$ orders of the three elements are equiprobable and there is only one order in which both pairs are inverted, so the expectation value is $1/6$.
For the pairs with an outer element in common, all $6$ orders of the three elements are equiprobable and there are two orders in which both pairs are inverted, so the expectation value is $1/3$.
For the pairs with no elements in common, the two pairs have an independent probability of $1/2$ each of being inverted, so the expectation value is $1/4$. In total, the expectation value of the square of the number of inversions is
$$\frac12\frac{n(n-1)}2+\frac16\frac{n(n-1)(n-2)}3+\frac13\frac{2n(n-1)(n-2)}3+\frac14\frac{n(n-1)(n-2)(n-3)}4\\=\frac{n(n-1)(9n^2-5n+10)}{144}\;.$$
Subtracting the square of the expectation value of the number of inversions yields the variance
$$\operatorname{Var}T=\frac{n(n-1)(9n^2-5n+10)}{144}-\left(\frac{n(n-1)}4\right)^2=\frac{n(n-1)(2n+5)}{72}\;.$$