0
$\begingroup$

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}$

  • 0
    Please make the title more specific; this is a very specific random permutation problem.2012-05-04

1 Answers 1

1

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}\;.$

  • 0
    Yes, sorry $f$or the confusion! $a$nd i really appreciate the help :)2012-05-04