How to find the average Kendall's distance between 2 rankings Suppose I have 2 rankings:
$1$, $2$, $3$ and $2, 1, 3$ then the Kendall's distance between the two is 1 since there is only one pairwise adjacent switch. 
My question is, suppose my 2 rankings each consist of 3 items, then what's the average Kendall's distance between them? What's the average distance between 2 rankings with 8 items? Or X items?
I tried permuting all possible cases of rankings with 3 items (i.e. {1, 2, 3}, {1, 3, 2}, {3, 1, 2}, {3, 2, 1}, {2, 3, 1}, {2, 1, 3} and then calculating the Kendall's distance from each ranking to all the other ones. Then I took the average and got 1.5. Not sure if that's correct, and rankings with lots of items become computationally difficult for me, so I was wondering if there's a more straightforward solution. 
note: couldn't find a suitable tag so I just used permutation
 A: Erick Wong has already given the correct answer to your question, which is $\frac{n(n-1)}{4}$. Here is my attempt at a proof by induction.
Due to symmetry, we do not need to consider the entire matrix of distances between permutations, which is of size $n! \times n!$. It is enough to look at the distances between the naturally ordered ranking $(1, 2, ..., n)$ and all $n!$ permutations (including itself). In this case, each distance is equivalent to the number of inversions, i.e. pairs $i < j$ such that $\sigma(i) > \sigma(j)$. We then go on to prove the following (equivalent) statement:
$P(n)$: The average number of inversions of $\{1, 2, ..., n\}$ across its permutations is $ \frac{n(n-1)}{4}$.
We now show that $P(n)$ holds for any $n \ge 1$.
Basis: The statement obviously holds for $n = 1$. $\{1\}$ has only one permutation, namely $(1)$, which has $0 = \frac{0 \cdot (-1)}{4}$ inversions. 
Inductive step: We show that if $P(k)$ holds, then $P(k+1)$ holds.
We split our $(k+1)!$ permutations into $k+1$ sets of $k!$ permutations according to the position of the newest item in the set, $k+1$.
Case 1: We consider permutations of the form $(\sigma(1), \sigma(2), ..., \sigma(k), k + 1)$, where item $k+1$ is in the $k+1$-th position. From $P(k)$ we have that the average number of inversions of the items $\{1, 2, ..., k\}$ is $\frac{k(k-1)}{4}$. Since $k+1$ is the largest item, the new item pairs $(\sigma(i), k+1)$, $i \in \{1, 2, ..., k\}$, do not constitute any additional inversions.
Case 2: We consider permutations of the form $(\sigma(1), \sigma(2), ..., \sigma(k-1), k + 1, \sigma(k))$, where item $k+1$ is in the $k$-th position. From $P(k)$ we have that the average number of inversions of the items $\{1, 2, ..., k\}$ is $\frac{k(k-1)}{4}$. Since $k+1$ is the largest item, the new item pairs $(\sigma(i), k+1)$, $i \in \{1, 2, ..., k-1\}$, do not constitute any additional inversions. The pair $(k+1, \sigma(k))$, on the other hand, is always an inversion. This increases the average number of inversions for the set of $k+1$ items to $\frac{k(k-1)}{4} + 1$
We follow this line of reasoning until we reach the final case...
Case k+1: We consider permutations of the form $(k + 1, \sigma(1), \sigma(2), ..., \sigma(k-1), \sigma(k))$, where item $k+1$ is in the first position. From $P(k)$ we have that the average number of inversions of the items $\{1, 2, ..., k\}$ is $\frac{k(k-1)}{4}$. Since $k+1$ is the largest item, the new item pairs $(k+1, \sigma(i))$, $i \in \{1, 2, ..., k\}$, all constitute additional inversions. This increases the average number of inversions for the set of $k+1$ items to $\frac{k(k-1)}{4} + k$.
We now combine the average number of inversions of the $k+1$ disjoint sets of $k!$ permutations to obtain the average number of inversions of $\{1, 2, ..., k+1\}$ across its permutations. Let us denote this number by $\bar{I}_{k+1}$.
\begin{align*}
\bar{I}_{k+1} &= \frac{1}{(k+1)!} \left[ \frac{k(k-1)}{4} k! + \left(\frac{k(k-1)}{4} + 1\right) k! + ... + \left( \frac{k(k-1)}{4} + k \right) k! \right] \\
& = \frac{1}{k+1} \left[ \frac{k(k-1)}{4} + \left(\frac{k(k-1)}{4} + 1\right) + ... + \left( \frac{k(k-1)}{4} + k \right) \right] \\
& = \frac{1}{k+1} \left[ \frac{k(k-1)(k+1)}{4} + \frac{k(k+1)}{2} \right] \\
& = \frac{k(k-1)}{4} + \frac{k}{2}  \\
& = \frac{(k+1)k}{4} \\
\end{align*}
With this we have shown that $P(k+1)$ holds and the proof by induction is complete. We conclude that the average number of inversions of $\{1, 2, ..., n\}$ across its permutations, which is equal to the average Kendall tau distance between its permutations, is $ \frac{n(n-1)}{4}$.
Q.E.D.
A: Here's my comment in answer form, which I believe should be a simpler presentation than igb's answer (which seems correct to me, though I haven't checked the fine details).
Let $\sigma,\tau$ be two independent randomly chosen permutations.  Then the Kendall distance between $\sigma$ and $\tau$ is equal to the number of inversions in $\sigma^{-1} \tau$.  Since multiplication by any fixed $\sigma^{-1}$ is a bijection on the finite space of permutations, the distribution of $\sigma^{-1} \tau$ is also uniformly random.  So we may equivalently consider the expected number of inversions in $\tau$ itself.
For any $1\le i<j\le n$, let $X_{ij}(\tau)$ be the indicator variable which takes the value $1$ if $\tau(i) > \tau(j)$ and $0$ otherwise.  Then by symmetry the expected value of $X_{ij}(\tau)$ is $1/2$ (for instance, pre-multiplication by the transposition $(i,j)$ maps bijectively between the permutations where $X_{ij} =0$ and the permutations where $X_{ij}=1$).  Furthermore, the precise number of inversions in $\tau$ is exactly $\sum_{i=1}^{n-1} \sum_{j=i+1}^n X_{ij}(\tau)$.  By linearity of expectation, the expected value of this sum is equal to the sum of each expectation, or $1/2$ times the number of terms $X_{ij}$.  This gives $n(n-1)/4$.
