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

  • 2
    Some questions. First, how do you define the number of transpositions in a permutation? The minimum? Second, other than the identity permutation, which presumably has zero transpositions, other permutations have at least one transposition, so the expectation must be $\geq 1-\frac{1}{n}$.2012-05-04
  • 0
    Is $T$ perhaps the number -- or better, the proportion -- of [inversions](http://en.wikipedia.org/wiki/Inversion_(discrete_mathematics))? Or the [parity](http://en.wikipedia.org/wiki/Parity_of_a_permutation)? I think you mean the *proportion* of inversions.2012-05-04
  • 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
    I guess I didn't explain myself well enough. If I have a set of n objects {1,2,3,...,n} then pi is a random permutation of those objects. A transposition (how I learned it) is just a 2-cycle for example when a 2 is in the ninth spot in the set and a 9 is in the second spot in the set. I know the expectation of the number of k-cycles is 1/k and therefore for a 2 cycle, *E(T)*=1/22012-05-04
  • 0
    @donkeykong15: I see :-) Well, that was probably the most work I ever put into a question I'd misunderstood, but no worries, it was fun :-) I'll think about the other question. So what you're interested in is the number of transpositions in the *cycle structure* of the permutation.2012-05-04
  • 0
    Yes, sorry for the confusion! and i really appreciate the help :)2012-05-04