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