In wonderful lectures by P. Diaconis "Group representations in probability and statistics, Chapter 6. Metrics on Groups, and Their Statistical Use" metrics on permutation group are considered and central limit theorems for kind of balls volumes are dicussed. Some of these theorems goes back to classical results in statistics by Kendall, Mann-Whitney etc.. and some completely new.

Question in brief: Are there any generalizations of such results and constructions to other finite groups ? One may expect kind of classes/examples of pairs: (group, metric on group) such that kind of central limit theorems for balls volumes holds true.

Simple Motivational Example: Consider finite abelian group $(Z/2Z)^n$ i.e. just sequences of zeros and ones. We can put metric on it: $d(x,y)=|x-y|_{L_1} = \sum_i |x_i-y_i|$ i.e. just count all "1" in vector $x-y$. A volume of ball of radius "k", is the same as probability of sum $\sum_{i<=n} \xi_i$ to be less or equal than $k$ (and multiply by $2^n$), where independent variables $\xi_i = 0,1$ with $1/2$-probability. That is exactly the setup of the most classical central limit theorem, which can be visualized by Galton board (Bean machine).

Diaconis-Graham theorem 1977
Consider symmetric group $S_n$ with a metric $\rho(\pi,\sigma) = \sum |\pi(i)-\sigma(i) |$. If $\sigma$ is chosen uniformly in $S_n$ then:

$$ P( \frac{\rho - Average}{\sqrt{Variance}} < t )= 1/sqrt{(2\pi)}\int_{\infty}^t exp(-x^2/2) dx + O(1)$$

$$ Average(\rho) = (n^2-1)/3, Variance(\rho) = 1/45(n+1)(2n^2+7). $$

Diaconis also describes similar results for other of metrics on symmetric group. Some of them goes to classical results in statistics. And related to rank correlation coefficients by Kendall and Spearman, to Mann-Whitney test, etc (see also MO)... See also recent paper A central limit theorem for a new statistic on permutations Sourav Chatterjee, Persi Diaconis where other generalization for symmetric groups is considered. It is tempting to think, that similar results can be generalized substituting symmetric group by some other groups.

See MO57629 on Hoeffding's theorem

Kendall's tau (Diaconis p 117) Consider symmetric group $S_n$ with a metric $I(\pi,\sigma) = $ min # (pairwise adjacent transpositions to bring $\pi^{-1}$ to $\sigma^{-1}$).

This metric has a long history, summarized in Kruskal (1958, Sec. 17). It was popularized by Kendall who gives a comprehensive discussion in Kendall ("Rank Correlation Methods" 1970). The definitions in terms of inverses is given to make the metric right invariant.

Standardized by its mean and variance / has a standard normal limiting distribution. Kendall (1970) gives tables for small n. An elegant argument for the mean, variance and limiting normality is given in (C-3) below. This also gives fast computational algorithms and correction terms to the normal limit. A second argument is sketched in 5. below.

In wonderful lectures by P. Diaconis "Group representations in probability and statistics, Chapter 6. Metrics on Groups, and Their Statistical Use" metrics on permutation groups are considered and central limit theorems for kind of balls volumes are discussed. Some of these theorems go back to classical results in statistics by Kendall, Mann-Whitney etc.. and some are completely new.

Question in brief: Are there any generalizations of such results and constructions to other finite groups ? One may expect kinds of classes/examples of pairs: (group, metric on group) such that these kind of central limit theorems for balls volumes hold true.

Simple Motivational Example: Consider the finite abelian group $(\mathbf{Z}/2\mathbf{Z})^n$ i.e. just sequences of zeros and ones. We can put a metric on it: $d(x,y)=|x-y|_{L_1} = \sum_i |x_i-y_i|$ i.e. just count all "1" in the vector $x-y$. The volume of the ball of radius $k$, is the same as the probability of the sum $\sum_{i<=n} \xi_i$ to be less or equal than $k$ (and multiply by $2^n$), where independent variables $\xi_i = 0,1$ with $1/2$-probability. That is exactly the setup of the most classical central limit theorem, which can be visualized by the Galton board (Bean machine).

Diaconis-Graham theorem 1977
Consider the symmetric group $S_n$ with the metric $\rho(\pi,\sigma) = \sum |\pi(i)-\sigma(i) |$. If $\sigma$ is chosen uniformly in $S_n$ then:

$$ P\left( \frac{\rho - \mathrm{Average}}{\sqrt{\mathrm{Variance}}} < t \right)= 1/\sqrt{(2\pi)}\int_{\infty}^t \exp(-x^2/2) dx + O(1)$$

$$ \mathrm{Average}(\rho) = (n^2-1)/3, \mathrm{Variance}(\rho) = 1/45(n+1)(2n^2+7). $$

