Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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}$. –  copper.hat May 4 '12 at 6:17
    
Is $T$ perhaps the number -- or better, the proportion -- of inversions? Or the parity? I think you mean the proportion of inversions. –  bgins May 4 '12 at 6:22
    
Please make the title more specific; this is a very specific random permutation problem. –  joriki May 4 '12 at 10:05

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

share|improve this answer
    
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/2 –  donkeykong15 May 4 '12 at 17:00
    
@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. –  joriki May 4 '12 at 17:02
    
Yes, sorry for the confusion! and i really appreciate the help :) –  donkeykong15 May 4 '12 at 17:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.