Diaconis also describes similar results for other metrics on symmetric group. Some of them are related to classical results in statistics, as well as rank correlation coefficients by Kendall and Spearman, to Mann-Whitney test, etc (see also MO)... See also recent paper A central limit theorem for a new statistic on permutations, Sourav Chatterjee, Persi Diaconis where other generalization for symmetric groups is considered. It is tempting to think, that similar results can be generalized substituting symmetric group by some other groups.

See MO57629 on Hoeffding's theorem.

Kendall's tau (Diaconis p 117) Consider the symmetric group $S_n$ with the metric $I(\pi,\sigma) = $ min # (pairwise adjacent transpositions to bring $\pi^{-1}$ to $\sigma^{-1}$).

This metric has a long history, summarized in Kruskal (1958, Sec. 17). It was popularized by Kendall, who gives a comprehensive discussion in Kendall ("Rank Correlation Methods" 1970). The definitions in terms of inverses is given to make the metric right-invariant.

Standardized by its mean and variance / has a standard normal limiting distribution. Kendall (1970) gives tables for small $n$. An elegant argument for the mean, variance and limiting normality is given in (C-3) below. This also gives fast computational algorithms and correction terms to the normal limit. A second argument is sketched in 5. below.

In wonderful lectures by P. Diaconis "Group representations in probability and statistics, Chapter 6. Metrics on Groups, and Their Statistical Use" metrics on permutation group are considered and central limit theorems for kind of balls volumes are dicussed. Some of these theorems goes back to classical results in statistics by Kendall, Mann-Whitney etc.. and some completely new.

Question in brief: Are there any generalizations of such results and constructions to other finite groups ? One may expect kind of classes/examples of pairs: (group, metric on group) such that kind of central limit theorems for balls volumes holds true.

Let me give more details:

Simple Motivational Example: Consider finite abelian group $(Z/2Z)^n$ i.e. just sequences of zeros and ones. We can put metric on it: $d(x,y)=|x-y|_{L_1} = \sum_i |x_i-y_i|$ i.e. just count all "1" in vector $x-y$. A volume of ball of radius "k", is the same as probability of sum $\sum_{i<=n} \xi_i$ to be less or equal than $k$ (and multiply by $2^n$), where independent variables $\xi_i = 0,1$ with $1/2$-probability. That is exactly the setup of the most classical central limit theorem, which can be visualized by Galton board (Bean machine).

Diaconis-Graham theorem 1977
Consider symmetric group $S_n$ with a metric $\rho(\pi,\sigma) = \sum |\pi(i)-\sigma(i) |$. If $\sigma$ is chosen uniformly in $S_n$ then:

$$ P( \frac{\rho - Average}{\sqrt{Variance}} < t )= 1/sqrt{(2\pi)}\int_{\infty}^t exp(-x^2/2) dx + O(1)$$

$$ Average(\rho) = (n^2-1)/3, Variance(\rho) = 1/45(n+1)(2n^2+7). $$

Diaconis also describes similar results for other of metrics on symmetric group. Some of them goes to classical results in statistics. And related to rank correlation coefficients by Kendall and Spearman, to Mann-Whitney test, etc (see also MO)... See also recent paper A central limit theorem for a new statistic on permutations Sourav Chatterjee, Persi Diaconis where other generalization for symmetric groups is considered. It is tempting to think, that similar results can be generalized substituting symmetric group by some other groups.

Other metrics.

$L_2$ metric and Spearman's rank correlation (Diaconis p 116 bottom) Consider symmetric group $S_n$ with a metric $S^2(\pi,\sigma) = \sum |\pi(i)-\sigma(i) |^2 $.

It is right invariant. When transformed to lie in [—1,1] as in example 1 of Section A, it arises naturally as the correlation R between the ranks of two samples. It is widely used in applied work. $S^2$ has mean $(n^3 - n)/6$ and variance $n^2(n-1)(n+1)^2/36$. Normalized by its mean and variance, $S^2$ has a limiting normal distribution. These results can all be found in Kendall ("Rank Correlation Methods" 1970). Normality can be proved using Hoeffding's theorem as above .

See MO57629 on Hoeffding's theorem

Kendall's tau (Diaconis p 117) Consider symmetric group $S_n$ with a metric $I(\pi,\sigma) = $ min # (pairwise adjacent transpositions to bring $\pi^{-1}$ to $\sigma^{-1}$).

This metric has a long history, summarized in Kruskal (1958, Sec. 17). It was popularized by Kendall who gives a comprehensive discussion in Kendall ("Rank Correlation Methods" 1970). The definitions in terms of inverses is given to make the metric right invariant.

...

Standardized by its mean and variance / has a standard normal limiting distribution. Kendall (1970) gives tables for small n. An elegant argument for the mean, variance and limiting normality is given in (C-3) below. This also gives fast computational algorithms and correction terms to the normal limit. A second argument is sketched in 5. below.

There are also examples of Cayley, Ulam and Hamming metrices.

In wonderful lectures by P. Diaconis "Group representations in probability and statistics, Chapter 6. Metrics on Groups, and Their Statistical Use" metrics on permutation group are considered and central limit theorems for kind of balls volumes are dicussed. Some of these theorems goes back to classical results in statistics by Kendall, Mann-Whitney etc.. and some completely new.

Question in brief: Are there any generalizations of such results and constructions to other finite groups ? One may expect kind of classes/examples of pairs: (group, metric on group) such that kind of central limit theorems for balls volumes holds true.

Let me give more details:

Simple Motivational Example: Consider finite abelian group $(Z/2Z)^n$ i.e. just sequences of zeros and ones. We can put metric on it: $d(x,y)=|x-y|_{L_1} = \sum_i |x_i-y_i|$ i.e. just count all "1" in vector $x-y$. A volume of ball of radius "k", is the same as probability of sum $\sum_{i<=n} \xi_i$ to be less or equal than $k$ (and multiply by $2^n$), where independent variables $\xi_i = 0,1$ with $1/2$-probability. That is exactly the setup of the most classical central limit theorem, which can be visualized by Galton board (Bean machine).

Diaconis-Graham theorem 1977
Consider symmetric group $S_n$ with a metric $\rho(\pi,\sigma) = \sum |\pi(i)-\sigma(i) |$. If $\sigma$ is chosen uniformly in $S_n$ then:

$$ P( \frac{\rho - Average}{\sqrt{Variance}} < t )= 1/sqrt{(2\pi)}\int_{\infty}^t exp(-x^2/2) dx + O(1)$$

$$ Average(\rho) = (n^2-1)/3, Variance(\rho) = 1/45(n+1)(2n^2+7). $$

Diaconis also describes similar results for other of metrics on symmetric group. Some of them goes to classical results in statistics. And related to rank correlation coefficients by Kendall and Spearman, to Mann-Whitney test, etc (see also MO)... See also recent paper A central limit theorem for a new statistic on permutations Sourav Chatterjee, Persi Diaconis where other generalization for symmetric groups is considered. It is tempting to think, that similar results can be generalized substituting symmetric group by some other groups.

Other metrics.

$L_2$ metric and Spearman's rank correlation (Diaconis p 116 bottom) Consider symmetric group $S_n$ with a metric $S^2(\pi,\sigma) = \sum |\pi(i)-\sigma(i) |^2 $.

It is right invariant. When transformed to lie in [—1,1] as in example 1 of Section A, it arises naturally as the correlation R between the ranks of two samples. It is widely used in applied work. $S^2$ has mean $(n^3 - n)/6$ and variance $n^2(n-1)(n+1)^2/36$. Normalized by its mean and variance, $S^2$ has a limiting normal distribution. These results can all be found in Kendall ("Rank Correlation Methods" 1970). Normality can be proved using Hoeffding's theorem as above .

See MO57629 on Hoeffding's theorem

Kendall's tau (Diaconis p 117) Consider symmetric group $S_n$ with a metric $I(\pi,\sigma) = $ min # (pairwise adjacent transpositions to bring $\pi^{-1}$ to $\sigma^{-1}$).

This metric has a long history, summarized in Kruskal (1958, Sec. 17). It was popularized by Kendall who gives a comprehensive discussion in Kendall ("Rank Correlation Methods" 1970). The definitions in terms of inverses is given to make the metric right invariant.

...

Standardized by its mean and variance / has a standard normal limiting distribution. Kendall (1970) gives tables for small n. An elegant argument for the mean, variance and limiting normality is given in (C-3) below. This also gives fast computational algorithms and correction terms to the normal limit. A second argument is sketched in 5. below.

There are also examples of Cayley, Ulam and Hamming metrics.

In wonderful lectures by P. Diaconis "Group representations in probability and statistics, Chapter 6. Metrics on Groups, and Their Statistical Use" metrics on permutation group are considered and central limit theorems for kind of balls volumes are dicussed. Some of these theorems goes back to classical results in statistics by Kendall, Mann-Whitney etc.. and some completely new.

Question in brief: Are there any generalizations of such results and constructions to other finite groups ? One may expect kind of classes/examples of pairs: (group, metric on group) such that kind of central limit theorems for balls volumes holds true.

Let me give more details:

Simple Motivational Example: Consider finite abelian group $(Z/2Z)^n$ i.e. just sequences of zeros and ones. We can put metric on it: $d(x,y)=|x-y|_{L_1} = \sum_i |x_i-y_i|$ i.e. just count all "1" in vector $x-y$. A volume of ball of radius "k", is the same as probability of sum $\sum_{i<=n} \xi_i$ to be less or equal than $k$ (and multiply by $2^n$), where independent variables $\xi_i = 0,1$ with $1/2$-probability. That is exactly the setup of the most classical central limit theorem.

Diaconis-Graham theorem 1977
Consider symmetric group $S_n$ with a metric $\rho(\pi,\sigma) = \sum |\pi(i)-\sigma(i) |$. If $\sigma$ is chosen uniformly in $S_n$ then:

$$ P( \frac{\rho - Average}{\sqrt{Variance}} < t )= 1/sqrt{(2\pi)}\int_{\infty}^t exp(-x^2/2) dx + O(1)$$

$$ Average(\rho) = (n^2-1)/3, Variance(\rho) = 1/45(n+1)(2n^2+7). $$

Diaconis also describes similar results for other of metrics on symmetric group. Some of them goes to classical results in statistics. And related to rank correlation coefficients by Kendall and Spearman, to Mann-Whitney test, etc (see also MO)... See also recent paper A central limit theorem for a new statistic on permutations Sourav Chatterjee, Persi Diaconis where other generalization for symmetric groups is considered. It is tempting to think, that similar results can be generalized substituting symmetric group by some other groups.

In wonderful lectures by P. Diaconis "Group representations in probability and statistics, Chapter 6. Metrics on Groups, and Their Statistical Use" metrics on permutation group are considered and central limit theorems for kind of balls volumes are dicussed. Some of these theorems goes back to classical results in statistics by Kendall, Mann-Whitney etc.. and some completely new.

Question in brief: Are there any generalizations of such results and constructions to other finite groups ? One may expect kind of classes/examples of pairs: (group, metric on group) such that kind of central limit theorems for balls volumes holds true.

Let me give more details:

Simple Motivational Example: Consider finite abelian group $(Z/2Z)^n$ i.e. just sequences of zeros and ones. We can put metric on it: $d(x,y)=|x-y|_{L_1} = \sum_i |x_i-y_i|$ i.e. just count all "1" in vector $x-y$. A volume of ball of radius "k", is the same as probability of sum $\sum_{i<=n} \xi_i$ to be less or equal than $k$ (and multiply by $2^n$), where independent variables $\xi_i = 0,1$ with $1/2$-probability. That is exactly the setup of the most classical central limit theorem, which can be visualized by Galton board (Bean machine).

Diaconis-Graham theorem 1977
Consider symmetric group $S_n$ with a metric $\rho(\pi,\sigma) = \sum |\pi(i)-\sigma(i) |$. If $\sigma$ is chosen uniformly in $S_n$ then:

$$ P( \frac{\rho - Average}{\sqrt{Variance}} < t )= 1/sqrt{(2\pi)}\int_{\infty}^t exp(-x^2/2) dx + O(1)$$

$$ Average(\rho) = (n^2-1)/3, Variance(\rho) = 1/45(n+1)(2n^2+7). $$

Diaconis also describes similar results for other of metrics on symmetric group. Some of them goes to classical results in statistics. And related to rank correlation coefficients by Kendall and Spearman, to Mann-Whitney test, etc (see also MO)... See also recent paper A central limit theorem for a new statistic on permutations Sourav Chatterjee, Persi Diaconis where other generalization for symmetric groups is considered. It is tempting to think, that similar results can be generalized substituting symmetric group by some other groups.

Other metrics.

$L_2$ metric and Spearman's rank correlation (Diaconis p 116 bottom) Consider symmetric group $S_n$ with a metric $S^2(\pi,\sigma) = \sum |\pi(i)-\sigma(i) |^2 $.

It is right invariant. When transformed to lie in [—1,1] as in example 1 of Section A, it arises naturally as the correlation R between the ranks of two samples. It is widely used in applied work. $S^2$ has mean $(n^3 - n)/6$ and variance $n^2(n-1)(n+1)^2/36$. Normalized by its mean and variance, $S^2$ has a limiting normal distribution. These results can all be found in Kendall ("Rank Correlation Methods" 1970). Normality can be proved using Hoeffding's theorem as above .

See MO57629 on Hoeffding's theorem

Kendall's tau (Diaconis p 117) Consider symmetric group $S_n$ with a metric $I(\pi,\sigma) = $ min # (pairwise adjacent transpositions to bring $\pi^{-1}$ to $\sigma^{-1}$).

This metric has a long history, summarized in Kruskal (1958, Sec. 17). It was popularized by Kendall who gives a comprehensive discussion in Kendall ("Rank Correlation Methods" 1970). The definitions in terms of inverses is given to make the metric right invariant.

...

Standardized by its mean and variance / has a standard normal limiting distribution. Kendall (1970) gives tables for small n. An elegant argument for the mean, variance and limiting normality is given in (C-3) below. This also gives fast computational algorithms and correction terms to the normal limit. A second argument is sketched in 5. below.

There are also examples of Cayley, Ulam and Hamming metrices.